題目：給定一棵二叉樹和其中的一個(gè)節(jié)點(diǎn)，如何找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)？樹中的節(jié)點(diǎn)除了有兩個(gè)分別指向左、右子節(jié)點(diǎn)的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針。

如下圖中的二叉樹的中序遍歷序列是{d,b,h,e,i,a,f,c,g}。我們將以這棵樹為例來分析如何找出二叉樹的下一個(gè)節(jié)點(diǎn)

1307402-20180521190942325-1516169312.png

分析

如果一個(gè)節(jié)點(diǎn)有右子樹，那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹。也就是說，從右子節(jié)點(diǎn)出發(fā)沿著指向左子節(jié)點(diǎn)的指針，我們就能找到它的下一個(gè)節(jié)點(diǎn)。如上圖節(jié)點(diǎn)b的下一個(gè)節(jié)點(diǎn)就是h，節(jié)點(diǎn)a的下一個(gè)節(jié)點(diǎn)是f

如果節(jié)點(diǎn)沒有右子樹，當(dāng)節(jié)點(diǎn)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是它的父節(jié)點(diǎn)。如圖節(jié)點(diǎn)d的下一個(gè)節(jié)點(diǎn)b，節(jié)點(diǎn)f的下一個(gè)節(jié)點(diǎn)是c

如果一個(gè)節(jié)點(diǎn)既沒有右子樹，并且它還是它父節(jié)點(diǎn)的右子樹，那么這種情況就有點(diǎn)復(fù)雜。我們可以沿著指向父節(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)i的下一個(gè)節(jié)點(diǎn)，我們沿著指向父節(jié)點(diǎn)的指針向上遍歷，先到達(dá)節(jié)點(diǎn)e。由于節(jié)點(diǎn)e是它父節(jié)點(diǎn)b的右節(jié)點(diǎn)，我們繼續(xù)向上遍歷到節(jié)點(diǎn)b。節(jié)點(diǎn)b是它父節(jié)點(diǎn)a的左子節(jié)點(diǎn)，因此節(jié)點(diǎn)b的父節(jié)點(diǎn)a就是節(jié)點(diǎn)i的下一個(gè)節(jié)點(diǎn)

找出節(jié)點(diǎn)g的下一個(gè)節(jié)點(diǎn)的步驟類似，我們先沿著父節(jié)點(diǎn)的指針到達(dá)節(jié)點(diǎn)c。由于節(jié)點(diǎn)c是它父節(jié)點(diǎn)a的右子節(jié)點(diǎn)，因此我們繼續(xù)向上遍歷到節(jié)點(diǎn)a。由于節(jié)點(diǎn)a是樹的根節(jié)點(diǎn)，它沒有父節(jié)點(diǎn)，因此節(jié)點(diǎn)g沒有下一個(gè)節(jié)點(diǎn)

總結(jié)

1. 如果一個(gè)節(jié)點(diǎn)有右子樹,那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹中的最左節(jié)點(diǎn)
2. 如果一個(gè)節(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)向上遍歷,父節(jié)點(diǎn)A是它本身父節(jié)點(diǎn)B的左孩子,B是下一個(gè)節(jié)點(diǎn)
• 如果沒有就是尾節(jié)點(diǎn)，返回NULL

算法實(shí)現(xiàn)

二叉樹

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
    BinaryTreeNode *m_pParent;
};

獲取下一個(gè)節(jié)點(diǎn)

BinaryTreeNode* GetNext(BinaryTreeNode *pNode)
{
    if (pNode == nullptr)
        return nullptr;

    BinaryTreeNode *pNext = nullptr; // 用于記錄下一個(gè)節(jié)點(diǎn)
    if (pNode->m_pRight != nullptr) // 右子樹存在
    {
        BinaryTreeNode *pRight = pNode->m_pRight; // 獲得當(dāng)前右子節(jié)點(diǎn)
        while (pRight->m_pLeft != nullptr)  // 左子節(jié)點(diǎn)不為空，那么循環(huán)遍歷找到葉子節(jié)點(diǎn)
            pRight = pRight->m_pLeft;

        pNext = pRight; // 找到下一個(gè)節(jié)點(diǎn)
    }
    else if (pNode->m_pParent != nullptr) // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)存在
    {
        BinaryTreeNode *pCurrent = pNode; // 當(dāng)前節(jié)點(diǎn)
        BinaryTreeNode *pPrarent = pNode->m_pParent; // 父節(jié)點(diǎn)
        // 父節(jié)點(diǎn)不為空，并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)，循環(huán)向上遍歷
        while (pPrarent != nullptr && pCurrent == pPrarent->m_pRight) {
            pCurrent = pPrarent;
            pPrarent = pPrarent->m_pParent;
        }
        pNext = pPrarent;
    }
    return  pNext;
}

輔助函數(shù)

// 創(chuàng)建二叉樹
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = nullptr;
    pNode->m_pRight = nullptr;
    pNode->m_pParent = nullptr;

    return pNode;
}

// 連接二叉樹
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;

        if(pLeft != nullptr)
            pLeft->m_pParent = pParent;
        if(pRight != nullptr)
            pRight->m_pParent = pParent;
    }
}

// 打印節(jié)點(diǎn)
void PrintTreeNode(BinaryTreeNode* pNode)
{
    if(pNode != nullptr)
    {
        printf("value of this node is: %d\n", pNode->m_nValue);

        if(pNode->m_pLeft != nullptr)
            printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
        else
            printf("left child is null.\n");

        if(pNode->m_pRight != nullptr)
            printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue);
        else
            printf("right child is null.\n");
    }
    else
    {
        printf("this node is null.\n");
    }

    printf("\n");
}

// 打印樹
void PrintTree(BinaryTreeNode* pRoot)
{
    PrintTreeNode(pRoot);

    if(pRoot != nullptr)
    {
        if(pRoot->m_pLeft != nullptr)
            PrintTree(pRoot->m_pLeft);

        if(pRoot->m_pRight != nullptr)
            PrintTree(pRoot->m_pRight);
    }
}

// 銷毀樹
void DestroyTree(BinaryTreeNode* pRoot)
{
    if(pRoot != nullptr)
    {
        BinaryTreeNode* pLeft = pRoot->m_pLeft;
        BinaryTreeNode* pRight = pRoot->m_pRight;

        delete pRoot;
        pRoot = nullptr;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

// 測試
void Test(char* testName, BinaryTreeNode* pNode, BinaryTreeNode* expected)
{
    if(testName != nullptr)
        printf("%s begins: ", testName);

    BinaryTreeNode* pNext = GetNext(pNode);
    if(pNext == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}

簡單使用

int main(int argc, const char * argv[]) {
    BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    Test("Test1", pNode8, pNode9);
    Test("Test2", pNode6, pNode7);
    Test("Test3", pNode10, pNode11);
    Test("Test4", pNode5, pNode6);
    Test("Test5", pNode7, pNode8);
    Test("Test6", pNode9, pNode10);
    Test("Test7", pNode11, nullptr);

    DestroyTree(pNode8);
    return 0;
}