数据结构 第六章 树和二叉树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 (赫夫曼树) 2.构造赫夫曼树算法 (1)根据给定的n个权值{w1,w2,……,wn}构成n棵二叉树的集合F={T1，T2，……,Tn}，其中每棵二叉树Ti只有一个权为wi的结点(根结点，无左右子树)。 (2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在集合F中删除先前所选取的两棵二叉树，并把新构成的二叉树加入到F中； (4)重复执行b，c两步，直到F中只剩下一棵二叉树。 6.4 赫夫曼树及其应用 二、构造赫夫曼树 6.4 赫夫曼树及其应用 a 9 b 4 c 5 d 2 a 9 c 5 b 4 d 2 6 a 9 c 5 b 4 d 2 6 11 a 9 c 5 b 4 d 2 6 11 20 例 W={9，4，5，2}，以此为权值构造一棵赫夫曼树 二、构造赫夫曼树 例 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 1.问题的提出 三、赫夫曼编码 6.4 赫夫曼树及其应用 由于电文中字符的出现频率不同，用等长编码会造成电文过长，从而导致传送时间过长。 思想：根据字符出现频率编码，使电文总长最短；同时要避免译码时的二义性，因此采用前缀编码（即任意一个字符的编码都不是另一个字符编码的前缀） 6.4 赫夫曼树及其应用 三、赫夫曼编码 2、赫夫曼编码的方法 (1)首先构造出赫夫曼树： (2) 设计赫夫曼编码：在有了赫夫曼树之后，将树中每个结点的左分支用“0”代表，右分支用“1”代表。则从根结点到叶结点之间，沿途路径上的分支组成的“0”或“1”代码串就是该叶子结点所代表的字符编码，称为赫夫曼编码。 赫夫曼编码为前缀编码。 例 字符集 D={C,A,S,T, ; } 字符出现频率 w={2,4,2,3,3} C S 3 3 6 4 2 2 4 8 14 T ; A T : 00 ; : 01 A : 10 C