数据结构第6章树和二叉树4赫夫曼树及其应用ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:树和森林第第6 6章章 树和二叉树树和二叉树树的根本概念二叉树遍历二叉树和线索二叉树赫夫曼树及其运用:v根本术语根本术语6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用路 径途径长度树的途径长度带权途径长度树的带权途径长度霍 夫 曼 树:v根本术语根本术语6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用DABCEFG途径：由一结点到另一结点间的分支所构成途径长度：途径上的分支数目ae的途径长度2树的途径长度：从树根到每一结点的途径

2、长度之和树长度 10:v根本术语根本术语6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用DABCEFG结点带权途径长度：结点到根的途径长度与结点上权的乘积树的带权途径长度：树中一切叶子结点的带权途径长度之和3798结点F的途径长度为2，其WPL=29=18niiilwWPL1其中n表示叶子结点的数目wi表示叶子结点ki的权值li表示根到ki之间的途径长度:v根本术语根本术语6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用赫夫曼树：带权途径长度最小的树, 又称最优二叉树树的带权途径长度如何计算？Weighted Path LengthniiilwWPL1:v例：有四个叶子结点

3、例：有四个叶子结点a,b,c,d，分别带权为，分别带权为7, 5, 2, 4，由它们构成三棵不同的二叉树，由它们构成三棵不同的二叉树6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用abdc7524cdab2457bdac7524WPL=36WPL=46WPL= 35Huffman树树:v构造最优树构造最优树(赫夫曼算法赫夫曼算法)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用(1) 由给定的 n 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩展二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩展二叉树 Ti 只需一个带有权值 wi 的

4、根结点，其左、右子树均为空。 (2) 反复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩展二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树参与 F。:第一步：abcd9254第二步：第三步：第四步：abc9654d2abc9654d211abc9654d21120:第一步：5629第二步：第三步：第四步：7562977562977135629771316第五步：562977131629:第一步：5629第二步：第三步：第四步：75629775629779716

5、第五步：57269716132913562713:第一步：56297572697161329562977131629:v断定树断定树 (赫夫曼树的运用之一赫夫曼树的运用之一)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用分数0596069707980899099比例0.050.150.40.30.1a60 a70 a80 a90 不及格 中等 良好 优秀 及格YNYNYNYN输入输入1000010000个数个数据，那么需进据，那么需进展展3150031500次比较次比较。:v断定树断定树 (赫夫曼树的运用之一赫夫曼树的运用之一)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其

6、运用分数0596069707980899099比例0.050.150.40.30.170a80 a60 及格中等良好80a90 60a70 不及格优秀YNYYYNNN以比例数为权构造一棵哈夫曼树，如(b)判别树所示。再将每一比较框的两次比较改为一次:v断定树断定树 (赫夫曼树的运用之一赫夫曼树的运用之一)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用分数0596069707980899099比例0.050.150.40.30.1不及格Ya90 a80 a70 a60 优秀中等及格良好YNNNYYY输入输入1000010000个个数据，仅需数据，仅需进展进展2200022000次次比

7、较。比较。:v赫夫曼编码赫夫曼编码(赫夫曼树的运用之二赫夫曼树的运用之二)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用1二进制编码 通讯中，可以采用0、1的不同陈列来表示不同的字符，称为二进制编码。 发送端需求将电文中的字符序列转换成二进制的0、1序列，即编码； 接受端需求把接受的0、1序列转换成对应的字符序列，即译码。 :v赫夫曼编码赫夫曼编码(赫夫曼树的运用之二赫夫曼树的运用之二)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用等长编码不等长编码A B C D00 01 10 11发送：A B A C C C C D A B00 01 00 10 10 10 10

8、11 00 01 让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，缩短传送电文的总长度A B C D 1 10 0 01发送：A B A C C C C D A B 1 10 1 0 0 0 0 01 1 10?无法译码！为此引入前缀编码的概念无法译码！为此引入前缀编码的概念:v赫夫曼编码赫夫曼编码(赫夫曼树的运用之二赫夫曼树的运用之二)6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用2前缀编码 假设对某一字符集进展不等长编码，那么要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。:v利用二叉树设计二进制的前缀编码利用二叉树设计二

9、进制的前缀编码6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用01abcd1100 假设有一棵如左图所示的二叉树，四个叶结点分别表示A、B、C、D四个字符，且商定左分支表示字符0 ，右分支表示字符1，那么可以从根结点到叶子结点的途径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。 :v赫夫曼编码赫夫曼编码6.5 赫夫曼赫夫曼(Huffman)树及其运用树及其运用 设计电文总长最短的二进制前缀编码即： 以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称赫夫曼编码。 :v赫夫曼编码赫夫曼编码6.5 赫夫曼赫夫曼(Huffma

10、n)树及其运用树及其运用例：设通讯誉的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，试为这8个字母设计哈夫曼编码。:0.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.070.070.190.190.020.020.060.060.3

11、20.320.030.030.210.210.100.100.050.050.110.110.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.17:0.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.

12、050.110.110.170.170.280.280.400.40:0.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400.600.600.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400.600.601.001.0000000001111111:0.070.070.190.190.

13、020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400.600.601.001.0000000001111111a, b, c, d, e, f, g, h 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 abcdefgh:0.070.070.190.190.020.020.060.060.320.320.030.030.210.210.100.100.050.050.110.110.170.170.280.280.400.400

14、.600.601.001.0000000001111111a, b, c, d, e, f, g, h 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 abcdefgha = 1010a = 1010b = 00b = 00c = 10000c = 10000d = 1001d = 1001e = 11e = 11f = 10001f = 10001g = 01g = 01h = 1011h = 1011:对应的哈夫曼编码左对应的哈夫曼编码左0右右1符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0