第9讲 哈夫曼树及其构造——教学讲义
哈夫曼树可用来构造最优编码，用于信息传输、数据压缩等方面，哈夫曼树是一种应用广泛的二叉树。 一、 哈夫曼树
1．哈夫曼树的基本概念
在介绍哈夫曼树之前，先给出几个基本概念。 ● 结点间的路径和路径长度
路径是指从一个结点到另一个结点之间的分支序列，路径长度是指从一个结点到另一个结点所经过的分支数目。
● 结点的权和带权路径长度
在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。在树型结构中，把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。 ● 树的带权路径长度
树的带权路径长度为树中从根到所有叶子结点的各个带权路径长度之和，通常记为：
∑=⨯=n
1
i i
i l w WPL
其中n 为叶子结点的个数，w i 为第i 个叶子结点的权值，l i 为第i 个叶子结点的路径长度。 例6-5 计算下图中三棵二叉树的带权路径长度。 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35
研究树的路径长度PL 和带权路径长度WPL，目的在于寻最优分析。 问题1: 什么样的二叉树的路径长度PL 最小？
一棵树的路径长度为0结点至多只有1个    （根）            路径长度为1结点至多只有2个 （两个孩子）              路径长度为2结点至多只有4个
依此类推：  路径长度为K 结点至多只有  2k
个
所以n 个结点二叉树其路径长度至少等于如下图所示序列的前n 项之和。
0 ，1 ， 1 ，2， 2，  2， 2，3， 3，3，3，3，3，3，3，4，4，.......  n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8    ...          n=15
结点序列及结点的路径长度
A    B    C    D 7    5    2    4 (a)权为36      C    B D    A 7    5 2
4 (b)权为46
A  B  C    D 7    5    2    4 (c)权为35 具有不同带权路径长度的二叉树
由上图可知，结点n 对应的路径长度为⎣⎦n log 2，所以前n 项之和为
2
1
log
n
k k =⎢⎥⎣⎦∑。
完全二叉树的路径长度=0122
1
2021222log
h
h
k h k =⨯+⨯+⨯++⨯=
⎢⎥⎣⎦∑ (h 为树的深度)，
所以完全二叉树具有最小路径长度的性质，但不具有惟一性。有些树并不是完全二叉树，但
也可以具有最小路径长度。如下图所示。
例          A                                      A
B      C                              B      C
D      E                                D              E
PL=0+1+1+2+2=6                          PL =0+1+1+2+2=6
具有相同最小路经长度的不同形态的二叉树 问题2：什么样的带权的树路径长度最小？
例如：给定一个权值序列{2,3,4,7}，可构造如下图所示的多种二叉树的形态。                        o                        o
o  o                      2 o  o                  o  o o  o                      3 o  o
2  3  4  7                        4 o    o7
(a)WPL=2*2+2*3+2*4+2*7=32        (b)WPL=1*2+2*3+3*4+3*7=41                  o                                            7o  o                                    4 o    o                                  3 o    o 2
(c)WPL=1*7+2*4+3*3+3*2=7+8+9+6=30
具有不同带权路径长度的二叉树 上图(a)所示二叉树是完全二叉树，但并不具有最小带权的路径长度，由此可见完全二叉树不一定WPL 最小，如何在Min{m(T)}中最小呢？
给定n 个实数w 1,....w n (n>=2)，求一个具有n 个终端结点的二叉树，使其带权路径长
度∑w i l i 最小。其中每个终端结点k i 有一个权值w i 与它对应，l i 为根到叶子的路                  径长度。由于哈夫曼给出了构造这种树的规律，将给定结点构成一棵（外部通路）带权树的路径长度最小的二叉树，因此就称为哈夫曼树。 2. 构造哈夫曼树
哈夫曼树：它是由n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。因为这种树最早由哈夫曼（Huffman ）研究，所以称为哈夫曼树，又叫最优二叉树，图6.38（c ）所示的二叉树就是一棵哈夫曼树。
构造哈夫曼树的算法步骤如下： （1） 初始化：用给定的n 个权值 {w 1, w 2, … , w n } 对应的由n 棵二叉树构成的森林
哈夫曼编码树的带权路径长度
F={T 1,T 2, …,T n }，其中每一棵二叉树T i (1≤i ≤n)都只有一个权值为w i 的根结点，其左、右子树为空。 （2） 最小树：在森林F 中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、
右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和。
（3） 删除与加入：从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。
（4） 判断：重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。
直观地看，先选择权小的，所以权小的结点被放置在树的较深层，而权较大的离根较近，这样自然在哈夫曼树中权越大叶子离根越近，这样一来，在计算树的带权路径长度时，自然会具有最小带权路径长度，这种生成算法就是一种典型的贪心法。
手工构造的方法也非常简单：给定一组权值{ w1, w2, …, w n}，用n个权值构成n棵单根树的森林F；将F={T1，T2，…，T n}按权值从小到大排列；取T1和T2合并组成一棵树，使其根结点的权值T=T1+T2，再按大小插入F，重复此过程，直到只有一棵树为止。
给定一组权值{7，4，3，2 }，用上述方法构造哈夫曼树，将得到图6.38（c）所示的二叉树。
3. 哈夫曼树的类型定义
（1） 存储结构
哈夫曼树是一种二叉树，当然可以采用前面已经介绍过的通用存储方法，而哈夫曼树是求某种最优方案，由于哈夫曼树中没有度为1的结点，因此一棵有n个叶子的哈夫曼树共有2×n－1个结点，可以用一个大小为2×n－1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点
的信息，所以构成一个静态三叉链表。
静态三叉链表中：每个结点的结构如下图所示。：
权值双亲序号左孩子序号右孩子序号
静态三叉链表中结点的结构
各结点存储在一维数组中，0号单元不使用，从1号位置开始使用。
下图给出了一棵二叉树及其静态三叉链表。
( a ) 一棵二叉树                            ( b ) 静态三叉链表
一棵二叉树及其静态三叉链表
对于有n个叶子结点的哈夫曼树，结点总数为2n－1个，为实现方便，将叶子结点集中存储在前面部分1~n个位置，而后面的n－1个位置中存储其余非叶子结点。
（2）哈夫曼树的类型定义
用静态三叉链表实现的哈夫曼树类型定义如下：
#define N 20 /* 叶子结点的最大值。*/
#define M 2*N-1 /* 所有结点的最大值。*/
typedef struct
{
int weight ; /* 结点的权值*/
int  parent ;  /* 双亲的下标*/
int  LChild ;  /* 左孩子结点的下标*/ int  RChild ;  /* 右孩子结点的下标*/
} HTNode,  HuffmanTree[M+1];  /*  HuffmanTree 是一个结构数组类型，0号单元不用。 */
4．哈夫曼树的算法实现
【算法描述】  创建哈夫曼树算法
void CrtHuffmanTree(HuffmanTree  ht,  int  w[ ],  int n) { /*构造哈夫曼树ht[M+1]， w[ ]存放n 个权值。*/
for(i=1;i<=n;i++) ht[i] ={ w[i],0,0,0};  /* 1 ~ n 号单元存放叶子结点，初始化*/ m=2*n-1;
for(i=n+1;i<=m;i++) ht[i] ={0,0,0,0};  /* n+1 ~ m 号单元存放非叶结点，初始化 */ ————————————初始化完毕！对应算法步骤1————————— for(i=n+1; i<=m; i++)    /*创建非叶结点，建哈夫曼树*/ {
select(ht, i-1, s1, s2);    /* 在 ht[1] ~ ht[i-1] 的范围内选择两个parent 为0且
weight 最小的结点，其序号分别赋值给s1、s2返回 */
ht [i].weight= ht [s1].weight+ ht [s2].weight; ht [s1].parent=i;  ht [s2].parent=i; ht [i].LChild=s1;  ht [i].RChild=s2; }  /*哈夫曼树建立完毕*/
}
该算法分成两大部分，其中第一部分是初始化，先初始化ht 的前1~n 号元素，存放叶子结点（相当初始森林），它们都没有双亲与孩子。再初始化ht 的后n-1个（从n+1~2n-1）非叶结点元素；第二部分为实施选择、删除合并n-1次（相当步骤（2）~（4））：选择是从当前森林中（在森林中树的根结点的双亲为0）选择两棵根的权值最小的树；删除合并是将选到的两棵树的根权和存入ht 的当前最前面的空闲元素中（相当于合并树中新结点），并置入相应的双亲与孩子的位置指示。
例 数据传送中的二进制编码。要传送数据 state, seat, act, tea, cat, set, a ,eat ，如何使传送的长度最短？
为了保证长度最短，先计算各个字符出现的次数，将出现次数当作权，如表6-2所示。
表6-2 题中各字符频率
按权构造哈夫曼树的过程如下图所示。
字符
s t    a    c    e 字符出现的次数
3
8
7
5
2
构造哈夫曼树的过程
按照创建哈夫曼树算法，该例建立哈夫曼树的结果如下表6-3与表6-4： 表6-3  哈夫曼树的初态：                        表6-4 哈夫曼树的终态：

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