剑指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;
    }

 

     

 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)