6.5.2　最优二叉树——哈夫曼树

1.哈夫曼树的基本概念

最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

那么什么是二叉树的带权路径长度呢？

在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫作二叉树的带权路径长度，记为：其中，Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。如图6－24所示的二叉树的带权路径长度值WPL＝2×2＋4×2＋5×2＋3×2＝28。

图6－24 一个带权二叉树

给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图6－25给出了其中5个不同形状的二叉树。

这五棵树的带权路径长度分别为：

（a）WPL＝1×2＋3×2＋5×2＋7×2＝32

（b）WPL＝1×3＋3×3＋5×2＋7×1＝29

（c）WPL＝1×2＋3×3＋5×3＋7×1＝33

（d）WPL＝7×3＋5×3＋3×2＋1×1＝43

（e）WPL＝7×1＋5×2＋3×3＋1×3＝29

图6－25 具有相同叶子结点和不同带权路径长度的二叉树

由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼依据这一特点提出了一种方法，这种方法的基本思想是：

（1）由给定的n个权值｛W1，W2，…，Wn｝构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝｛T1，T2，…，Tn｝；

（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；

（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；

（4）重复（2）和（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

图6－26给出了前面提到的叶结点权值集合为W＝｛1，3，5，7｝的哈夫曼树的构造过程。可以计算出其带权路径长度为29，由此可见，对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。

2.哈夫曼树的构造算法

在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组Huff－Node的大小设置为2n－1，数组元素的结构形式如下：

图6－26 哈夫曼树的建立过程

其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。

构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。

下面给出哈夫曼树的构造算法。

算法6.25 构造哈夫曼树

3.哈夫曼树在编码问题中的应用

在数据通信中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A、B、C、D四种字符，若这四种字符采用图6－27（a）所示的编码，则电文的代码为000010000100100111000，长度为21。在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。图6－27（b）所示为另一种编码方案，用此编码对上述电文进行编码所建立的代码为00010010101100，长度为14。在这种编码方案中，四种字符的编码均为两位，是一种等长编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。如当字符A、B、C、D采用图6－27（c）所示的编码时，上述电文的代码为0110010101110，长度仅为13。

图6－27 字符的四种不同的编码方案

哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为｛d1，d2，…，dn｝，它们在电文中出现的次数或频率集合为｛w1，w2，…，wn｝，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称为哈夫曼编码。

在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。

在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。例如，图6－27（d）的编码方案，字符A的编码01是字符B的编码010的前缀部分，这样对于代码串0101001，既是AAC的代码，也是ABD和BDA的代码，因此，这样的编码不能保证译码的唯一性，我们称为具有二义性的译码。

然而，采用哈夫曼树进行编码，则不会产生上述二义性问题。因为在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其他字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。

下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分：

（1）构造哈夫曼树；

（2）在哈夫曼树上求叶结点的编码。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。我们可以设置一结构数组HuffCode用来存放各字符的哈夫曼编码信息，数组元素的结构如下：

其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCode［i］.bit中的从HuffCode［i］.start到n的分量上。

哈夫曼编码算法描述如下。

算法6.26 哈夫曼编码

4.哈夫曼树在判定问题中的应用

例如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如：

这个判定过程可以图6－28（a）所示的判定树来表示。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如表6－2所示。

表6－2 学生成绩分布

80%以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和10为权构造一棵有五个叶子结点的哈夫曼树，则可得到如图6－28（b）所示的判定过程，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到如图6－28（c）所示的判定树，按此判定树可写出相应的程序。假设有10 000个输入数据，若按图6－28（a）的判定过程进行操作，则总共需进行31 500次比较；而若按图6－28（c）的判定过程进行操作，则总共仅需进行22 000次比较。

图6－28 转换五级分制的判定过程