第六章-01(ldq)4.ppt

数 据 结 构 ——C语言描述 青海师范大学计算机学院 （1）输出二叉树中的结点 （2）输出二叉树中的叶子结点 （3）统计叶子结点数目 （4）建立二叉链表方式存储的二叉树 （5）求二叉树的高度 （6）按树状打印二叉树 以上操作可以通过对二叉树遍历来完成，一方面要重点理解访 问根节点操作的含义，另一方面要注意对具体的实现时是否要 考虑遍历的次序选择的要求。 请注意： 作业： 算法作业： 深入理解二叉树遍历的三种方法。 先序、中序、后序遍历。 书面作业P194 (4) (5) （2）找结点的中序后继结点 ①分析：对于结点p，若要找其后继结点， 当p-Rtag=1时，p-RChild即为p的后继结点； 当p-Rtag=0时， 说明p有右子树，此时p的中序后继结点即为其右子树的“最左下端”的结点。 ② 查找算法： void InSucc(BiTNode *p, BiTNode *succ) /*在中序线索二叉树中查找p的中序后继结点， 并用succ指针返回结果*/ { if (p-Rtag==1) succ= p- RChild; /*直接利用线索*/ else { /*在p的右子树中查找“最左下端”结点*/ for(q= p-RChild; q-Ltag==0 ; q=q-LChild ); succ=q; } } ③ 找结点的中序后继结点动态演示： 遍历线索树的问题可以分为两步：第一步是求出某种遍历次序下第一个被访问结点，然后连续求出刚访问结点的后继结点，直至所有的结点均被访问。 （1）在中序线索树上求中序遍历的第一个结点 BiTNode *InFirst (BiTree Bt) { BiTNode *p = Bt; if ( ! P ) return (Null) While (p-LTag == 0) p=p-LChild ; return p } 4 遍历中序线索树 （2）遍历中序二叉线索树 void TInOrder (BiTree Bt) { BiTNode *p; P=InFirst ( Bt ); While ( p ) { Visit ( p ) ; p = InNext (p); } 通过调用InFirst和 InNext，可以实现对中序线索树的中序遍历，且不需要使用递归栈。 （1） 插入结点运算 在中序线索二叉树上插入新结点可分两种情况：要么作某结点的左孩子、要么作某结点的右孩子。 在后种情况中，用InsNode(BiTNode *p, BiTNode *r)表示在线索二叉树中插入r所指向的结点，做p所指结点的右孩子。此时有两种情况： ①若结点p的右孩子为空，则插入结点r的过程很简单。原来p的后继变为r的后继，结点p变为r的前驱，结点r成为p的右孩子，结点r的插入对p原来的后继结点没有任何的影响。插入过程如下图所示。 5 插入、删除运算 ——以中序线索二叉树为例 图：结点的右孩子为空时的插入操作 ②若p的右孩子不为空，则插入后，p的右孩子变为r的右孩子结点， p变为r的前驱结点，r变为p的右孩子结点，这时还需要修改原来p的右子树中“最左下端”结点的左指针域，使它由原来的指向结点p变为指向结点r。插入过程如下图所示。 图：结点的右孩子非空时的插入操作 算法描述： void InsNode(BiTNode *p, BiTNode *r) {if(p-Rtag==1) /* p无右孩子 */ { r-RChild=p-RChild; /* p的后继变为r的后继 */ r-Rtag=1; p-RChild=r; /* r成为p的右孩子 */ r-LChild=p; /* p变为r的前驱 *