哈夫曼树及其应用
路径长度
树中一个结点到另一个结点之间的路径由这两个结点之间的分枝构成，路径上的分枝数目称为它的路径长度。
由树的定义可知，从根结点到达树的每个结点有且仅有一条路径。我们曾规定树的根的层数为1，如果树中某个结点的层数为k，则从树的根到该结点的路径长度为（k-1）。例如，在图1（a）中，从根A到结点B、C、D、E、F、G、H的路径长度分别为1、1、2、2、3、3、4。
树的路径长度是从树的根结点到树的各个结点的路径长度之和，记作PL。例如，图1所示的3棵二叉树的路径长度分别为：
PL(a) = 0+1+1+2+2+3+3+4 = 6
PL(b) = 0+1+1+2+2+2+2+3 = 13
PL(c) = 0+1+1+2+2+2+2+3 = 13
由于二叉树中第k层的结点最多为2k-1个，而树的根到第k层的结点的路径长度为k-1，换句话说，二叉树中路径长度为k-1的这样的结点最多有2k-1个。
显然，在n个结点的各二叉树中，完全二叉树具有最小的路径长度。例如，图1（b）所示为完全二叉树，其路径长度是13。但具有最小路径长度的不一定是完全二叉树。例如，图1（c）所示为非完全二叉树，它也具有最小路径长度。一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。
哈夫曼树
首先我们考虑带权的二叉树。
假如给定一个有n个权值的集合{w1，w2，…，wn}，其中wi≥0（1≤i≤n）。若T是一棵有n个叶子的二叉树，而且将权w1，w2，…，wn分别赋给T的n个叶子，那么我们称T是权w1，w2，…，wn的二叉树。叶子的带权路径长度为T的根到该叶子之间的路径长度与该叶子中权的乘积。n个叶子的二叉树的带权路径长度定义为：
其中：wi为叶子i的权，li为根结点到叶子i之间的路径长度。在权w1，w2，…，wn的二叉树中，其WPL最小的二叉树称为最优树。
例如，图2所示的3棵二叉树都是权值3、6、8、9、10的二叉树，它们的带权路径长度分别为：
WPL(a) = 9×3 +10×3 + 3×2 + 6×2 + 8×2 = 91
WPL(b) = 10×1 +9×2 + 8×3 + 6×4 + 3×4 = 88
WPL(c) = 8×2 +9×2 + 3×3 + 6×3 + 10×2 = 81
其中，（c）的带权路径长度最小。可以验证，在以权值3、6、8、9、10为叶子的所有二叉树中，最小的带权路径长度为81，因此图2（c）所示的二叉树是最优树。
直观地看，若权值越大的叶子离根结点越近，其带权路径长度主越小。我们希望出WPL最小的树即最优树出来。显然，完全二叉树未必是最优树。
如何构造权集合的最优树，哈夫曼（Huffman）提出了一个很好的算法，我们称之为哈夫曼算法，叙述如下：
（1） 由给定的n个权值{w1，w2，…，wn}构成有n棵二叉树的森林F = {T1，T2，…，Tn}，
其中每棵二叉树Ti只有一个带权植wi的根结点，其左、右子树均为空二叉树。
（2） 当森林中至少还有两棵树时，重复下列步骤：
① 将F= {T1，T2，…，Tn}按树的根中权值的大小，从小到大排序。
② 从F中取出根的权值最小的两棵二叉树T1和T2，构造一棵新的二叉树T，使T1和T2分别为T的左子树和右子树，T的根的权值为T1、T2的根的权值之和.
③ 将新二叉树T插入F中。
用哈夫曼算法构造出来的二叉树一定是最优树。事实上，从构造过程可以看出，权值最大的叶子离根最近，权值最小的叶子离根最远，所得二叉树必然具有最小的带权路径长度。于是，最优树又称为哈夫曼树。
例如，设给定的权集合为{7，8，10，6，3}，构成森林F并排序后，如图3（a）所示；用根为3和6的二叉树生成根为9的二叉树，并重新排序后，如图3（b）所示；重复进行下去，直到F中剩下一棵二叉树为止，便得到哈夫曼树，如图3（e）所示，其带权路径长度为：
WPL = 3×3 + 6×3 + 7×2 + 8×2 + 10×2 = 77
哈夫曼编码树的带权路径长度
哈夫曼码
在不同的应用中，对权和带权路径长度有着不同的解释。下面我们来讨论哈夫曼树在数据编码中的一个应用，即数据的最小冗余编码问题。
在电信通讯业务中，我们可以用0和1所组成的编码来表示一个字母或其它字符，用这样的一
个编码序列来表示一个字符序列。假定文本中出现的字符集为26个字母，由于24<26<25，因此最简单的编码方案是每个字母都用固定长度为5的二进制编码来表示。这种编码不考虑字符在文本中出现的频度。
现在讨论另一种编码方案。众所周知，在实际应用中，各个字符出现的频度或使用次数是不相同的。有些字符经常出现，比如A和E；有些字符的使用率很低，比如Z和Q。我们的目标是，希望用短的编码来表示那些出现频度大的字符，用长的编码来表示出现频度小的字符，从而使要表示的字符序列（文本）的编码序列的总长度最小，使所需总空间量最少。这就是最小冗余编码问题。
假定我们要进行编码的字符集为{c1，c2，…，cn}，设各个字符在文本中的出现次数为集合{w1，w2，…，wn}。显然，我们把提出的问题归结为构造一棵有n个叶子的哈夫曼树。叶子中的权值代表字符ci（1≤i≤n）的出现次数wi。最优编码的的是使得下面的带权路径长度具有最小值：
这里，li是字符ci的编码长度，即从根结点到叶子wi的路径长度。
例如，给定下面的字符序列：
            AFTER  DATA  EAR  ARE  ART  AREA
可以看出，这里用到的字符集为{A，E，R，T，F，D}，各字母的出现次数为{8，4，5，3，1，1}。现在要求设计这些字母的最优编码。
我们用{8，4，5，3，1，1}作权构造一棵哈夫曼树，如图4所示。叶子中的权为字母的出现次数。我们在各非终端结点发出的左分枝上标上0，右分枝上标上1。于是，从根结点到叶子的路径上的0和1所组成的序列就是该叶子所对应的字母编码。我们称这样的树为哈 夫曼编码树，由此所得的编码称为哈夫曼码。本例中各字母的哈夫曼码如下所列：
字母
A
E
R
T
F
D
编码
11
00
10
011
0100
0101
其中，出现次数最多的字母A、E、R，具有最短的编码，长度均为2；出现次数最少的字母F、D，具有最长的编码，长度均为4。
哈夫曼码具有下述两个优点：
（1） 对给出的文本具有最短的编码序列；
（2） 任一字符ci的编码不会是另一字符cj（ci≠cj）的编码的前缀（词头）；即使两个字符的出现次数相同（wi = wj），其编码也不相同。例如，上面的A的编码11，与F的编码0100的前缀01是不相同的。这样，两个字符之间不需要加分隔符，但两个单词之间仍需要加空白。
一个任一长度的编码序列可被唯一地翻译为一个字母序列（单词）。依次取出编码序列中的0或1，从哈夫曼编码树的根开始去寻一条路径：若为0，则沿着左分枝往下走；若为1，则沿着右分枝往下走。每到达一个叶子时，就译出一个相应的字母。然后再回到哈夫曼编码树的根结点，依次译出余下的字母，最后得到一个单词。
例如，对于编码序列1110011，对照图4中的哈夫曼编码树，依次取出1、1，从根22走向右孩子13，再走向右孩子8，这已是一个叶子，故译出字母A；然后由10译出R；最后由011译出T。这样，1110011的译码为单词ART。又如，编码序列1101000110010的译码为单词AFTER。
由于哈夫曼码使得编码序列的总长度最短，因此，对于计算机来说，所需的总存贮量最少。但是，由于每个字符的编码长度不一致，这给译码带来困难。因此，通常还是采用固定长度的字符代码。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。