数据结构课件--第六章.pptVIP

RChild Rtag Data Ltag LChild 为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示： 其中： Ltag= 0 LChild域指示结点的左孩子 1 LChild域指示结点的遍历前驱 Rtag= 0 RChild域指示结点的右孩子 1 RChild域指示结点的遍历后继 返回主目录 线索：在这种存储结构中，指向前驱和后继结点的指针叫做线索。 线索链表：以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表。 线索化：对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。 线索二叉树：线索化了的二叉树称为线索二叉树。 返回主目录 2. 二叉树的线索化 线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此线索化的过程是在遍历过程中修改空指针域的过程。 对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树 （先序线索二叉树、中序线索二叉树和后序线索二叉树）。 返回主目录 中序线索化算法： void Inthread(BiTree root) /* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL* / { if (root!=NULL) { Inthread(root-LChild); /* 线索化左子树 */ if (root-LChild==NULL) {root-Ltag=1; root-LChile=pre; / *置前驱线索 */} if (pre!=NULL pre-RChild==NULL) /* 置后继线索 */ pre- RChild=root; pre=root； Inthread(root-RChild); /*线索化右子树*/ } } 返回主目录 下面是对同一棵二叉树的遍历方法不同得到的不同线索树。 NULL (a)二叉树 A B C D G E F H (b)先序线索二叉树 A B C D G E F H NULL NULL （c）中序线索二叉树 A B C D G E F H （d）后序线索二叉树 NULL A B C D G E F H 返回主目录 3. 在线索二叉树中找前驱、后继结点 1）找结点的中序前驱结点 根据线索二叉树的基本概念和存储结构可知，对于结点p，当p-Ltag=1时，p-LChild指向p的前驱。 当p-Ltag=0时，p-LChild指向p的左孩子。由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。其查找算法如下： 返回主目录 在中序线索树中找结点前驱算法： void InPre(BiTNode * p, BiTNode * pre) /* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */ { if(p-Ltag==1) pre= p-LChild; /*直接利用线索*/ else { /* 在p的左子树中查找“最右下端”结点 */ for(q= p-LChild;q-Rtag==0;q=q-RChild); pre=q; } } 返回主目录 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; } } 返回主目录 4. 线索二叉树的插入、删除运算 二叉树加上线索之后，当插入或删除一结点时，可能会破坏原树的线索。所以在线索二叉树中插入或删除结点的难点在于：插入一个结点后，仍要保持正确的线索。 我们主要以中序线索二叉树为例，说明线索二叉树的插入和删除运算。 返回主目录 1）插入结点运算 在中序线索二叉树中插入结点可分为两种情况： 第一种：将新的结点插入到二叉树中，作某结点的左孩子； 第二种：将新的结点插入到二叉树中，作某结点的右孩子。 我们仅讨论后一种情