数据结构 第六章 节 树和二叉树6.4.pptVIP

6.4 赫夫曼(Huffman)树及其应用 一、赫夫曼树的概念 二、构造赫夫曼树 三、赫夫曼编码 一、赫夫曼树的概念 6.4 赫夫曼树及其应用 有关赫夫曼树的术语 1.结点的路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 2.路径的长度：路径上的分支个数。 3.树的路径长度：从根结点到每一结点的路径长度之和。 4.结点带权路径长度：从该结点到根结点之间的路径长度与结点上权的乘积。 权——将树中结点赋上一个有意义的实数，如某个字符出现的次数，从根结点到该结点的距离、花费的时间等。 5.树的带权路径长度(WPL) ：所有叶子结点的带权路径长度之和为树的带权路径长度。 一、赫夫曼树的概念 6.4 赫夫曼树及其应用 6.赫夫曼树(最优二叉树)：假设有n个权值{w1,w2,……,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点的权值为wi，其中带权路径长度最小的二叉树称为赫夫曼树。 例：权值分别为9，4，5，2，构造有4个叶子结点的二叉树 a b c d 9 4 5 2 WPL=9*2+4*2+5*2+2*2=40 d c a b 5 2 9 4 WPL=9*3+4*3+5*1+2*2=48 a c b d 9 5 4 2 WPL=9*1+5*2+4*3+2*3=37 (赫夫曼树) 1.赫夫曼树的应用： 二、构造赫夫曼树 6.4 赫夫曼树及其应用 解决判定问题时，得到最佳判定树。 等级 分数段 比例 A B C D E 0 ~ 59 60 ~ 69 70 ~ 79 80 ~ 89 90 ~ 100 0.05 0.15 0.40 0.30 0.10 例如:编制一个将百分制转换成五级分制的程序。 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A a80 a70 a60 a90 E Y N D Y N C Y N B Y N A WPL1=5*1+15*2+40*3+(30+10)*4=315 WPL2=(40+30+10)*2+(5+15)* 3 =220 (赫夫曼树) 例 w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 8 7 15 14 29 23 3 5 8 11 11 3 5 8 19 14 29 23 8 7 15 11 3 5 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42 29 14 8 7 15 29 58 11 3 5 8 19 23 42 29 14 8 7 15 29 58 100 * *