数据结构第6章d.ppt

第6章 树和二叉树（ Tree Binary Tree ） 提前介绍：二叉树的应用 6.5 Huffman树及其应用 Huffman树简介： 构造霍夫曼树的基本思想： 构造Huffman树的步骤： 操作要点2：按左0右1对Huffman树的所有分支编号！ 例2（严题集6.26③）：假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？ 为清晰起见，重新排序为:w={2, 3, 6, 7, 10, 19, 21, 32} 若按二进制编码： 例3：设字符集为26个英文字母，其出现频度如下表所示。 小结：哈夫曼树及其应用 怎样生成Huffman树？ 步骤如下： 对Huffman编码器程序的解释： 二叉树小结 本章小结 * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 平衡树—— 排序树—— 字典树—— 判定树—— 带权树—— 最优树—— 特点：左右子树深度差 ≤1 特点：“左小右大” 由字符串构成的二叉树排序树 例如，12个球只称3次分出轻重 特点：路径长度带权值 带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。 路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 霍 夫 曼 树： 1、最优二叉树（霍夫曼树） 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和。 结点到根的路径长度与结点上权的乘积 预备知识：若干术语 d e b a c f g 树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 a→e的路径长度＝ 树长度＝ 2 10 树的带权路径长度如何计算？ WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 经典之例： WPL= WPL=46 WPL= 35 哈夫曼树则是：WPL 最小的树。 Huffman树 Weighted Path Length WPL=7×2+5×2+2 ×2+4 ×2=36 36 在所有含有n个叶子结点，并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树” 思考： Huffman树有什么作用，研究它有什么意义？ 在解某些判定问题时，利用Huffman树可以得到最佳判定算法。 例如：编制一个将百分制转换成五级分制的程序 if(a60) b=“bad”; else if (a70) b=“pass”; else if(a80) b=“general”; else if(a90) b=“good”; else b=“excellent”; 这个判定过程如图A判定树来表示 a60 不及格 a70 a80 a90 及格 中等 良好 优秀 Y Y Y Y N N N N 图A 分析该算法的质量问题：即操作所需时间，如有10000个数据输入，则需进行多少次比较？又如在实际生活中，学生的成绩在5个等级上的分布是不均匀的，假设分布规律如下： 0.10 0.30 0.40 0.15 0.05 比例数 90—100 80—89 70—79 60—69 0—59 分数 则80%以上的数据需进行3次或3次以上的比较才能得出结果。 假定以5、15、40、30和10为权构造一棵有5个叶子结点的赫夫曼树，即可得到如图B所示的判定过程 70≤a80 中等 80≤ a90 60≤ a70 良好 及格 不及格 优秀 Y Y Y Y N N N N a60 图B 由于判定框都有两次比较，将这两次比较分开，则判定树如图C： a80 中等 a90 a60 良好 及格 不及格 优秀 Y Y Y Y N N N N a70 图C 那么，怎么就画出这个判定树了，怎么就设计出质量好的算法了？方法： ————构造赫夫曼树 根据这些图都可以设计出算法并编写出程序——数据结构作用的体现！ (1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下