第6章树与二叉树2.ppt

附：中序遍历迭代算法(利用堆栈) * void iter_inorder(tree_pointer node) { int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) { for (; node; node=node-left_child) add(top, node);/* add to stack */ node= delete(top); /* delete from stack */ if (!node) break; /* empty stack */ printf(“%D”, node-data); node = node-right_child; } } 时间复杂度O(n) 附：层序遍历算法(利用队列) * void level_order(tree_pointer ptr) /* level order tree traversal */ { int front = rear = 0; tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */ addq(front, rear, ptr); for (;;) { ptr = deleteq(front, rear); + * E * D / C A B * * * * * * 第6章 树和二叉树（ Tree Binary Tree ） * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 （今日授课内容是本章及本课程的重点） 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 * 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 （二叉树的运算见下一节） 2. 二叉树的性质 (3+2) * 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k0）。 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： * 性质4: 具有n个结点的完全二叉树的深度必为?log2n?＋1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n≤2k-1 或2k-1≤n2k 三边同时取对数，于是有：k-1≤log2nk 因为k是整数，所以k= ?log2n? +1 可根据归纳法证明。 课堂讨论： * Q1：满二叉树和完全二叉树有什么区别？ A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。 满二叉树是完全二叉树的一个特例。 Q3: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 489 488 1 0 Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？ A1：因为只有这两种形式可以实现顺序存储！ 由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。 A3：易求出总层数和末层叶子数。总层数k=?log2n?＋1 =10; 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为1000-511=489个。 * 请注意叶子结点总数≠末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：末层的489个叶子只占据了上层的245个结点（?489/2? ) 上层（k=9)右边的0度结点数还有29-1-245=11个！ 另一法：可先求2度结点数,再由此得到叶子总数。 首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉） 另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2， （共有?4