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

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

假设前序遍历结果为: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 == '\0')
			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, ++preorder, cur + 1, inend);
			}
		}
		return pRoot;
	}
	void _PostOrder(const Node* pRoot)
	{
		if (pRoot)
		{
			_PostOrder(pRoot->_pLeft);
			_PostOrder(pRoot->_pRight);
			cout << pRoot->_data << " ";
		}
	}
private:
	Node* _pRoot;
};

相关文章
相关标签/搜索