4.5.3 哈弗曼树（Huffman）树和哈弗曼编码

1.哈夫曼树的定义

树中结点被赋予一个表示某种意义的数值，称为该结点的权。从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为

WPL=连加Wi*Li

式中，Wi是第i个叶结点所带的权值；Ii是该叶结点到根结点的路径长度。

在含有N个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈弗曼树，也称为最优二叉树。

2.哈夫曼树的构造

给定N个权值分别是w1,W2,……，Wn的结点

1）将这N个结点分别分为N棵含一个结点的二叉树，构成森林F.

2）构成一个新结点，并从F中选取两个根结点权值最小的树作为新结点左、右子树，并且将新结点的权值置成左、右子树上根结点的权值之和。

3）从F中删除刚才选出的两棵树，同时将得到的树加入F中。

4）重复步骤2）和3），直到F中只剩下一棵树为止。

哈夫曼树具有如下特点：

1）每个初始结点最终都成叶结点，并且权值最小的结点到根结点的路径长度越大。

2）构造过程中共新建了N-1个结点（双分支结点），因此哈夫曼树中结点总数为2N-1。

3）每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。

3.哈夫曼编码

对于待处理的一个字符串序列，如果对每个字符采用同样长度的二进制来表示，则称这种编码方式为固定长度编码。

如果对不同字符采用不等长的二进制来表示，则称这种编码方式为可变长度编码。

如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。如0、101和100是前缀编码。

解码过程：因为没有一个码是其他码的前缀，所以，可以识别出第一个编码，将它翻译为源码，再对余下的编码文件重复同样的解码操作。如00101100可被唯一地解析为0、0、101和100。

由哈夫曼树得到哈夫曼编码是一个很自然的过程，首先，将每个出现的字符当做一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然所有字符结点都出现在叶子结点。我们可以将字符的编码解释为从根至该路径上边标记的序列，其中边标记为0表示“转向左孩子”，标记为1表示“转向右孩子”。

WPL可以看成是最终编码得到二进制编码的长度。