《剑指offer》第八题（重要！查找二叉树的中序遍历的下一个结点）

文件一：main.cpp

// 面试题：二叉树的下一个结点

// 题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？

// 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。

#include <iostream>

#include "BinaryTree.h"

using namespace std;

BinaryTreeNode* GetNext(BinaryTreeNode* pNode)

{

    if (pNode == NULL)

        return NULL;

    BinaryTreeNode* pNext = NULL;//跟占位符一样的pNext

    if (pNode->m_pRight != NULL)//第一种情况：我有右孩子

    {

        pNext = pNode->m_pRight;//从这个右孩子开始，一直向下找到没有左孩子为止，则这个节点就是pNext

        while (pNext->m_pLeft != NULL)

            pNext = pNext->m_pLeft;

    }

    else if (pNode->m_pParent != NULL)//第二种情况：我没有右孩子，而我有父节点

    {

        BinaryTreeNode* pCurrent = pNode;

        pNext = pNode->m_pParent;

        while (pNext != NULL && pCurrent == pNext->m_pRight)//从我这个开始向上找父节点，一直找到我这一脉是该父节点的左孩子，如果遇到根节点还没有那就没了

        {

            pCurrent = pNext;

            pNext = pNext->m_pParent;

        }

    }

    return pNext;

}

// ====================测试代码====================

void Test(const char* testName, BinaryTreeNode* pNode, BinaryTreeNode* expected)

{

    if (testName != NULL)

        printf("%s begins: ", testName);

    BinaryTreeNode* pNext = GetNext(pNode);

    if (pNext == expected)

        printf("Passed.\n");

    else

        printf("FAILED.\n");

}

//            8

//        6      10

//       5 7    9  11

void Test1_7()

{

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode9 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode11 = CreateBinaryTreeNode();

    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, NULL);

    DestroyTree(pNode8);

}

//            5

//          4

//        3

//

void Test8_11()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode5, pNode4, NULL);

    ConnectTreeNodes(pNode4, pNode3, NULL);

    ConnectTreeNodes(pNode3, pNode2, NULL);

    Test("Test8", pNode5, NULL);

    Test("Test9", pNode4, pNode5);

    Test("Test10", pNode3, pNode4);

    Test("Test11", pNode2, pNode3);

    DestroyTree(pNode5);

}

//        2

//         3

//          4

//           5

void Test12_15()

{

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode2, NULL, pNode3);

    ConnectTreeNodes(pNode3, NULL, pNode4);

    ConnectTreeNodes(pNode4, NULL, pNode5);

    Test("Test12", pNode5, NULL);

    Test("Test13", pNode4, pNode5);

    Test("Test14", pNode3, pNode4);

    Test("Test15", pNode2, pNode3);

    DestroyTree(pNode2);

}

void Test16_17()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    Test("Test16", pNode5, NULL);

    Test("Test17", NULL, NULL);

    DestroyTree(pNode5);

}

int main(int argc, char* argv[])

{

    Test1_7();

    Test8_11();

    Test12_15();

    Test16_17();

    system("pause");

}

文件二：BinaryTree.h

#ifndef BINARY_TREE_H

#define BINARY_TREE_H

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft;

    BinaryTreeNode*        m_pRight;

    BinaryTreeNode*        m_pParent;

};

BinaryTreeNode* CreateBinaryTreeNode(int value);

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight);

void PrintTreeNode(BinaryTreeNode* pNode);

void PrintTree(BinaryTreeNode* pRoot);

void DestroyTree(BinaryTreeNode* pRoot);

#endif

文件三：BinaryTree.cpp

#include <iostream>

#include "BinaryTree.h"

using namespace std;

BinaryTreeNode* CreateBinaryTreeNode(int value)//还是建立新节点

{

    BinaryTreeNode* pNode = new BinaryTreeNode();

    pNode->m_nValue = value;

    pNode->m_pLeft = NULL;

    pNode->m_pRight = NULL;

    pNode->m_pParent = NULL;

    return pNode;

}

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)//一个父节点连接左右两孩子

{

    if (pParent != NULL)

    {

        pParent->m_pLeft = pLeft;

        pParent->m_pRight = pRight;

        if (pLeft != NULL)

            pLeft->m_pParent = pParent;

        if (pRight != NULL)

            pRight->m_pParent = pParent;

    }

}

void PrintTreeNode(BinaryTreeNode* pNode)//打印当前节点

{

    if (pNode != NULL)

    {

        cout << "value of this node is:" << pNode->m_nValue << endl;

        if (pNode->m_pLeft != NULL)

            cout << "value of its left child is:" << pNode->m_pLeft->m_nValue << endl;

        else

            cout << "left child is null.\n";

        if (pNode->m_pRight != NULL)

            cout << "value of its right child is: " << pNode->m_pRight->m_nValue << endl;

        else

            cout << "right child is null.\n";

    }

    else

    {

        cout << "this node is null.\n";

    }

    cout << endl;

}

void PrintTree(BinaryTreeNode* pRoot)//打印整个树

{

    PrintTreeNode(pRoot);

    if (pRoot != NULL)

    {

        if (pRoot->m_pLeft != NULL)

            PrintTree(pRoot->m_pLeft);

        if (pRoot->m_pRight != NULL)

            PrintTree(pRoot->m_pRight);

    }

}

void DestroyTree(BinaryTreeNode* pRoot)//删除整个树

{

    if (pRoot != NULL)

    {

        BinaryTreeNode* pLeft = pRoot->m_pLeft;

        BinaryTreeNode* pRight = pRoot->m_pRight;

        delete pRoot;

        pRoot = NULL;

        DestroyTree(pLeft);

        DestroyTree(pRight);

    }

}