③结点的带权路径长度： 某结点的路径长度与该结点上的权值的乘积称为该结
点的带权路径长度。
④ 树的带权路径长度(WPL)：
树中所有叶子结点的带权路径长度之和称为树的带权
路径长度。
编辑ppt
7
1二.哈、夫树哈曼的夫树带的曼权有树路关径及概长其念度W应为P用树树L：=的的2带带*权权4+路路3径径*长长7+度度3为为*：：5+ 实W例PL：=已1*知7某+2二*叉5+1W树*3P的2*L=2四=+42个6*叶7+子2结*5点+2a,*b2,c+,d 分3*别4带=3权57，5，2，2*4，4=则3可6 构造出有如下几 种不同形式的二叉树：
设这4个不同的字符为A，B，C，D，则可进 行等长编码如下：
编辑ppt
17
二、哈夫曼树及其应用
3.哈夫曼编码
①等长编码：
设这4个不同的字符为A，B，C，D，则可进 行等长编码如下：
编辑ppt
18
二、哈夫曼树及其应用
3.哈夫曼编码
①等长编码： 设这4个不同的字符为A，B，C，D，则可进
行等长编码如下：
步骤3:判断F中是否只有唯一的一棵二叉树。若是，则求
解过程结束；否则，转步骤编及其应用
2.哈夫曼树的求解过程
③实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。
15
40 a
30 b
5 c 编辑ppt
10d
15e 12
学生
30%的 学生
编辑ppt
5
思考：如何找到一棵最优的判断树使得编写 出来的程序的运行时间是最高效的？
编辑ppt
6
二、哈夫曼树及其应用
1.哈夫曼树的有关概念
①结点的路径长度： 从根结点沿某条路径到某结点途中所经历的边的条数
称为该结点的路径长度。
② 树的路径长度： 从根结点到每一个叶子结点的路径长度之和。
二、哈夫曼树及其应用
2.哈夫曼树的求解过程
③实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。
15
40 a
30 b
5 c 编辑ppt
10 d
15 e 13
二、哈夫曼树及其应用
2.哈夫曼树的求解过程
③实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。
打印 "bad"
a<70
yes
no
打印 "pass"
a<80
yes
no
5%的 学生
打印
a<90
"general yes
" 15%的 学生 40%的
学生 编辑ppt
打印 "good" 30%的 学生
no
打印 1学0生""% ex的cell4ent
学生成绩数据分布情况表
共做220次
分数
0~59 60~69 70~79 80~89 9比0~较100
编辑ppt
9
二、哈夫曼树及其应用
2.哈夫曼树的求解过程
①问题：
造一已棵知最优n个二叶叉子树的。权值为{w1,w2,...wn}，构
编辑ppt
10
二、哈夫曼树及其应用
2.哈夫曼树的求解过程
②方法：
步骤1:构造一个具有n棵二叉树的森林 F={T1,T2,......,Tn}，其中Ti是只有一个根结点且根结 点的权值为wi的二叉树。 步骤2:在F中选取两棵其根结点的权值最小的二叉树，从 F中删除这两棵树，并以这两棵二叉树为左右子树构造一 棵新的二叉树添加到F中，该新的二叉树的根结点的权值 为其左右孩子二叉树的根结点的权值之和。
*问题：现在要编写程序依次根据每个学生的成绩 打印出该学生的成绩等级。
编辑ppt
3
学生成绩数据分布情况共表 做315次比
分数
0~59 60~69 70~79 80~89 9较0~100
学生比例数 0.05 0.15 0.40 0.30 0.10
读取一个学生成绩→a
方法1：
a<60
yes
no
循环一百次
2.哈夫曼树的求解过程
100
40 a 60
30 b
30
15
15 e
5 c 编辑ppt
10 d
16
二、哈夫曼树及其应用
3.哈夫曼编码
①等长编码： 以英文字符编码为例，一般英文字符编码是采
用7位二进制数编码（ASCII码）。7位二进制数 可以为27个不同的英文字符编码。
下面为讨论问题简单起见，假设被编码的字符 集中只有4个（即22个）不同字符，故只要两位二 进制数即可完成编码。
A: 00 B: 01 C: 10 D: 11
则对于电文“ABACCDA”的二进制电码为： 00010010101100 总长为14位
译码时，两位一分进行译码，可唯一得到电文： ABACCDA 。
编辑ppt
19
二、哈夫曼树及其应用
3.哈夫曼编码
思考：如何解 决这一问题？
②压缩编码：
问题的关键在于编码
学生比例数 0.05 0.读15取一个0.4学0生成0绩.30 0.10
方法2：
→a
循环一百次
a<80
yes
no
a<70
yes
no
a<60
打印
yes
no "general
打印 "bad"
5%的
打印 " "pass"
15%的
40%的 学生
学生
学生
a<90
yes
no
打印 “good "
打印 "excellent " 10%的
树的应用
编辑ppt
1
二叉树遍历的应用
1.查找数据元素 2. 求二叉树的高度 3. 求叶子结点数
编辑ppt
2
一、问题的提出(判断树)
设有100个学生某门课程的考试成绩的分布如下表 所示：
学生成绩数据分布情况表
分数
0~59 60~69 70~79 80~89 90~100
学生比例数 0.05 0.15 0.40 0.30 0.10
c 2 7a
4
7
5
24
d
a
bc
d
75
a
b
5 b 2 c 4d
编辑ppt
8
二、哈夫曼树及其应用
⑤哈夫曼树的定义：
设有n个叶子结点的二叉树，其第i个 叶叶子子结结点点n 的的路权径值长为度wi(为i=l1i ,,2则,3使,...n),且第i个 WPL=∑i=1wi*li最小的二叉树称为“最优 二叉树”或称为“哈夫曼树”。
30
40 a
30 b
15
15e
5 c 编辑ppt
10d
14
二、哈夫曼树及其应用
2.哈夫曼树的求解过程
③实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。
60
40 a
30 b
30
15
15 e
5 c 编辑ppt
10d
15
二、哈夫曼树及其应用
例如：对于刚才的4个字符的是编否码为问无题前，缀可编以码按。如