【数据结构】二叉树前驱后继的查找_二叉树的后继元素怎么找

转自文库

 

线索二叉树的运算

1．查找某结点*p在指定次序下的前趋和后继结点
（1）在中序线索二叉树中，查找结点*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)。

 

（2）在中序线索二叉树中查找结点*p的中序前趋结点
　　中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下：
①若*p的左子树为空，则p->1child为左线索，直接指向*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的中序前趋(或中序后继)。线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效。

 

（3）在后序线索二叉树中，查找指定结点*p的后序前趋结点
　　在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是：
①若*p的左子树为空，则p->lchild是前趋线索，指示其后序前趋结点。
　　　【例】在下图所示的后序线索二叉树中，H的后序前趋是B，F的后序前趋是C。

 

②若*p的左子树非空，则p->lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。
　　当*p的右子树非空时，*p的右孩子必是其后序前趋
　　【例】在上图所示的后序线索二叉树中，A的后序前趋是E；
　　当*p无右子树时，*p的后序前趋必是其左孩子
　　【例】在上图所示的后序线索二叉树中，E的后序前趋是F

 

（4）在后序线索二叉树中，查找指定结点*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的后序后继。由此，线索对查找指定结点的后序后继并无多大帮助