数据结构课件第6章树和二叉树1章节幻灯片.ppt

5.5 求等价类过程实例(续) 集合S = {1, 2, 3, 4, 5, 6, 7, 8, 9} 等价关系集为{(1,2), (3,4), (5,6), (7,8), (1,3), (5,7), (1,9)} 1 2 3 4 5 6 7 8 9 3 4 2 1 9 6 5 7 8 6. 树的计数 6.1 二叉树的相似和等价 6.2 二叉树的计数 6.3 由前序序列和中序序列构造二叉树 6.4 普通树的计数 6.1 二叉树的相似和等价 两棵二叉树相似是指：它们或者为空树；或者均不为空树，且它们的左右子树分别相似。 两棵二叉树等价是指：它们不仅相似，而且对应点上的元素均相同。 6.2 二叉树的计数 b0 =1 b1 =1 b2 =2 b3 =5 b4 =14 6.2 二叉树的计数(续1) b(0) = 1 b(1) = 1 b(2) = 2 b(3) = 5 b(4) = 14 根据相似的递归定义得到： 结论： 6.2 二叉树的计数(续2) 思考题：给定结点总数n和二叉树“最左边” ( leftmost)结点的深度。求这样的二叉树共有多少棵？ 6.3 由前序序列和中序序列构造二叉树 前序序列 {ABHFDECKG} 和中序序列 {HBDFAEKCG} HBDF EKCG A EKCG A B H DF EKCG A B H F D KCG E A B H F D E A B H F D C K G 固定前序序列，有几个中序序列就有几棵不同的二叉树 6.4 普通树的计数 普通树的计数可以借助于二叉树的计数实现 具有n+1个结点的普通树的数目和具有n个点的二叉树的数目相同 树和二叉树建立一一对应关系：把树进行左孩子-右兄弟存储表示，去掉根结点，就得到对应的二叉树；反之也容易实现 7. 霍夫曼树 7.1 赫夫曼树的相关定义 7.2 赫夫曼树的构造过程 7.3 赫夫曼树的构造过程举例 7.4 前缀编码 7.5 赫夫曼编码 7.6 赫夫曼解码 7.1 赫夫曼树的相关定义 A B C D E F G 路径长度 树的路径长度 树的带权路径长度WPL 最优二叉树（赫夫曼树） a b c d c a b d a b c d a 7 b 5 c 2 d 4 36 46 35 7.2 赫夫曼树的构造过程 (1) 由给定的n个权值 {w0, w1, w2, …, wn-1}，构造具有n棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 }，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 7.3 赫夫曼树的构造过程举例 F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 初始 合并{2} {4} 7 5 2 4 6 F : {18} 11 7 5 2 4 6 合并{5} {6} 5 合并{7} {11} 2 7 4 6 11 18 7.3 赫夫曼树的构造过程举例(存储结构演示1) 5 2 7 4 Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 初态 7.3 赫夫曼树的构造过程举例(存储结构演示2) 5 2 7 4 6 Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1