【数据结构】前序遍历和中序遍历确定二叉树

已知一个二叉树，我们可以得到它的前序遍历，中序遍历和后续遍历。那么，我们已知前序和中序的遍历结果，怎样还原二叉树呢？

假设前序遍历结果为：abdcef，中序遍历结果为dbaecf。

前序遍历：根结点+左子树+右子树

中序遍历：左子树+根结点+右子树

由此，我们可以得知，前序结果第一个字母a为根结点，在中序遍历结果中找到a，a的左侧d,b为a的左子树，a的右侧e,c,f为a的右子树；前序结果第二个字母b为a的左孩子，在中序遍历结果中找到b，b的左侧d为b的左子树，右子树为空；以此类推，利用递归，最终可以得到二叉树。

#include <iostream>
using namespace std;
#include <string>
template <class T>
struct TreeNode
{
	TreeNode(const T& data)
	: _data(data),_pLeft(NULL),_pRight(NULL)
	{}

	T _data;
	TreeNode<T> *_pLeft;
	TreeNode<T> *_pRight;
};
template <class T>
class BinTree
{
	typedef TreeNode<T> Node;
public:
	BinTree()
		: _pRoot(NULL)
	{}
	Node* ReBuildTree(char* preorder,char* inorder)
	{
		size_t size = strlen(inorder);
		return _ReBuildTree(_pRoot,preorder,inorder,inorder + size - 1);
	}
	void PostOrder()
	{
		cout << "后序遍历结果:";
		_PostOrder(_pRoot);
		cout << endl;
	}
private:
	Node* _ReBuildTree(Node*& pRoot,char*& preorder,char* inbegin,char* inend)
	{
		if (inbegin>inend || *preorder == '')
			return NULL;
		pRoot = new Node(*preorder);
		char* cur = inbegin;
		for (cur = inbegin; cur <= inend; cur++)
		{
			if (*cur == *preorder)
			{
				if (inbegin <= cur - 1)
					_ReBuildTree(pRoot->_pLeft,++preorder,inbegin,cur - 1);
				if (cur + 1 <= inend)
					_ReBuildTree(pRoot->_pRight,cur + 1,inend);
			}
		}
		return pRoot;
	}
	void _PostOrder(const Node* pRoot)
	{
		if (pRoot)
		{
			_PostOrder(pRoot->_pLeft);
			_PostOrder(pRoot->_pRight);
			cout << pRoot->_data << " ";
		}
	}
private:
	Node* _pRoot;
};