|
线索二叉树的运算 ． 查找某结点*p在指定次序下的前趋和后继结点 （）在中序线索二叉树中查找结点*p的中序后继结点 在中序线索二叉树中查找结点*p的中序后继结点分两种情形 ① 若*p的右子树空(即p>rtag为Thread)则p>rchild为右线索直接指向*p的中序后继 【例】下图的中序线索二叉树中结点D的中序后继是A ② 若*p的右子树非空(即p>rtag为Link)则*p的中序后继必是其右子树中第一个中序遍历到的结点也就是从*p的右孩子开始沿该孩子的左链往下查找直至找到一个没有左孩子的结点为止该结点是*p的右子树中最左下的结点即*P的中序后继结点 【例】上图的中序线索二叉树中 A的中序后继是F它有右孩子 F的中序后继是H它无右孩子 B的中序后继是D它是B的右孩子 在中序线索二叉树中求中序后继结点的过程可【参见动画演示】具体算法如下 BinThrNode *InorderSuccessor(BinThrNode *p) {//在中序线索树中找结点*p的中序后继设p非空 BinThrNode *q if (p>rtag==Thread) //*p的右子树为空 Return p>rchild //返回右线索所指的中序后继 else{ q=p>rchild //从*p的右孩子开始查找 while (q>ltag==Link) q=q>lchild //左子树非空时沿左链往下查找 return q //当q的左子树为空时它就是最左下结点 } //end if } 该算法的时间复杂度不超过树的高度h即O(h) （）在中序线索二叉树中查找结点*p的中序前趋结点 中序是一种对称序故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称具体情形如下 ① 若*p的左子树为空则p>child为左线索直接指向*p的中序前趋结点 【例】上图所示的中序线索二叉树中F结点的中序前趋结点是A ② 若*p的左子树非空则从*p的左孩子出发沿右指针链往下查找直到找到一个没有右孩子的结点为止该结点是*p的左子树中最右下的结点它是*p的左子树中最后一个中序遍历到的结点即*p的中序前趋结点 【例】上图所示中序线索二叉树中结点E左子树非空其中序前趋结点是I 在中序线索二叉树中求中序前趋结点的过程可【参见动画演示】具体算法如下 BinThrNode *Inorderpre(BinThrNode *p) {//在中序线索树中找结点*p的中序前趋设p非空 BinThrNode *q if (p>ltag==Thread) //*p的左子树为空 return p>lchild //返回左线索所指的中序前趋 else{ q=p>lchild //从*p的左孩子开始查找 while (q>rtag==Link) q=q>rchild //右子树非空时沿右链往下查找 return q //当q的右子树为空时它就是最右下结点 } //end if } 由上述讨论可知对于非线索二叉树仅从*p出发无法找到其中序前趋(或中序后继)而必须从根结点开始中序遍历才能找到*p的中序前趋(或中序后继)线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效 （） 在后序线索二叉树中查找指定结点*p的后序前趋结点 在后序线索二叉树中查找指定结点*p的后序前趋结点的具体规律是 ① 若*p的左子树为空则p>lchild是前趋线索指示其后序前趋结点 【例】在下图所示的后序线索二叉树中H的后序前趋是BF的后序前趋是C ② 若*p的左子树非空则p>lchild不是前趋线索由于后序遍历时根是在遍历其左右子树之后被访问的故*p的后序前趋必是两子树中最后一个遍历结点 当*p的右子树非空时*p的右孩子必是其后序前趋 【例】在上图所示的后序线索二叉树中A的后序前趋是E 当*p无右子树时*p的后序前趋必是其左孩子 【例】在上图所示的后序线索二叉树中E的后序前趋是F （） 在后序线索二叉树中查找指定结点*p的后序后继结点 具体的规律 ① 若*p是根则*p是该二叉树后序遍历过程中最后一个访问到的结点*p的后序后继为空 ② 若*p是其双亲的右孩子则*p的后序后继结点就是其双亲结点 【例】上图所示的后序线索二叉树中E的后序后继是A ③ 若*p是其双亲的左孩子但*P无右兄弟*p的后序后继结点是其双亲结点 【例】上图所示的后序线索二叉树中F的后序后继是E ④ 若*p是其双亲的左孩子但*p有右兄弟则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点它是该子树中最左下的叶结点 【例】上图所示的后序线索二叉树中B的后序后继是双亲A的右子树中最左下的叶结点H 注意 F是孩子树中最左下结点但它不是叶子 由上述讨论中可知在后序线索树中仅从*p出发就能找到其后序前趋结点要找*p的后序后继结点仅当*p的右子树为空时才能直接由*p的右线索p>rchild得到否则必须知道*p的双亲结点才能找到其后序后继因此如果线索二叉树中的结点没有指向其双亲结点的指针就可能要从根开始进行后序遍历才能找到结点*P的后序后继由此线索对查找指定结点的后序后继并无多大帮助 （） 在前序线索二叉树中查找指定结点*p的前序后继结点 【参见练习】 （） 在前序线索二叉树中查找指定结点*p的前序前趋结点 【参见参考书】 在前序线索二叉树中找某一点*p的前序后继也很简单仅从*p出发就可以找到但找其前序前趋也必须知道*p的双亲结点当树中结点未设双亲指针时同样要进行从根开始的前序遍历才能找到结点*p的前序前趋 ．遍历线索二叉树 遍历某种次序的线索二叉树只要从该次序下的开始结点开发反复找到结点在该次序下的后继直至终端结点 遍历中序线索二叉树算法 void TraverseInorderThrTree(BinThrTree p) { //遍历中序线索二叉树 if(p){//树非空 while(p>ltag==Link) p=p>lchild //从根往下找最左下结点即中序序列的开始结点 do{ printf(％cp>data) //访问结点 p=InorderSuccessor(p) //找*p的中序后继 }while(p) }//endif }//TraverselnorderThrTree 分析 ① 中序序列的终端结点的右线索为空所以do语句的终止条件是p==NULL ② 该算法的时间复杂性为O(n)因为是非递归算法常数因子上小于递归的遍历算法因此若对一棵二叉树要经常遍历或查找结点在指定次序下的前趋和后继则应采用线索链表作为存储结构为宜 ③ 以上介绍的线索二叉树是一种全线索树（即左右线索均要建立）许多应用中只要建立左右线索中的一种 ④ 若在线索链表中增加一个头结点令头结点的左指针指向根右指针指向其遍历序列的开始或终端结点会更方便 |
