剑指Offer - 面试题8：二叉树的下一个节点

typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
struct BinaryTreeNode
{
  TElemType m_nValue;
  BinaryTreeNode* m_pLeft;
  BinaryTreeNode* m_pRight;
  BinaryTreeNode* m_pParent;
};

#include <iostream>
using namespace std;
typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
struct BinaryTreeNode
{
  TElemType 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 = nullptr;
  pNode->m_pRight = nullptr;
  pNode->m_pParent = nullptr;
  return pNode;
}
//连接节点
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
  if (nullptr == pParent)
  {
    return;
  }
  pParent->m_pLeft = pLeft;
  pParent->m_pRight = pRight;
  if (nullptr != pLeft)
  {
    pLeft->m_pParent = pParent;
  }
  if (nullptr != pRight)
  {
    pRight->m_pParent = pParent;
  }
}
void Print(TElemType n)
{
  cout << n << " ";
}
void Preorder(BinaryTreeNode* root)//前序遍历
{
  if (nullptr == root)
  {
    return;
  }
  Print(root->m_nValue);
  Preorder(root->m_pLeft);
  Preorder(root->m_pRight);
}
void Inorder(BinaryTreeNode* root)//中序递归
{
  if (nullptr == root)
  {
    return;
  }
  Inorder(root->m_pLeft);
  Print(root->m_nValue);
  Inorder(root->m_pRight);
}
BinaryTreeNode* GetNext(BinaryTreeNode* pNode)//中序遍历中找出一个节点的下一个节点
{
  if (nullptr == pNode)
  {
    return nullptr;
  }
  BinaryTreeNode* pNext = nullptr;//存储下一个节点的指针
  //该节点有右子树，
  if (nullptr != pNode->m_pRight)
  {
    BinaryTreeNode* p = pNode;
    //那么它的下一个节点就是它的右子树中最左子节点
    while (nullptr != p->m_pLeft)
    {
      p = p->m_pLeft;
    }
    pNext = p;
  }
  //该节点无右子树
  else
  {
    BinaryTreeNode* parent = pNode->m_pParent;//父亲节点指针
    BinaryTreeNode* p = pNode;//当前节点指针
    //有如下俩种情况。但是可以合并
    //1.该节点是父亲的左节点。那么它的下一个节点就是它的父亲节点
    //2.该节点是父亲的右节点，那么只能沿着父亲节点的指针一直向上遍历，
    //   直到找到一个是它父亲节点的左子节点。
    //若该节点是父亲的右节点就一直找
    while (nullptr != parent && parent->m_pRight == p)
    {
      p = parent;
      parent = p->m_pParent;
    }
    pNext = parent;
  }
  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);
  /*输出*/
  cout << "中序遍历：";
  Inorder(pNode8);
  cout << endl << "先序遍历：";
  Preorder(pNode8);
  /*测试*/
  cout << endl << "找中序遍历中节点5的下一个节点为：";
  BinaryTreeNode* ret = GetNext(pNode5);
  if (nullptr == ret)
  {
    cout << "nullptr" << endl;
  }
  else
  {
    cout << ret->m_nValue << endl;
  }
  cout << "找中序遍历中节点7的下一个节点为：";
  ret = GetNext(pNode7);
  if (nullptr == ret)
  {
    cout << "nullptr" << endl;
  }
  else
  {
    cout << ret->m_nValue << endl;
  }
  cout << "找中序遍历中节点11的下一个节点为：";
  ret = GetNext(pNode11);
  if (nullptr == ret)
  {
    cout << "nullptr" << endl;
  }
  else
  {
    cout << ret->m_nValue << endl;
  }
  cout << "找中序遍历中节点10的下一个节点为：";
  ret = GetNext(pNode10);
  if (nullptr == ret)
  {
    cout << "nullptr" << endl;
  }
  else
  {
    cout << ret->m_nValue << endl;
  }
}