剑指offer之二叉树的下一个结点

1 问题

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针

2 分析

比如我现在的二叉树如下

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 4
     
    
   

    

     

    
    

     
 2 6
     
    
   

    

     

    
    

     
 1 3   5 7 
     
    
  
 

这里分3种情况

1) 如果这个节点包含右子树，那么下一个节点就是这个右子树的最左下节点，比如节点4的下一个节点是5.

2) 如果这个节点不包含右子树，如果这个节点的父节点的左子节点是同一个，那么下一个节点就是这个节点的父节点，比如节点6的下一个节点就是7.

3) 如果这个节点不包含右子树，如果这个节点的父节点的右子节点是同一个，这里分2种情况，我们先找到这节点的父结点，然后父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点，比如节点3的下一个节点是4，也有可能没有下一个节点，比如节点7的下一个节点就是空。

3 代码实现

  

   

    

     

    
    

     

      typedef struct Tree
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int value;
     
    
   

    

     

    
    

     
 struct Tree* left;
     
    
   

    

     

    
    

     
 struct Tree* right;
     
    
   

    

     

    
    

     
 struct Tree* parent;
     
    
   

    

     

    
    

     

       Tree(int value) : value(value), left(NULL), right(NULL), parent(NULL) {}
     
    
   

    

     

    
    

     

       Tree() : value(0), left(NULL), right(NULL), parent(NULL) {}
     
    
   

    

     

    
    

     

      } Tree;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      Tree* getNext(Tree* node)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (NULL == node)
     
    
   

    

     

    
    

     
 return NULL;
     
    
   

    

     

    
    

     

       Tree* nextNode = NULL;
     
    
   

    

     

    
    

     
 if (NULL != node->right)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Tree* rightNode = node->right;
     
    
   

    

     

    
    

     
 while (rightNode->left != NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       rightNode = rightNode->left;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       nextNode = rightNode;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       Tree* currentNode = node;
     
    
   

    

     

    
    

     

       Tree* parentNode = currentNode->parent;
     
    
   

    

     

    
    

     
 while (NULL != parentNode && parentNode->right == currentNode)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       currentNode = parentNode;
     
    
   

    

     

    
    

     

       parentNode = currentNode->parent;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       nextNode = parentNode;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return nextNode;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/102512202