由二叉树的前序和中序如何得到二叉树的后序呢？

由二叉树的前序和中序如何得到二叉树的后序呢？

在山城等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、成都网站建设 网站设计制作定制开发,公司网站建设,企业网站建设,高端网站设计,营销型网站建设,成都外贸网站建设公司,山城网站建设费用合理。

首先得明白什么是前序、中序、后序。

二叉树前序：遍历顺序为，根节点、左子树、右子树；中序：遍历顺序为，左子树、根节点、右子树；后序：遍历顺序为，左子树、右子树、根节点

可以发现，二叉树前序中的第一个节点为树的根节点root，然后找出root在中序里面的位置，就可以把前序和中序分别划分为左、右子树两个部分，然后递归调用即可。

#include
using namespace std;
template
struct BinaryTreeNode
{
	T _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	BinaryTreeNode(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
	{}
};
template
class BinaryTree
{
protected:
	BinaryTreeNode* _root;
protected:
	void _PreOrder(BinaryTreeNode* root)
	{
		if (root != NULL)
		{
			cout << root->_data << " ";
			_PreOrder(root->_left);
			_PreOrder(root->_right);
		}
		return;
	}
	BinaryTreeNode* _CreateBinary(char* preOrder, char* inOrder, int length)
	{
		BinaryTreeNode* root = NULL;
		if (length == 0)
			return NULL;
		int tmp = *preOrder;
		int index = 0;
		while (index < length&&inOrder[index] != tmp)
			index++;
		if (index < length)
		{
			root = new BinaryTreeNode(tmp-'0');
			root->_left = _CreateBinary(preOrder + 1, inOrder,index);
			root->_right = _CreateBinary(preOrder + index + 1, inOrder + index + 1, length - index - 1);
		}
		return root;
	}
	void _Clear(BinaryTreeNode* root)
	{
		if (root)
		{
			_Clear(root->_left);
			_Clear(root->_right);
			delete root;
		}
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	~BinaryTree()
	{
		_Clear(_root);
		_root = NULL;
	}
	void  PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}
	void CreateBinaryTree(char* preOrder, char* inOrder)
	{
		int length = strlen(preOrder);
		_root = _CreateBinary(preOrder, inOrder,length);
	}
};
void Test1()
{
	char* preOrder = "12473568";
	char* inOrder = "47215386";
	BinaryTree bt;
	bt.CreateBinaryTree(preOrder, inOrder);
	bt.PreOrder();
}

文章名称：由二叉树的前序和中序如何得到二叉树的后序呢？
网站地址：http://cdxtjz.cn/article/jcshjc.html