|
() 在后序线索二叉树中查找指定结点*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)因为是非递归算法常数因子上小于递归的遍历算法因此若对一棵二叉树要经常遍历或 查找结点在指定次序下的前趋和后继则应采用线索链表作为存储结构为宜 ③ 以上介绍的线索二叉树是一种全线索树(即左右线索均要建立)许多应用中只要建立左右线索中的一种 ④ 若在线索链表中增加一个头结点令头结点的左指针指向根右指针指向其遍历序列的开始或终端结点会更方便 |
