劍指offer之二叉樹的下一個(gè)結(jié)點(diǎn)

1 問題

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


 
2 分析

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

     
                    4
               2         6
            1     3   5     7

這里分3種情況

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

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

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

 
3 代碼實(shí)現(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)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)