树和叉树(严).pptVIP

第6章 树和二叉树 性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，则有：N=n0+n1+n2 再看二叉树中的分支数： 除根结点外，其余每个结点都有唯一的一个进入分支，而所有这些分支都是由度为1和2的结点射出的。设B为二叉树中的分支总数，则有： N=B+1 ∴ B＝n1+2?n2 ∴ N=B+1=n1+2?n2+1 ∴ n0+n1+n2=n1+2?n2+1 即 n0=n2+1 证毕 性质4 结点数为n的完全二叉树，其深度为 ?log2n? + l 其中符号： ?x?表示不大于x的最大整数。 ?x? 表示不小于x的最小整数。 证明：假设完全二叉树的深度为k，则根据性质2及完全二叉树的定义有： 2k-1-1n≦2k-1 或 2 k-1≦n2k 取对数得：k－1㏒2nk 因为k是整数。 ∴ k= ?㏒2n? +1 证毕 性质5 在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有： ⑴ i=1时，结点i是树的根；否则，结点i的双亲为结点 ? i/2 ? (i1) 。 ⑵ 2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。 ⑶ 2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。 证明：用数学归纳法证明。首先证明⑵和⑶，然后由⑵和⑶导出⑴。 当i=1时，由完全二叉树的定义知，结点i的左孩子的编号是2，右孩子的编号是3。 若2n，则二叉树中不存在编号为2的结点，说明结点i的左孩子不存在。 若3n，则二叉树中不存在编号为3的结点，说明结点i的右孩子不存在。 现假设对于编号为j(1≦j≦i)的结点，(2)和(3)成立。即： ◆ 当2j≦n ：结点j的左孩子编号是2j；当2jn时，结点j的左孩子结点不存在。 当i1时，设编号为i的结点的双亲结点的编号为m，若编号为i的结点是其双亲结点的左孩子，则由(2)有： i=2m ，即m=?i/2? ； 若编号为i的结点是其双亲结点的右孩子，则由(3)有： i=2m+1 ，即m=?(i-1) /2? ； ∴ 当i1时，其双亲结点的编号为?i/2? 。 证毕 6.2.3 二叉树的存储结构 6.3 遍历二叉树及其应用 遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。 二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。 6.3.1 先序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 访问根结点； ⑵ 先序遍历左子树(递归调用本算法)； ⑶ 先序遍历右子树(递归调用本算法)。 2 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 访问p所指向的结点； ⑵ q=p-Rchild ，若q不为空，则q进栈； ⑶ p=p-Lchild ，若p不为空，转(1)，否则转(4)； ⑷ 退栈到p ，转(1)，直到栈空为止。 算法实现： 6.3.2 中序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 中序遍历左子树(递归调用本算法)； ⑵ 访问根结点； ⑶ 中序遍历右子树(递归调用本算法)。 2 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T ⑴ 若p不为空，p进栈， p=p-Lchild ； ⑵ 否则(即p为空)，退栈到p，访问p所指向的结点； ⑶ p=p-Rchild ，转(1)； 直到栈空为止。 算法实现： 6.3.3 后序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 后序遍历左子树(递归调用本算法)； ⑵ 后序遍历右子树(递归调用本算法) ； ⑶ 访问