数据结构第6章2解析.ppt

6.6.1 树的存储 一、 双亲表示法： 二、 孩子表示法： 孩子表示法示意图: 三、 孩子兄弟表示法 孩子兄弟表示法示意图： 树转换为二叉树示意图 森林转换为二叉树示意图 二叉树转换为森林的示意图 6.6.3 树和森林的遍历 二、树的遍历算法 三、森林的遍历 3、森林的后序遍历* 6.7 哈夫曼树及其应用 6.7.1 哈夫曼树 问题1： 二、哈夫曼树的构造 例如: 三、哈夫曼算法的实现 静态三叉链表结构定义 2、哈夫曼算法 例给定权值: {9,14 ,10 ,10, 12, 13, 9 ,11 } 二、哈夫曼编码: 对哈夫曼树中每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的值构成该叶子的哈夫曼编码。 结论一：哈夫曼编码是前缀码。 三、哈夫曼编码应用举例 四、哈夫曼编码算法 6.8 实例分析与实现 P153 6.9 算法总结 选择最小子树算法 带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度，通常记为WPL： WPL=?wi×li i=1 n 其中：n为叶子结点的个数；wi为第i个叶子的权值； li为第i个叶子结点的路径长度。 结点的权：给树中每个结点赋予一个具有某种 实际意义的数值，我们称该数值为这个结点的权。 例如下图所示的三棵二叉树 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 其带权路径长度分别为： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35 什么样的二叉树的路径长度PL最小？ 分析：二叉树中路径长度为0的结点只有1个； 路径长度 0 ，1，1，2，2，2，2，3，3，……3，4，4，... 结点数n n=1 n=2,3 n=4, 5 ,6 , 7 n=8... n=15 n=16… 可知：结点n对应的路径长度为? log2n ? 路径长度为1的结点至多只有2个； 路径长度为2的结点至多只有4个； …… 路径长度为K的结点至多只有2k个; 所以n个结点的二叉树其路径长度至少等于如下序列的前n项之和。 n k=1 ? ? log2k ? 所以n个结点二叉树的PL至少为前n项之和: 因为深度为h的完全二叉树的路径长度为： 20×0+21 × 1+22 × 2+…+ 2h × h = h k=1 ? ? log2k ? 所以完全二叉树具有树的路径长度为最小的性质，但不具有唯一性。 例如：下列不同形状的二叉树均具有最小的路径长度 A B C D E PL=0+1+1+2+2=6 A B D C E PL=0+1+1+2+2=6 A B C D E PL=0+1+1+2+2=6 故：深度为h的二叉树若前h-1层为满二叉树， 则具有最小的路径长度。 什么样的树的带权路径长度WPL最小？ 例如：给定一个权值序列{2, 4, 5, 7}，可构造多种二叉树的形态: 问题2： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(a) ＝ 36 WPL(b) ＝ 46 WPL(c)＝35 其带权路径长度分别为： 在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树，被称为“最优二叉树” 。 特征：在最优二叉树中没有度数为 1 的结点(可用反证法证明); 含 n个叶子结点的最优二叉树的总结点数为 2*n-1 (依据二叉树性质三)。 最优二叉树的构造方法最早由哈夫曼研究，所以又称为“哈夫曼树”。 (1) 初始化：根据给定的 n 个权值 {w1, w2, …, wn} ,构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树； 构造哈夫曼树的方法： 找最小树并构造新树：在 F 中选取其根结点的权值为最小的两棵二叉树, 分别作为左、右子树构造一棵新的二叉树, 并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； (2) 删除与插入：从F中删去这两棵树,并加入刚生成的新树； 重复 (2) 和 (3) ,直至 F 中只含一棵树为止。 (3) (4) 由此得到二叉树就是“最优二叉树”