（先序和中序遍历创建二叉树）或者（中序和后序遍历创建二叉树）

#include
#include
#include
#include 
#define ElemType int
using namespace std;
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}TNode,*Tree;
int treenum[]={1,2,4,0,0,5,0,0,3,0,0};
int k;
void createTree(Tree &T,int &k)
{
	ElemType n;
//	printf("输入为0停止！\n"); 
//	scanf("%d",&n);
	if(treenum[k]==0){
		T=NULL;
		k++;
	}
	else{
		T=new TNode;
		T->data=treenum[k];
		k++;
//		cout<<"T="<data<<"k="<lchild,k);
		createTree(T->rchild,k);
	}
}
//先序遍历 
int PreTree(Tree &T)
{
	if(T==NULL){
		return 0;
	}
	else{
		cout<data;
		PreTree(T->lchild);
		PreTree(T->rchild); 
	}
}
//中序和先序构建二叉树 
Tree PreInCreat(ElemType Pre[],ElemType In[],int PreBegin,int PreEnd,int InBegin,int InEnd){
	if(PreBegin>PreEnd){ //结束条件：“当前节点为叶子节点”
		return NULL; 
	}
//	if(PreBegin>PreEnd){ 
//		return NULL; 
//	}
	TNode *node=new TNode;
	node->data=Pre[PreBegin];
	int index=0;
	for(int i=InBegin;i<=InEnd;i++) //中序遍历得index 
	{
		if(In[i]==Pre[PreBegin]){
			index=i;
			break;
		}
	}
	node-> lchild = PreInCreat(Pre,In,PreBegin+1, PreBegin+index-InBegin, InBegin, index-1);//递归求左 
	node-> rchild = PreInCreat(Pre,In,PreBegin+index-InBegin+1, PreEnd, index+1, InEnd);//递归求右 
	return node;	
}
//中序和后序构建二叉树 
Tree PostInCreat(ElemType Post[],ElemType In[],int PostBegin,int PostEnd,int InBegin,int InEnd){
	if(PostBegin>PostEnd||InBegin>InEnd){ //结束条件：“当前节点为叶子节点”
		return NULL; 
	}
	TNode *node=new TNode;
	node->data=Post[PostEnd];
	int index=0;
	for(int i=InBegin;i<=InEnd;i++) //中序遍历得index 
	{
		if(In[i]==Post[PostEnd]){
			index=i;
			break;
		}
	}
	node-> lchild = PostInCreat(Post,In,PostBegin, PostBegin+index-InBegin-1, InBegin, index-1);//递归求左 后序+的是左孩子个数 
	node-> rchild = PostInCreat(Post,In,PostBegin+index-InBegin, PostEnd-1, index+1, InEnd);//递归求右  //后序+有孩子个数 
	return node;	
}
int main()
{
	Tree T;
	ElemType Pre[]={1,2,4,5,3};
	ElemType Inter[]={4,2,5,1,3};
	ElemType Post[]={4,5,2,3,1};
	int PreBegin=0;
	int PreEnd=4;
	int InBegin=0;
	int InEnd=4;
	int PostBegin=0;
	int PostEnd=4;
//	T=PreInCreat(Pre,Inter,PreBegin,PreEnd,InBegin,InEnd);
	T=PostInCreat(Post,Inter,PostBegin,PostEnd,InBegin,InEnd);
	PreTree(T);
	return 0;
}