第7章树和二叉树:哈夫曼树

7.11 哈夫曼树

1. 哈夫曼树的基本概念

哈夫曼树，是二叉树的一个具体应用。有关概念如下：

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
• 路径长度：路径上的分支数目称作路径长度。
• 树的路径长度：从树根到每一结点的路径长度之和。
• 权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况决定。
• 带权树：如果一棵树中的结点上带有权值，则称此树为带权树。
• 结点的带权路径长度：从根结点到具有权值的结点之间的路径长度与该结点上权的乘积，为结点的带权路径长度（Weighted Path Length, WPL）。
• 树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作WPL = ∑ k = 1 n w k l k \text{WPL}=\sum\limits_{k=1}^nw_kl_kWPL=k=1∑n​wk​lk​，其中n nn表示叶子结点的个数，w k w_kwk​和l k l_klk​分别表示第k kk个叶子结点的权值和根到它之间的路径长度（即从根结点到该叶子结点的路径上经过的分支数）。

以图 7.10.3 所示二叉树为例：

• 从结点 G 到结点 J 的路径是：G → H → I → J G\to H\to I\to JG→H→I→J；从 A 到 D 的路径是：A → B → C → D A\to B\to C\to DA→B→C→D。
• 从根结点 A 到 叶子结点 D 的路径长度是 3（共计 3 个分支）；从 E 到 H 的路径长度是 2。
• 记录下从根结点 A 到每结点的路径长度l k ( k = 1 , 2 , ⋯ , 9 , 即 : B , C , D , E , F , G , H , I , J ) l_k~(k=1,2,\cdots,9,即:B,C,D,E,F,G,H,I,J)lk​(k=1,2,⋯,9,即:B,C,D,E,F,G,H,I,J)，则该二叉树的路径长度是：L = ∑ k = 1 9 l k L=\sum\limits_{k=1}^9l_kL=k=1∑9​lk​。
• 假设叶子结点 D，F，J 权分别是 7,2,8 ，那么结点 D 的带权路径长度为：7 × 3 = 21 7\times3=217×3=21。
• 二叉树的带权路径长度为：WPL = 7 × 3 + 2 × 2 + 8 × 5 = 65 \text{WPL}=7\times3+2\times2+8\times5=65WPL=7×3+2×2+8×5=65。

如果有一组具有确定权值的叶子结点，用这些叶子结点可以构造出多个具有不同带权路径长度的二叉树，如图 7.11.1 所示，由 4 个具有确定权值的叶子结点构成了 4 棵不同的二叉树，这些树的带权路径分为为：

• 图 7.11.1(a)：WPL = 1 × 2 + 3 × 2 + 5 × 2 + 7 × 2 = 32 \text{WPL}=1\times2+3\times2+5\times2+7\times2=32WPL=1×2+3×2+5×2+7×2=32
• 图 7.11.1(b)：WPL = 1 × 2 + 3 × 3 + 5 × 3 + 7 × 1 = 33 \text{WPL}=1\times2+3\times3+5\times3+7\times1=33WPL=1×2+3×3+5×3+7×1=33
• 图 7.11.1©：WPL = 7 × 3 + 5 × 3 + 3 × 2 + 1 × 1 = 43 \text{WPL}=7\times3+5\times3+3\times2+1\times1=43WPL=7×3+5×3+3×2+1×1=43
• 图 7.11.1(d)：WPL = 1 × 3 + 3 × 3 + 5 × 2 + 7 × 1 = 29 \text{WPL}=1\times3+3\times3+5\times2+7\times1=29WPL=1×3+3×3+5×2+7×1=29

由上述计算可知，即使叶子结点的权值相同，但是由于二叉树不同或者在二叉树中的位置不同，最终所得到的二叉树的带权路径长度 WPL 的值也不同，特别是比较图 7.11.1© 和图 7.11.1(d) 可知，如果将权值比较大的叶子结点放置在靠近根结点的位置，即路径长度小；而叶子结点权值较小的，放置在远离根结点的位置，即路径长度大，这样所构造的二叉树的 WPL 的值较小。

假设有m mm个权值{ w 1 , w 2 , ⋯ , w m } \{w_1,w_2,\cdots,w_m\}{w1​,w2​,⋯,wm​}，可以构造一棵含n nn个叶子结点的二叉树，每个叶子结点的权为w i w_iwi​，则其中带权路径长度 WPL 最小的二叉树称做最优二叉树或哈夫曼树。

图 7.11.1(d) 的 WPL 是图中各树最小，并且可以验证，它恰为哈夫曼树，即其带全路径长度在所有权为 7, 5, 3, 1 的 4 个叶子结点的二叉树中最小。

由上述例子，可以直观地发现，在哈夫曼树中，权值越大的结点离根结点越近。根据这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称哈夫曼算法。

2. 哈夫曼树的构造算法

（1）哈夫曼树的构造过程

1. 根据给定的n nn个权值{ w 1 , w 2 , ⋯ , w n } \{w_1,w_2,\cdots,w_n\}{w1​,w2​,⋯,wn​}，构造n nn棵只有根结点的二叉树，这n nn棵二叉树构成一个森林F FF。
2. 在森林F FF中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3. 在森林F FF中删除这两棵树，同时将新得到的二叉树加入F FF中。
4. 重复 (2) 和 (3) ，直到F FF只含一棵树为止。这棵树便是哈夫曼树。

在构造哈夫曼树时，首先选择权小的，这样保证权大的离根较近，这样一来，在计算树的带权路径长度时，自然会得到最小带权路径长度，这种生成算法是一种典型的贪心法。

贪心算法（Greedy Algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

例如，图 7.11.2 为哈夫曼树的构造过程。

（2）哈夫曼算法的实现

哈夫曼树是一种二叉树，可以采用之前所学习过的通用存储方法，而由于哈夫曼树中没有度为1 11的结点，则一棵有n 0 n_0n0​个叶子结点（即二叉树中度为 0 的结点）的哈夫曼树共有2 n 0 − 1 2n_0-12n0​−1个结点，可以存储在一个大小为2 n 0 − 1 2n_0-12n0​−1的一维数组中。

【定理】对于具有n 0 n_0n0​个叶子结点的哈夫曼树，共有2 n 0 − 1 2n_0-12n0​−1个结点。

证明：在哈夫曼树的构造过程中，每次都是将两棵树合并为一棵树，所以哈夫曼树中不存在度为 1 的结点，即n 1 = 0 n_1=0n1​=0。

由二叉树的性质，n 0 = n 2 + 1 n_0=n_2+1n0​=n2​+1，即n 2 = n 0 − 1 n_2=n_0-1n2​=n0​−1，则n = n 0 + n 1 + n 2 = n 0 + n 2 = n 0 + n 0 − 1 = 2 n 0 − 1 n=n_0+n_1+n_2=n_0+n_2=n_0+n_0-1=2n_0-1n=n0​+n1​+n2​=n0​+n2​=n0​+n0​−1=2n0​−1。

树中每个结点还要包含其双亲信息和孩子结点的信息，由此，每个结点的存储结构设计如图 7.11.3 所示。

哈夫曼树中的结点类型：

typedefstruct{intweight;//结点的权值intparent,lchild,rchild;//结点的双亲、左孩子、右孩子的下标}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树

哈夫曼树的各结点存储在由 HufmanTree 定义的动态分配的数组中，为了实现方便，数组的 0 号单元不使用，从 1 号单元开始使用，所以数组的大小为2 n 2n2n。将叶子结点集中存储在前面部分1 ∼ n 1\sim n1∼n个位置，而后面的n − 1 n-1n−1个位置存储其余非叶子结点。

【算法步骤】

构造哈夫曼树算法的实现可以分成两大部分。

① 初始化：

• 首先动态申请2 n 2n2n个单元；

• 然后循环2 n − 1 2n-12n−1次，从 1 号单元开始，依次将 1 至2 n − 1 2n-12n−1所有单元中的双亲、左孩子、右孩子的下标都初始化为 0；

• 最后再循环n nn次，输入前n nn个单元中叶子结点的权值。

② 创建树：循环n − 1 n-1n−1次，通过n − 1 n-1n−1次的选择、删除与合并来创建哈夫曼树。

• 选择是从当前森林中选择双亲为 0 且权值最小的两个树根结点 s1 和 s2；
• 删除是指将结点 s1 和 s2 的双亲改为非 0；
• 合并就是将 s1 和 s2 的权值和作为一个新结点的权值依次存入到数组的第n + 1 n+1n+1之后的单元中，同时记录这个新结点左孩子的下标为 s1，右孩子的下标为 s2。

【算法描述】

voidCreateHuffmanTree(HuffmanTree&HT,intn){//构造哈夫曼树 HTif(n<=1)return;m=2*n-1;HT=new HTNode[m+1];//0 号单元未用，所以需要动态分配 m+1 个单元，HT[m] 表示根结点for(i=1;i<=m;++i){//将 1~m 号单元中的双亲、左孩子、右孩子的下标都初始化为 0HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n;++i){//输入前 n 个单元叶子结点的权值cin>>HT[i].weight;}//初始化工作结束，下面开始创建哈夫曼树for(i=n+1;i<=m;++i){//通过 n-1 次的选择、删除、合并来创建哈夫曼树//在 HT[k] (1≤k≤i-1) 中选择两个其双亲域为 0 且权值最小的结点，//并返回它们在 HT 中的序号 s1 和 s2Select(HT,i-1,s1,s2);//得到新结点 i，从森林中删除 s1, s2，//将 s1 和 s2 的双亲域由 0 改为 iHT[s1].parent=i;HT[s2].parent=i;//s1, s2 分别作为 i 的左右孩子HT[i].lchild=s1;HT[i].rchild=s2;//i 的权值为左右孩子权值之和HT[i].weight=HT[s1].weight+HT[s2].weight;}}

例 7.11.1已知w = ( 5 , 29 , 7 , 8 , 14 , 23 , 3 , 11 ) w=(5, 29, 7, 8, 14, 23, 3, 11)w=(5,29,7,8,14,23,3,11)，利用哈夫曼树的构造方法，构造一棵哈夫曼树，并计算树的带权路径长度。

【解】

1. 将叶子结点按照权值从小到大排序，如下图所示。

2. 将前两个叶子结点构造成一个新的二叉树，并且重新排序。

3. 按照上述的方法，不断构建二叉树，最终得到哈夫曼树。
   

WPL = ( 3 + 5 + 7 + 8 ) × 4 + ( 11 + 14 ) × 3 + ( 23 + 29 ) × 2 = 271 \text{WPL}=(3+5+7+8)\times4+(11+14)\times3+(23+29)\times2=271WPL=(3+5+7+8)×4+(11+14)×3+(23+29)×2=271

例 7.11.1高度为h ( h ≥ 1 ) h~(h\ge1)h(h≥1)的哈夫曼树中，至少有（①） 个结点，至多有（②）个结点。

A.2 h − 1 2^h-12h−1\qquadB.2 h − 1 2^{h-1}2h−1\qquadC.2 h 2h2h\qquadD.2 h − 1 2h-12h−1

【解】

当高度为h ( h ≥ 1 ) h~(h\ge1)h(h≥1)的哈夫曼树为一个满二叉树时结点个数最多，此时总节点数为2 h − 1 2^h-12h−1。最少时第 1 层只有一个结点，2~h 层各 2 个节点，此时为2 h − 1 2h-12h−1个。

本题答案：①D；②A

例 7.12.1由带权为 9、2、5、7 的 4 个叶子结点构成的一棵哈夫曼树的带权路径长度是（ ）

A. 23\qquadB.37\qquadC. 46\qquadD. 44

【解】

根据权值构造如下图所示的哈夫曼树，计算其带全路径长度= ( 2 + 5 ) × 3 + 7 × 2 + 9 × 1 = 44 =(2+5)\times3+7\times2+9\times1=44=(2+5)×3+7×2+9×1=44。

本题答案：D