数据结构课件1-11全书讲第6讲树与二叉树幻灯片.ppt

B C D E F G H I J K 1．森林中第一棵树的根结点 2．森林中第一棵树的子树森林 3．森林中其它树构成的森林 森林由三部分构成 森林转化成二叉树 的规则 ? 若F为空，即n = 0，则 对应的二叉树B为空二叉树 ? 若F不空，则 对应二叉树B的根root(B)是F中第 一棵树T1的根root(T1)，其左子树为 B(T11, T12, …, T1m)，其中，T11, T12, …, T1m是root(T1)的子树；其右子 树为B(T2, T3, …, Tn)，其中，T2, T3, …, Tn是除T1外其它树构成的森林 二叉树转换为森林 的规则 ? 如果B为空，则对应的森林F也为空 ? 如果B非空，则 F中第一棵树T1的根为root；T1的根 的子树森林(T11, T12, …, T1m ) 是由 root的左子树LB转换而来，F 除了T1 之外其余的树组成的森林(T2, T3, …, Tn )是由root的右子树RB转换而成的 森林 森林与二叉树的转换 树的先根遍历 若树为空，则空操作，结束；否则按如下规则遍历： （1）访问根结点； （2）分别先根遍历根的各棵子树。 树　的　遍　历 树的后根遍历 若树为空，则空操作，结束；否则按如下规则遍历： （1）分别后根遍历根的各棵子树； （2）访问根结点。 A B C D E F G H I J K 先根次序遍历 A B E F C D G H I J K 后根次序遍历 E F B C I J K H G D A 森林的先根遍历 若森林F为空, 返回 否则: ?访问F的第一棵树的根结点 ?先根次序遍历第一棵树的子树森林 ?先根次序遍历其它树组成的森林 森 林　的　遍　历 森林的中根遍历 若森林F为空，返回 否则: ?中根次序遍历第一棵树的子树森林 ?访问F的第一棵树的根结点 ?中根次序遍历其它树组成的森林 哈 夫 曼 树 (Huffman Tree) 与哈 夫 曼 编 码 结点的路径长度 从根结点到该结点的路径上分 支的数目 结点间路径长度(Path Length) 连接两结点的路径上的分支数 树的带权路径长度 (Weighted Path Length,WPL) 树的各叶结点所带的权值与该 结点到根的路径长度的乘积的 和 树的路径长度 树中每个结点的路径长度之和 在所有含n个叶子结点、并带相同 权值的m叉树中，必存在一棵其带权路 径长度取最小值的树，称为“最优树”, 或“哈夫曼树” (Huffman Tree) 具有不同带权路径长度的二叉树 哈夫曼树中，权值大的结点离根最近 2 7 9 7 5 4 9 2 WPL(T)= 7?2+5?2+2?3+4?3+9?2 =60 WPL(T)= 7?4+9?4+5?3+4?2+2?1 =89 5 4 构造哈夫曼树 (以二叉树为例) 根据给定的 n 个权值 {w1, w2, …, wn}，造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权 值为 wi 的根结点，其左、右子树为 空树； (1) 在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和； (2) 从F中删去这两棵树，同时加入 刚生成的新树 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止 (3) (4) 9 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 任何一个字符的编码都不是