rebuild.cpp

给一棵结点编号为1, 2, …, n 的二叉树的前序遍历序列和中序遍历序列

#include"rebuild.h"
Bintree* CreateTree(int *pre,int *in,int n,int* flag)
{
	Bintree *ptr;
	int *pos;
	int k;	
	if(n<=0)
		return NULL;
	ptr=(Bintree *)malloc(sizeof(Bintree));
	if (!ptr)	exit(OUT_OF_MEM);
	ptr->data=*pre;
	for(pos=in;pos<in+n;pos++)
	{
		if(*pos==*pre)
			break;
	}
	if(pos==in+n)
	{
		*flag=0;
		return(NULL);
	}
	k=pos-in;
	ptr->lchild=CreateTree(pre+1,in,k,flag);
	if(*flag==0)
		return(NULL);
	ptr->rchild=CreateTree(pre+k+1,pos+1,n-1-k,flag);
	if(*flag==0)
		return(NULL);
	return(ptr);
}

void PostorderTraversal(Bintree* b)
{
	if (b!=NULL)	
	{
		PostorderTraversal(b->lchild);	//左子树
		PostorderTraversal(b->rchild); //右子树			
		printf("%d ",b->data);//根结点
	}
}