题目

给定一颗二叉树和其中的一个节点，如何找出中序便利序列的下一个节点？树中的节点除了有俩个分别指向左、右子节点的指针，还有一个指向父节点的指针。

结构如下

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

分析

简单画出一个二叉树

想要在中序遍历中找到一个节点的下一个节点，我们可以分情况讨论。

我们还可以合并一下无右子树的情况，将2.1合并到2.2中。

代码如下
C++

#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;
	}

}

测试如下

本章完！