2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念: 从一个结点到另一个结点之间的分支数 目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的 路径长度之和。 2/22 202l/2/
2021/2/22 2 2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念： 从一个结点到另一个结点之间的分支数 目称为这对结点之间的路径长度。 树的路径长度是从树的根到每一结点的 路径长度之和
树的路径长度用PL表示。 4 PL=0+1+1+2+2+2+2=10 2/22 202l/2/
2021/2/22 3 1 2 4 5 3 6 7 PL=0+1+1+2+2+2+2=10 树的路径长度用PL表示
树的路径长度用PL表示。 C 4 PL=0+1+1+2+2+2+2=10 PL=0+1+1+2+2+3+3=12 2/22 202l/2/
2021/2/22 4 1 2 4 5 3 6 7 PL=0+1+1+2+2+2+2=10 1 2 4 5 C 6 7 PL=0+1+1+2+2+3+3=12 树的路径长度用PL表示
结点带权的路径长度: 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度: 树中叶子结点带权路径长度之和。 ⑤ 7 52 4 WPL=7*2+5*2+2*2+4*2=36 2/22 202l/2/
2021/2/22 5 结点带权的路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中叶子结点带权路径长度之和。 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36
树的带权路径长度记作: WPL= ∑ KLK k=1 其中:W为树中每个叶子结点的权; L为每个叶子结点到根的路径长度。 7 52 wPL=7*2+5*2+2*2+4*2=36 wPL最小的二叉树就称作最优二叉树或哈夫曼树。 2021/2/22
2021/2/22 6 树的带权路径长度记作： 其中：Wk为树中每个叶子结点的权； Lk为每个叶子结点到根的路径长度。 = = n k WPL WKLK 1 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 WPL最小的二叉树就称作最优二叉树或哈夫曼树
哈夫曼树(最优树) 加权路径长度最小的二叉树就 是哈夫曼树。 公式: WPL=∑WkLK 7 52 4 WPL=7*2+5*2+2*2+4*2=36 c2 7 a 4(d 5(b 2 d)4 7 5 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35 2/22 202l/2/
2021/2/22 7 a b c d 7 5 2 4 WPL=7*2+5*2+2*2+4*2=36 d c a b 2 4 7 5 WPL=7*3+5*3+2*1+4*2=46 a b c d 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 哈夫曼树 （最优树） 加权路径长度最小的二叉树就 是哈夫曼树。 公式： = = n k WPL WKLK 1
2、哈夫曼树的构造 例:给定权值{7,5,2,4},构造哈夫曼树。 6 方法 5 52 C d L)属始数据生成森林 (2)在森林中选取两棵根结点权值最小的和次小的二 叉树作为君子树构造一棵新的二叉树,其根结点的 权值为左右子树根结点权值之和。规是左子树根结点 的权值小于右子树根结点的权值。 3将新树加入到率林,去除原两棘权值 最小的树; (4)复2、,直至F中只剩一树为止。6 注意:参看中P5的例子。 d C (d 2 2/22 202l/2/
2021/2/22 8 6 7 5 c d (b) 11 b 5 7 c d (c) 18 7 a 11 c d b 5 6 (d) 2 4 a b c d 7 5 2 4 (a) 2、哈夫曼树的构造 例：给定权值{7，5，2，4}，构造哈夫曼树。 方法： （1）由原始数据生成森林； (2) 在森林中选取两棵根结点权值最小的和次小的二 叉树作为左右子树构造一棵新的二叉树，其根结点的 权值为左右子树根结点权值之和。规定左子树根结点 的权值小于右子树根结点的权值。 （3）将新的二叉树加入到森林F中，去除原两棵权值 最小的树； （4）重复2、3步骤，直至F中只剩一棵树为止。 注意：参看书中P53的例子
3、哈夫曼树的应用 (1)判定树 在解决某些判定问题时,利用哈夫曼树可以得到最 佳判定算法 例1将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的,可用图(a)二叉树结构 来实现。 N O「不及格 a<70 输入1000个 及格 <80 数据,则需进 行31500次比 中等 a<90 N 较。 良好 优秀 a 2/22 202l/2/
2021/2/22 9 3、哈夫曼树的应用 （1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最 佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构 来实现。 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N Y N Y N Y N (a) 输入10000个 数据，则需进 行31500次比 较
学生成绩分布不是均匀的情况: 10 分数05960670-7980899099 比例005050403010 70<a≤80 以比例 棵哈夫曼树, 如 输入10000个 中等 80≤a<90 数据,仅需进 行22000次比 良好 60<a<70 再将 较。 次比较改为 次,可得到判定 a<60 及格 a<80 不及格优秀 a<70 a<60 中等良好 优秀 (b) 不及格 及格 2/22 202l/2/
2021/2/22 10 分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.10 70≤a≤ 80 a<60 80≤a<90 60≤a<70 (b) (c) 学生成绩分布不是均匀的情况： 以比例数为权构造一棵哈夫曼树， 如（b)判断树所示。 再将每一比较框的两次比较改为一 次，可得到（c)判定树。 输入10000个 数据，仅需进 行22000次比 较
ll (2)哈夫曼编码-利用哈夫曼树构造通讯中电文编码(前缀码) 例2:要传输的电文是{CAS;CAT;SAT;AT} 要传输的字符集是D={C,A,S,T,;} 每个字符出现的频率是W={2,4,2,3,3} 各字符编码是;ACS 方法: 000110110111 止述电芽编码:4,2,3,3}作为叶子结原的权值生成繅哈 带:础密督倍点注明对点的字符 (2)约定左分支表示字符“0”,右支表录字符 3)-研子结点并始顺着双亲友攉社妻裡到根绪点路 径上的0或1连接的序列就是结点对应的字符的士制2 编码的逆序。 C 0212722
2021/2/22 11 14 6 8 3 3 4 4 2 2 0 0 0 0 1 1 1 1 T ; A C S 各字符编码是 T ； A C S 00 01 10 110 111 上述电文编码： 11010111011101000011111000011000 方法： （1）用{ 2，4， 2，3， 3 }作为叶子结点的权值生成一棵哈 夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0” ，右分支表示字符‘1’ （3）从叶子结点开始，顺着双亲反推上去，直到根结点，路 径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制 编码的逆序。 （2）哈夫曼编码-----利用哈夫曼树构造通讯中电文编码（前缀码） 例2：要传输的电文是{CAS；CAT；SAT；AT} 要传输的字符集是 D={C，A，S，T， ；} 每个字符出现的频率是W={ 2，4， 2，3， 3 } 注意：编码的总长度恰好为哈夫曼树的带权路径长