//找出二叉树中序遍历的下一个节点

#include <iostream>
#include<stdio.h>
using namespace std;
struct BinaryTreeNode
{
    int                    m_nValue;
    BinaryTreeNode*        m_pLeft;
    BinaryTreeNode*        m_pRight;
    BinaryTreeNode*        m_pParent;
};

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)
    {
        printf("value of this node is: %d\n", pNode->m_nValue);

        if(pNode->m_pLeft != NULL)
            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 != NULL)
            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 != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);

        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}
BinaryTreeNode* GetNext(BinaryTreeNode* pNode){
    if(pNode==NULL)
        return NULL;
    BinaryTreeNode* pNext=NULL;
    if(pNode->m_pRight!=NULL){//一个节点的右子树存在，那么它的下一个节点就是右子树的最左子节点
        BinaryTreeNode* pRight=pNode->m_pRight;
        while(pRight->m_pLeft!=NULL)
            pRight=pRight->m_pLeft;

        pNext=pRight;

    }
    else if(pNode->m_pParent!=NULL){//等价于下面的功能
        BinaryTreeNode* pCurrent=pNode;
        BinaryTreeNode* pParent=pNode->m_pParent;
        while(pParent!=NULL && pCurrent==pParent->m_pRight){
            pCurrent=pParent;
            pParent=pParent->m_pParent;
        }
        pNext=pParent;
    }
//    BinaryTreeNode* pParent=pNode->m_pParent;
//    if(pNode->m_pRight==NULL && pParent->m_pLeft==pNode){//这个节点没有右子树，并且是其父节点的左节点，那么它的下一个节点是其父节点，
//        pNext=pParent;
//    }
//    else if(pNode->m_pRight==NULL && pParent->m_pRight==pNode){//这个节点没有右子树，且是父节点的右子节点，比较复杂
//找到第一个该节点的祖先节点是目标节点的左子节点，这个目标节点就是它的下一个节点
//         BinaryTreeNode* pCurrent=pNode;
//        BinaryTreeNode* pParent=pNode->m_pParent;
//        while( pCurrent==pParent->m_pRight){
//            pCurrent=pParent;
//            pParent=pParent->m_pParent;
//        }
//        pNext=pParent;
//    }
    return pNext;
}

int main()
{
    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);

    BinaryTreeNode* p=GetNext(pNode10);


    cout<<p->m_nValue;
    return 0;
}