二叉树前驱后继的查找

1、线索二叉树的运算1査找某结点*p在指定次序下的前趋和后继结点（1）在中序线索二叉树中，查找结点*卩的中序后继结点在中序线索二叉树中，查找结点*p的中序后继结点分两种情形：若*p的右子树空（即p-rtag为Thread），则p-rchild为右线索，直接指向*p的中序后继。【例】下图的中序线索二叉树中，结点D的中序后继是A。AI-：M.LL000o0（心中序战盍二义郴【例】下图的中序线索二叉树中，结点D的中序后继是A。AI-：M.LL000o0（心中序战盍二义郴屮序线索二冥树及叭有储嵇构M/LL0 E0/匚11H1若*p的右子树非空（即p-rtag为Link），则*卩的中序后继必是其右子树中第一

2、个中序 遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有 左孩子的结点为止，该结点是*p的右子树中最左下的结点，即*P的中序后继结点。【例】上图的中序线索二叉树中：A的中序后继是F,它有右孩子;F 的中序后继是 H ，它无右孩子；B 的中序后继是 D ，它是 B 的右孩子。在中序线索二叉树中求中序后继结点的过程可【参见动画演示】，具体算法如下：BinThrNode *InorderSuccessor(BinThrNode *p)/在中序线索树中找结点*卩的中序后继，设p非空BinThrNode *q；if (p-rtag=Thread) *p 的右子树为空Ret

3、urn p-rchild； /返回右线索所指的中序后继elseq=p-rchild；/从*p的右孩子开始查找while (q-ltag=Link)q=q-lchild； /左子树非空时，沿左链往下查找return q；/当 q 的左子树为空时，它就是最左下结点 /end if该算法的时间复杂度不超过树的高度h,即0(h)。在中序线索二叉树中查找结点*卩的中序前趋结点中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继 结点的方法完全对称。具体情形如下：若*p的左子树为空，则p-lchild为左线索，直接指向*p的中序前趋结点；【例】上图所示的中序线索二叉树中，F结点的中

4、序前趋结点是A若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没 有右孩子的结点为止。该结点是*p的左子树中最右下的结点，它是*p的左子树中最后一 个中序遍历到的结点，即*p的中序前趋结点。【例】上图所示中序线索二叉树中，结点E左子树非空，其中序前趋结点是I 在中序线索二叉树中求中序前趋结点的过程可【参见动画演示】，具体算法如下：BinThrNode *Inorderpre(BinThrNode *p)/在中序线索树中找结点*卩的中序前趋，设p非空BinThrNode *q；if (p-ltag=Thread) *p 的左子树为空return p-lchild； /返

5、回左线索所指的中序前趋elseq=p-lchild；从*p的左孩子开始查找while (q-rtag=Link)q=q-rchild；/右子树非空时，沿右链往下查找return q； /当 q 的右子树为空时，它就是最右下结点 /end if由上述讨论可知：对于非线索二叉树，仅从*p出发无法找到其中序前趋(或中序后继)， 而必须从根结点开始中序遍历，才能找到*卩的中序前趋(或中序后继)。线索二叉树中的线索 使得查找中序前趋和中序后继变得简单有效。在后序线索二叉树中，查找指定结点*卩的后序前趋结点在后序线索二叉树中，查找指定结点*卩的后序前趋结点的具体规律是：若*p的左子树为空，则p-lchil

6、d是前趋线索，指示其后序前趋结点。【例】在下图所示的后序线索二叉树中，H的后序前趋是B， F的后序前趋是C。BEFDGH需序线窘二艾树NULL若BEFDGH需序线窘二艾树NULL若*p的左子树非空，则p-lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。当*卩的右子树非空时，*p的右孩子必是其后序前趋【例】在上图所示的后序线索二叉树中，A的后序前趋是E；当*卩无右子树时，*p的后序前趋必是其左孩子【例】在上图所示的后序线索二叉树中，E的后序前趋是F在后序线索二叉树中，查找指定结点*卩的后序后继结点具体的规律：若*p是根，则

7、*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继 为空若*p是其双亲的右孩子，则*p的后序后继结点就是其双亲结点【例】上图所示的后序线索二叉树中，E的后序后继是A。若*p是其双亲的左孩子，但*P无右兄弟，*卩的后序后继结点是其双亲结点【例】上图所示的后序线索二叉树中，F的后序后继是E。若*p是其双亲的左孩子，但*p有右兄弟，则*卩的后序后继是其双亲的右子树中第一 个后序遍历到的结点，它是该子树中最左下的叶结点【例】上图所示的后序线索二叉树中，B的后序后继是双亲A的右子树中最左下的叶 结点 HF 是孩子树中最左下结点，但它不是叶子。由上述讨论中可知：在后序线索树中，仅从*p出发就能找到其后序前趋结点；要找*p 的后序后继结点，仅当*卩的右子树为空时，才能直接由*卩的右线索p-