劍指offer之二叉樹的下一個結(jié)點

1 問題

給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序的下一個結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的指針


 
2 分析

比如我現(xiàn)在的二叉樹如下

     
                    4
               2         6
            1     3   5     7

這里分3種情況

1) 如果這個節(jié)點包含右子樹，那么下一個節(jié)點就是這個右子樹的最左下節(jié)點，比如節(jié)點4的下一個節(jié)點是5.

2) 如果這個節(jié)點不包含右子樹，如果這個節(jié)點的父節(jié)點的左子節(jié)點是同一個，那么下一個節(jié)點就是這個節(jié)點的父節(jié)點，比如節(jié)點6的下一個節(jié)點就是7.

3) 如果這個節(jié)點不包含右子樹，如果這個節(jié)點的父節(jié)點的右子節(jié)點是同一個，這里分2種情況，我們先找到這節(jié)點的父結(jié)點，然后父節(jié)點的指針一直向上遍歷，直到找到一個是它父結(jié)點的左子結(jié)點的結(jié)點。如果這樣的結(jié)點存在，那么這個結(jié)點的父結(jié)點就是我們要找的下一個結(jié)點，比如節(jié)點3的下一個節(jié)點是4，也有可能沒有下一個節(jié)點，比如節(jié)點7的下一個節(jié)點就是空。

 
3 代碼實現(xiàn)

    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
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)