已知中序后序创建二叉树

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

template<class Type>
class BinaryTree
{
public:
	struct TreeNode
	{
		Type data;
		TreeNode *leftchild, *rightchild;
	};
	BinaryTree() {}
	~BinaryTree(){}
private:
	TreeNode *root;

	static TreeNode *_BuyNode()
	{
		TreeNode *p = (TreeNode *)malloc(sizeof(TreeNode));
		assert(p != NULL);
		return p;
	}

	static int find(Type *is, const Type &x, int n)
	{
		for(int i = 0; i < n; ++i)
		{
			if(is[i] == x)
				return i;
		}
		return -1;
	}

	static TreeNode *CreatInPost(Type *post, Type *is, int n)
	{
		if(post == NULL || is == NULL || n ==0)
			return NULL;
		else
		{
			TreeNode *s = _BuyNode();
			s->data = post[n-1];

			int num = find(is, post[n-1], n);
			if(num == -1)
				exit(1);
			s->leftchild = CreatInPost(post, is,num);//此处放进去的是线序遍历的前num个
			s->rightchild = CreatInPost(post+num, is+num +1, n-num-1);//此处减1是因为这是从后序遍历中找的每次最后一个数就被使用了，每次到这里就要将它除掉
			return s;
		}
		
	}

	static void PreOrder(TreeNode *root)
	{
		if(root != NULL)
		{
			cout << root->data << " ";
			PreOrder(root->leftchild);
			PreOrder(root->rightchild);
		}
	}
public:
	void Creat(Type *post, Type *is, int n)
	{
		if(post != NULL && is != NULL)
		root = CreatInPost(post, is, n);
	}
	void PreOrder()
	{
		PreOrder(root);
		cout << endl;
	}
};

int main(void)
{
	BinaryTree<int> tree;
	int post[] = {34,56,67,45,23,89,78,12};
	int is[] = {34,23,56,45,67,12,78,89};
	int n = sizeof(post) / sizeof(post[0]);
	
	tree.Creat(post, is, n);
	tree.PreOrder();

	return 0;
}

已知中序后序创建二叉树,布布扣,bubuko.com

已知中序后序创建二叉树

原文：http://blog.csdn.net/xiaomoniao/article/details/21553647