本系列为数据结构学习笔记(待汇总)。

1 赫夫曼树

先看如下两棵树：
mark

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。

二叉树 a 中，根结点到结点 D 的路径长度为 4，二叉树 b 中根结点到结点 D 的路径长度为 2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树 a 的树路径长度就为 1+1+2+2+3+3+4+4=20。二叉树 b 的树路径长度就为1+2+3+3+2+1+2+2=16。

考虑到带权的结点，结点的带权的路径长度为该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值$\{w_1,w_2,…,w_n\}$，构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权 $W_k$，每个叶子的路径长度为 $l_k$，则其中带权路径长度(WPL)最小的二叉树称做赫夫曼树，也称为最优二叉树。

二叉树 a 的 $WPL=5 1+15 2+40 3+30 4+10 * 4 = 315 $
二叉树 b 的 $WPL=5 3+ 15 3+40 2+30 2+ 10 * 2 = 220 $

2 赫夫曼树构造方法

先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即 : A5，E10 , B15 , D30, C40。
取头两个最小权值的结点作为一个新节点 N1的两个子结点，注意相对较小的是左孩子，这里就是 A 为 N1 的左孩子， E 为 N1的右孩子，如图 6-12-5 所示。新结点的权值为两个叶子权值的和 5+10=15。
将 N1替换 A 与 E，插入有序序列中，保持从小到大排列。即: N1-15, B-15 , D-30, C-40。
重复步骤 2. 将 N1 与 B 作为一个新节点 N2的两个子结点。如图 6-12-6 所示。 N2 的权值=15+15=30。
将 N2 替换 N1 与 B ，插入有序序列中，保持从小到大排列。即: N2-30 , D-30, C-40。
重复步骤 2. 将 N2 与 D 作为一个新节点 N3 的两个子结点。如图 6-12-7 所
示。 N3 的权值=30+30=60。
将 N3替换 N2与 D，插入有序序列中，保持从小到大排列。即 : C-40 , N3-60。
重复步骤 2。将 C 与 N3 作为一个新节点 T 的两个子结点，如图 6-12-8 所示。由于 T 即是根结点，完成赫夫曼树的构造。

构造赫夫曼树的赫夫曼算法描述：

根据给定的 n 个权值$\{w_1,w_2,…,w_n\}$构成 n 棵二叉树的集合 $F = \{T_1,T_2,…,T_n\}$，其中每棵二叉树 $T_i $中只有一个带权为 $w_i$根结点，其左右子树均为空。
在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
重复 2 和 3 步骤，直到 F 只含一棵树为止。这棵树便是赫夫曼树。

3 赫夫曼编码

用于压缩和解压缩文件，把要压缩的文本进行重新编码，以减少不必要的空间。
比如我们有一段文字内容为 “BADCADFEED” 要网络传输给别人，显然用二进制的数字 (0 和 1) 来表示是很自然的想法。我们现在这段文字只有六个字母 ABCDEF，那么我们可以用相应的二进制数据表示：
mark

这样真正传输的数据就是编码后的 “001000011010000011101100100011“，对方接收时可以按照 3 位划分来译码。效率低下。

根据不同词频使用赫夫曼树重新编码。

假设六个字母的频率为 A 27 , B 8, C 15 , D 15 , E 30, F 5 ，合起来正好是 100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

以下左图为按照第2节的赫夫曼树构造方法得到的赫夫曼树，右图为将所有左分支改为0，右分支改为1后的赫夫曼树。
mark

对着六个字母重新编码如下：
mark

我们将文字内容为 “BADCADFEED” 再次编码，对比可以看到结果串变小了。

原编码二进制串 :001000011010000011101100100011(共30个字符)
新编码二进制率: 1001010010101001000111100(共 25 个字符)

数据被压缩了。

4 赫夫曼解码

前缀编码：编码中非 0 即 1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。

当我们接收到 1001010010101001000111100 时，按约定好的赫夫曼树可知， 1001 得到第一个字母是 B，接下来的01意味着第二个字符是 A，如图 6-12-10 所示，其余的也相应的可以得到，从而成功解码。
mark

5 赫夫曼编码定义

一般地，设需要编码的字符集为$\{d_1,d_2,…,d_n\}$，各个字符在电文中出现的次数或频率集合为$\{w_1,w_2,…,w_n\}$ ，以 $d_1,d_2,…,d_n$作为叶子结点，以 $w_1,w_2,…,w_n$ 作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是赫夫曼编码。

参考文献：
程杰. 大话数据结构