第02章算法与数据结构-04树和二叉树1精读.ppt

树的后根次序遍历: 当树非空时 依次后根遍历根的各棵 子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 A B C E D G F 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： HBDF EKCG A EKCG A B H DF KCG EKCG A B H DF EKCG A B H F D E A B H F D E A B H F D C K G 如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。 6 1 2 3 4 5 7 8 9 6 1 2 3 7 5 8 4 9 固定前序排列,选择所有可能的中序排列,可以构造多少种不同的二叉树？ 例如, 有 3 个数据 { 1, 2, 3 }，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321 ， 231， 213， 132，123. 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 具有n个结点不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同。 有0个, 1个, 2个, 3个结点的不同二叉树如下 b0 =1 b1 =1 b2 =2 b3 =5 b4 =14 计算具有 n 个结点的不同二叉树的棵数 最终结果： bi bn-i-1 1 霍夫曼树 (Huffman Tree) 路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。 树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和 EPL。 树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和 IPL。 树的路径长度 PL = EPL + IPL 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 树的外部路径长度 EPL = 3*1+2*3 = 9 树的外部路径长度 EPL = 1*1+2*1+3*1+4*1 = 10 1 带权路径长度 (Weighted Path Length, WPL) 二叉树的带权 (外部) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。 WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 2 2 2 4 4 4 5 5 5 7 7 7 带权(外部)路径 长度达到最小 霍夫曼树 带权路径长度达到最小的二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 (1) 由给定的 n 个权值 {w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 }，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。 霍夫曼算法 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 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 举例霍夫曼树的构造过程 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