哈夫曼树.ppt

n
w i pi
最小，其中
i 1
Wi是第i个字符的使用频度，而Pi是第i个字符的编码长度， 这正是度量报文的平均长度的式子。
2020/3/5
21
例2：要传输的电文是{CAS；CAT；SAT；AT}
要传输的字符集是 D={C，A，S，T， ；}
每个字符出现的频率是W={ 2，4， 2，3， 3 }
PL=0+1+1+2+2=6
2020/3/5
9
问题2：什么样的带权树路径长度最小？
例如：给定一个权值序列{2,3,4,7}，可构造的多种 二叉树的形态。
2
3
4
7
2 34 7
(a) WPL=2×2＋2×3+2×4+2×7=32 (b) WPL=1×2＋2×3+3×4+3×7=41
2020/3/5
7
4
3
2
(c) WPL=1×7＋2×4+3×3+3×2=30
10
哈夫曼树的构造
例：给定权值{7，5，2，4}，构造哈夫曼树。
6
方法： 75 2 4
75
（1）a 初始b化：由c 原始d数据生成森林a ； b c
d
（次2小）的找二最叉小(树a树) 作：为在左森右林子中树选构取造两一棵棵根新结的点二权叉值树最(，小b)其的根和
A）先序遍历
B）中序遍历
C）后序遍历
D）从根开始进行层次遍历
2、某二叉树的先序序列和后序序列正好相反，则该二叉
树一定是（ B ）的二叉树。
A）空或只有一个结点
B）高度等于其结点数
C）任一结点无左孩子
D）任一结点无右孩子
3、有n个叶子结点的哈夫曼树的结点总数为（ D ）
A）不确定
B）2n
C）2n＋1
D）2n－1
0
1
2
0
1
2
3 45 6
3
4
7
PL = 0＋1＋1＋2＋2＋2＋2＋3 ＝13
5 67
PL = 0＋1＋1＋2＋2＋3＋3＋3 ＝15
结点的权： 给树的每个结点赋予的一个具有某种实际意义的实数。 结点的带权路径长度：
从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：
树中叶子结点带权路径长度之和。
a<60
(b) (c)
哈夫曼树的应用
2、哈夫曼编码
(1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的 前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编 码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去 掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。
4
注（意3：）编从码叶的子总结长点度开恰始好，为顺哈着夫双曼亲树反的推T带上权去路，径; 直长到。根结A点，0 路 1
径上的‘0’或‘1’连接的序列就是结点对应的字符的二进2 制 2
编码的逆序。
CS
构造二叉树
例：已知结点的先序遍历序列和中序遍历序列分别为：
先序遍历序列：18，14，7，3，11，22，35，27
分数 比例
0—59 60—69 70—79 80—89 90—99
0.05 0.15 0.4
0.3
0.10
以比例数为权构造一棵哈夫曼树， 如（b)判输断入树100所00示个。
数据，仅需进
行22000次比
再将每一比较较。框的两次比较改为一 次，可得到（c)判定树。
70≤a < 80 80≤a<90 60≤a<70
4、除根结点外，树上每个结点（ B ）。
A）可有任意多个孩子、任意多个双亲 B）可有任意多个孩子、一个双亲 C）可有一个孩子、任意多个双亲 D）可有一个孩子、一个双亲
5、树用双亲链表表示，则（ C ）。
A）可容易地实现求双亲及子孙的运算 B）求双亲及子孙的运算均较困难 C）可容易地实现求双亲运算，但求子孙运算较困难 D）可容易地实现求子孙运算，但求双亲运算较困难
带权路径长度达到最小的扩充二叉树即为
哈夫曼树。哈夫曼树中，权值大的结点离根最
近。 2020/3/5
7
问题1：什么样的二叉树的路径长度PL最小？ 一棵二叉树的路径长度为0结点至多只有1个（根）；
路径长度为1结点至多只有2个（两个孩子）；
路径长度为2结点至多只有4个；
依此类推：路径长度为K结点至多只有2k个，所以n个结点的 二叉树其路径长度至少等于如下序列的前n项之和。
在解决某些判定问题时，利用哈夫曼树可以得到最 佳判定算法。
例1 将学生百分成绩按分数段分级的程序。
若学生成绩分布是均匀的，可用图（a)二叉树结构 来实现。
输入10000个 数据，则需进 行28000次比
较。
a<60
Y
N
不及格
a<70
Y
N
及格
a<80
Y
N
中等
a<90
Y
N
(a)
良好
优秀
学生成绩分布不是均匀的情况：
加权路径长度最小的二叉树就 是哈夫曼树。
公式：
n
WPL WiLi i1
a
bc
d
7
52
4
WPL=7*2+5*2+2*2+4*2=36
c2 4d
a
b
7
5
WPL=7*3+5*3+2*1+4*2=46
7a
5b
2c
d4
WPL=7*1+5*2+2*3+4*3=35
具有不同带权路径长度的二叉树
哈夫曼树
结点的权值为左右子树根结点权值之1和8 。规定左子树根
7结点的权值小于右子树根结点的权值。 （a 3）删除与加1入1 ：将新的二7叉树a加入到森林F1中1 ，去除 原两棵权值最小的树； （4）5判b 断：重复2、3步骤，直至F中只5b剩一棵树为止6。
c
d
c
d
(c)
(d)
2
4
哈夫曼树的应用 （1）判定树
(2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分 支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分 别构成一个二进制串，该二进制串就称为哈夫曼编码。
2020/3/5
19
定理6-1 哈夫曼编码是前缀码。
证明：哈夫曼编码是根到叶子路径上的边的编码的序列， 也就是等价边序列，而由树的特点知，若路径A是另一条路 经B的最左部分，则B经过了A，因此，A的终点不是叶子。 而哈夫曼编码都对应终点为叶子的路径，所以，任一哈夫 曼码都不会与任意其他哈夫曼编码的前部分完全重叠，因 此哈夫曼编码是前缀码。
路径长度 0 ，1 ， 1 ，2， 2， 2， 2，3， 3，3，3，3，3，3，3，4，4，...
结点数k k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8
...
k=15
由此可知，结点n对应的路径长度为 log2n ，所以
前n项之和为:
h
log2k
k=1
2020/3/58来自完全二叉树的路径长度为：
h
20×0+21 × 1+22 × 2+…+ 2h × h= log2k k=1
h为树的深度，其路径长度可达到最小，所以完全 二叉树具有最小路径长度的性质，但不具有唯一性。
例如：下列不同形状的二叉树均具有最小的路径长度
A
A
B
C
B
C
DE
D
E
PL=0+1+1+2+2=6
哈夫曼树及其应用
1.路径
2.路径长度
6.树的带权 路径长度
什么是哈夫曼树
3.树的路径长度
5.结点带权 路径长度
4.结点的权
2020/3/5
1
哈夫曼树（最优树）及其应用
路径长度的概念
路径：从一个结点到另一个结点之间的分支 序列
结点之间的路径长度：从一个结点到另一个 结点之间的分支数目
树的路径长度（用PL表示）：从树的根到每 一个结点的路径长度之和
中序遍历序列：3，7，11，14，18，22，27，35 18
14
22
7
3
11
35 27
给定一棵二叉树的先序序列和中序序列，可唯 一确定一棵二叉树
1、对二叉树从1开始编号，要求每个结点的编号大于其左 右孩子的编号，同一个结点的左右孩子中，其左孩子的编
号小于其右孩子的编号，则可采用（ C ）实现编号。
各字符编码是 T ； A C S
00 01 10 110 111 上方述法电：文编码：
14
0
1
110（1011）11用01{1120，1040，0021，11131，003001}1作00为0 叶子结点6 的权值生成一8棵哈 夫曼树，并将对应权值wi的叶子结点0注明对应1 的字符；0 1
（2）约定左分支表示字符“0”，右分3支表示3字符‘1’4
2020/3/5
20
定理6-2 哈夫曼编码是最优前缀码。 即对于n个字符，分别 以它们的使用频度为叶子权，构造哈夫曼树，则该树对应的 哈夫曼编码，能使各种报文（由这n种字符构成的文本）对 应的二进制串的平均长度最短。
证明：由于哈夫曼编码对应叶权为各字符使用频度的哈夫曼
树，因此，该树为带权长度最小的树，即
a
bc
d
7
52
4
WPL=7*2+5*2+2*2+4*2=36