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

水深无声 2022-05-31 07:36 143阅读 0赞

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

假设前序遍历结果为：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;
    };

![20180211194431286][]

[20180211194431286]: /images/20220531/49efc6fd98154e28b208164abd1230f2.png