哈夫曼编码的数据结构和算法（漫步计算机系统）
哈夫曼编码的数据结构和算法（漫步计算机系统）F:1E:4首先，我们统计这串字符中每个字符出现的次数，作为权值：A:8D:1
定义：给定有N个权值的N个叶子结点，每个叶子结点代表一个字符，权值可表示为字符出现的频率或概率。构造出一棵带权路径最小的二叉树即最优二叉树，权值较大的结点离根结点较大，使这些字符组成的串所需的二进制编码最少。
哈夫曼编码在通讯领域应用广泛。
在通讯中，需要将字符串转换为二进制串，假设要传输的字符串为“AFTERDATAEARAREARTAREA”，现在我们就来将其编码：
由以上定义可知，结点的权值越小，离根结点越远，越有可能成为叶子结点，使整棵二叉树的带权路径最小。
首先，我们统计这串字符中每个字符出现的次数，作为权值：
A:8
D:1
E:4
F:1
R:5
T:3
接下来构造哈夫曼树：
重复以下步骤：
- 按照权值从小到大对字符排序：D-F-T-E-R-A；
- 选择权值最小的两个字符作为两个结点，此处为D和F，生成一个新的结点，新结点的权值为它们的和；
直至字符串中所有字符都生成了结点。
生成过程如下图：
现在，我们需要利用最终生成的二叉树对每个字符进行编码，该编码又叫哈夫曼编码。
我们约定：
- 将权值较小的结点作为左结点，较大的作为右结点；
- 左孩子编码为0，右孩子编码为1。
最终的哈夫曼树为：
从上图可知，E结点的编码为：00，D结点的编码为1001。
最终各字符的编码为：
E:00
R:01
F:1000
D:1001
T:101
A:11
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。
