数据结构-树与叉树.pptVIP

Chapter 6Tree Binary Tree 树的基本术语 性质2 深度为 k 的二叉树至多有 2 k-1个结点，其中k ? 1。 证明：由性质1可见，深度为k的二叉树的最大结点数为 层次遍历(Levelorder Traversal) 从上到下，从左到右 遍历结果 - ＋／a* e f b -cd 二叉树的重建 　　由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树 前序序列{ A B H F D E C K G } 中序序列{ H B D F A E K C G } 二叉树应用事例 int main(void) { BinTreeNodeint *cur; int c; cur = new BinTreeNodeint(2); BinaryTreeint bt(cur); // 建立二叉树 c = 3; bt.InsertLeftChild(cur, c); // 插入左孩子 cur = bt.LeftChild(cur); c = 4; bt.InsertRightChild(cur, c); // 插入右孩子 cur = bt.GetRoot(); // 取出根结点 c = 6; bt.InsertRightChild(cur, c); // 插入右孩子 return 0; } 6.7 哈 夫 曼 树 (Huffman Tree) 与哈 夫 曼 编 码 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 层次遍历： A B C D E F G H I J K B C D E F G H I J K 1．森林中第一棵树的根结点 2．森林中第一棵树的子树森林 3．森林中其它树构成的森林 森林由三部分构成 森林的先根遍历 若森林F为空, 返回 否则: ?访问F的第一棵树的根结点 ?先根次序遍历第一棵树的子树森林 ?先根次序遍历其它树组成的森林 结果：B E F C D G H I J K B H I F C D E G J K 森林的后根遍历 若森林F为空，返回 否则: ?后根次序遍历第一棵树的子树森林 ?访问F的第一棵树的根结点 ?后根次序遍历其它树组成的森林 结果：E F B C I J K H G D B H I F C D E G J K 森林的层次遍历 若森林F为空，返回 否则: ?依次遍历各棵树的根结点 ?依次遍历各棵树根结点的所有子女 ?依次遍历这些子女结点的子女结点? 结果：B C D E F G H I J K B H I F C D E G J K 森林与二叉树的相互转换 结点的路径长度 从根结点到该结点的路径上分 支的数目 树的路径长度 树中每个结点的路径长度之和 树的带权路径长度 (Weighted Path Length,WPL) 树的各叶子结点所带的权值与 该结点到根的路径长度的乘积 的和 结点的带权路径长度 从该结点到到根结点之间的路 径长度与结点上权的乘积。 在所有含n个叶子结点、并带有各自权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”, 或“哈夫曼树” (Huffman Tree) 哈夫曼树中，权值大的结点离根最近 具有不同带权路径长度的二叉树 2 7 5 4 9 WPL(a)= 7?2+5?2+2?3+4?3+9?2=60 WPL(b)= 7?4+9?4+5?3+4?2+2?1=89 7 9 2 5 4 根据给定的 n 个权值 {w1, w2, …, wn}，造 n 棵二叉树的