chap6树和二叉树.ppt

路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。 树的路径长度是各叶结点(外结点)到根结点的路径长度之。 相关概念 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 1 树的外部路径长度 EPL = 3*1+2*3 = 9 树的外部路径长度 EPL = 1*1+2*1+3*1+4*1 = 10 带权路径长度 (Weighted Path Length, WPL) 二叉树的带权 (外部) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。 2 2 2 4 4 4 5 5 5 7 7 7 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 带权路径 长度达到最小 赫夫曼树（最优二叉树） 带权路径长度达到最小的二叉树即为赫夫曼树。 在赫夫曼树中，权值大的结点离根最近。 (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 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 上例存储结构 初 态 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 -1 -1 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 p1 p2 4 4 2 3 i 过 程 5 2 7 4 6 11 Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 3 11 -1 -1