大学《数据结构》第五章：树和二叉树-第六节-哈夫曼树及其应用

第六节哈夫曼树及其应用

一、最优二叉树(哈夫曼树)

1.树的路径长度

树的路径长度是从树根到树中每一结点的路径长度之和。在结点数

目相同的二叉树中，完全二叉树的路径长度最短。

2.树的带权路径长度(WPL)

结点的权：在一些应用中，赋予树中结点的一个有某种意义的实

数。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的

乘积。

树的带权路径长度(WPL):定义为树中所有叶结点的带权路径长度

之和。

3.最优二叉树或哈夫曼树

带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。

【例】给定4个叶子结点a,b,c和d,分别带权8,5,4和2。

构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别

为：

(a):WPL=8x3+5x3+2xl+4x2=49

(b):WPL=8x3+5x2+2x3+4xl=44

(c):WPL=8xl+5x2+2x3+4x3=36

其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

二、哈夫曼算法

1、构造哈夫曼树的方法：

①将给定的权值按照从小到大排列成{WI,W2,Wm}，并

且构造出树林F={T|,T2,...,Tm}o此时，其中的每棵树TiQwE

m）为左、右子树均为空的二叉树，二叉树的根结点的权值为Wi。

②把F中树根结点的权值最小的两棵二叉树1和T2合并为一棵新

的二叉树T（T的左子树为Ti,右子树为T2），并令T的根结点的权

值为Ti和T2的根结点的权值之和，然后将T按其根结点的权值大小

依次加入到树林F中。同时，从F中删去Ti和T2这两棵二叉树。

③重复步骤②，直到构造成一棵哈夫曼树。

【真题选解】

（例题•填空题）用6个权值分别为6、13、18、30、7和16的结

点构造一棵哈夫曼（Huffman）树，该树的带权路径长度为。

隐藏答案

【解析】用6个权值构造的过程如下图

90

构造的哈夫曼树的带权路径长度=(16+18+30)*2+13*3+

(6+7)*4=219

2、哈夫曼树的特点：

①在哈夫曼树中，权值越大的叶子离根结点越近。

②若有no个权值，需要进行no-1次合并，构造成为哈夫曼树。

③哈夫曼树没有度为1的结点。

④由no个权值构成的哈夫曼树，叶结点数为no,度为2的结点数

为no-1，结点总数为no+ri2=no+no-l=2no-l0

⑤给定一组权值，构造出的哈夫曼树的形态可能不唯一，但它们

的带权路径长度都一样。

三、哈夫曼编码

1、编码的概念

(1)编码和解码

数据压缩过程称为编码。即将文件中的每个字符均转换为一个唯一

的二进制位串。

数据解压过程称为解码。即将二进制位串转换为对应的字符。

(2)前缀码方案

对字符集进行编码时，要求字符集中任一字符的编码都不是其它字

符的编码的前缀，这种编码称为前缀(编)码。

【真题选解】

(例题•单选题)下述编码中不是前缀码的是()

A.(00,01,10,11)

B.(0,1,00,11)

C.(0,10,110,111)

D.(l,01,000,001)

隐藏答案

【答案】B

【解析】四个选项中除选项B外，其它三个选项的编码满足任一字

符的编码都不是其它字符的编码的前缀。

2、哈夫曼编码

设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率

作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。

【真题选解】

(例题•算法题)假设通信电文使用的字符集为{a,b,c,d,e,

f,g,h},各字符在电文中出现的频度分别为：7,26,2,28,13,

10,3,11,试为这8个字符设计哈夫曼编码。要求：

(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右

孩子结点的权值)；

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的

编码。

隐藏答案

【解析】先按照权值构造哈夫曼树，注意要满足题目的要求：树中

左孩子结点的权值不大于右孩子结点的权值。构造过程如下图：

2CgCgC

(1)(2)(3)(4)

到这里就很容易写出每个字符的哈夫曼编码了。

【答案】

(2)各字符的编码：a(0101),b(10),c(01000),d

(11),e(Oil),f(000)

g(01001)h(001)

注意：每个字符的编码都不是另外一个编码的前缀。

当前讲授

本章小结