在权为 wl，w2，…，wn 的 n 个叶子所构成的所有二叉树中，带权路径长度最 小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。 [例]给定 4 个叶子结点 a，b，c 和 d，分别带权 7，5，2 和 4。构造如下图 所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=4 (c)WPL=7*1+5*2+2*3+4*3=35 其中(c)树的 WPL 最小，可以验证，它就是哈夫曼树。
1、课题设计目的: (1)巩固构造哈夫曼树的算法。
(2)设计算法实现哈夫曼树及哈夫曼编码的构造。
2、课题设计意义： （1）通过设计此课程，让我对哈夫曼树有了更深的了解。 （2）通过设计此课程，让我们对老师课上的讲述有了更深的理解， 课题设计 目的与 设计意义 让所学有所思。 （3）哈夫曼树的编译码具体应用在生活中，使我们明白了数据结 构这一课程在实际生活中具有重要意义。
1.2 树的带权路径长度
树的带权路径长度(Weighted Path Length of Tree)：也称为树的代价，定 义为树中所有叶结点的带权路径长度之和，通常记为：
其中：n 表示叶子结点的数目 wi 和 li 分别表示叶结点 ki 的权值和根到结点 ki 之间的路径长度。
1．3 哈夫曼树的定义
指导教师： 年 月 日
目
录
第一章 哈夫曼树的基本术语......................................................................................1 1．1 路径和路径长度............................................................................................1 1.2 树的带权路径长度...........................................................................................1 1．3 哈夫曼树的定义............................................................................................1 第二章 哈夫曼树的构造..............................................................................................2 2.1 哈夫曼树的构造...............................................................................................2 第三章 哈夫曼树的存储结构及哈夫曼算法的实现..................................................3 3.1 哈夫曼树的存储结构.......................................................................................3 3.2 哈夫曼算法的简要描述..................................................................................3 第四章 哈夫曼树的应用............................................................................................5
3
将 T[p1]和 T[p2]的 parent 置为 i， 将 T[i]的 lchild 和 rchild 分别置为 p1 和 p2 新结点 T[i]的权值置为 T[p1]和 T[p2]的权值之和。 注意： 合并后 T[pl]和 T[p2]在当前森林中已不再是根，因为它们的双亲指针均已 指向了 T[i]，所以下一次合并时不会被选中为合并对象。
3.2 哈夫曼算法的简要描述
在上述存储结构上实现的哈夫曼算法可大致描述为(设 T 的类型为 HuffmanTree)： (1)初始化 将 T[0．．m-1]中 2n-1 个结点里的三个指针均置为空(即置为-1)，权值置 为 0。 (2)输人 读人 n 个叶子的权值存于向量的前 n 个分量(即 T[0．．n-1])中。它们是初 始森林中 n 个孤立的根结点上的权值。 (3)合并 对森林中的树共进行 n-1 次合并，所产生的新结点依次放人向量 T 的第 i 个分量中(n≤i≤m-1)。每次合并分两步： ①在当前森林 T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点 [p1]和 T[p2]作为合并对象，这里 0≤p1，p2≤i-1。 ② 将根为 T[p1]和 T[p2]的两棵树作为左右子树合并为一棵新的树， 新树的 根是新结点 T[i]。具体操作：
5
① 由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放 在一个临时向量中， 并设一个指针 start 指示编码在该向量中的起始位置 （start 初始时指示向量的结束位置）。 ② 当某字符编码完成时，从 start 处将编码复制到该字符相应的位串 cd 中即可。 4.22 字符集编码的存储结构及其算法描述 typedef struct { char cd[N]; /*存放哈夫曼码*/ int start; } HCode;
4
第四章
4.1 哈夫曼编码
哈夫曼树的应用
通信中，可以采用 0,1 的不同排列来表示不同的字符，称为二进制编码。而 哈夫曼树在数据编码中的应用， 是数据的最小冗余编码问题，它是数据压缩学的 基础。 若每个字符出现的频率相同， 则可以采用等长的二进制编码， 若频率不同， 则可以采用不等长的二进编码， 频率较大的采用位数较少的编码，频率较小的字 符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小编码 的问题。 而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种 最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为 0， 往右编码为 1，则得到叶子结点编码为从根结点到叶子结点中所有路径中 0 和 1 的顺序排列。 例如，给定权{1,5,7,3}，得到的哈夫曼树及编码见图 6-32 (假定权值就代 表该字符名字)。 1 的哈夫曼编码 100 5 的哈夫曼编码 11
4.1 哈夫曼编码.......................................................................................................5 4.2 求哈夫曼编码的算法.......................................................................................5 4.21 思想方法..................................................................................................5 4.22 字符集编码的存储结构及其算法描述..................................................6 4.3 哈夫曼树和编码程序实现：...........................................................................6 4.4 程序运行结果：...............................................................................................9 心得体会...............................................................................................................10 参考文献......................................................................................................................10
1
第二章 哈夫曼树的构造
2.1 哈夫曼树的构造
a b (a)初始森林 c d
6
a
7
b
5
c
2
(b)c 与 d 合并
d
4
18 7
a b
11 7 5 6 5
c a b
11 6 2
2
d
4
c
d
4
图1ห้องสมุดไป่ตู้
哈夫曼树的构造过程
假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设 为 w1,w2,…,wn,则哈夫曼树的构造规则为： (1) 将 w1,w2,…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右 子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈 夫曼树。 下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为 1,5,7,3， 则构造哈夫曼树过程如下图所示。从图中可知，n 个权值构造哈夫曼树需 n-1 次合并，每次合并，森林中的树数目减 1，最后森林中只剩下一棵树，即为我们 求得的哈夫曼树。
9 4 5 1 3
16 7
7 的哈夫曼编码 0 3 的哈夫曼编码 101