树 - 线索二叉树 （四）
( ) 在后序线索二叉树中 查找指定结点*p的后序前趋结点
在后序线索二叉树中 查找指定结点*p的后序前趋结点的具体规律是
① 若*p的左子树为空 则p >lchild是前趋线索 指示其后序前趋结点
【例】在下图所示的后序线索二叉树中 H的后序前趋是B F的后序前趋是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( %c p >data); //访问结点
p=InorderSuccessor(p); //找*p的中序后继
}while(p)
}//endif
}//TraverselnorderThrTree
分析
① 中序序列的终端结点的右线索为空 所以do语句的终止条件是p==NULL
② 该算法的时间复杂性为O(n) 因为是非递归算法 常数因子上小于递归的遍历算法 因此 若对一棵二叉树要经常遍历 或
查找结点在指定次序下的前趋和后继 则应采用线索链表作为存储结构为宜
③ 以上介绍的线索二叉树是一种全线索树(即左右线索均要建立) 许多应用中只要建立左右线索中的一种
④ 若在线索链表中增加一个头结点 令头结点的左指针指向根 右指针指向其遍历序列的开始或终端结点会更方便
lishixinzhi/Article/program/sjjg/201311/23874
