由前序和中序遍历构建一颗二叉树

这个算法本身是存在问题的，不细究。等大四我再写一个完善的算法。考试的时候可以写这个算法，思路没错，但是有种特殊情况这个算法没考虑。

#include<iostream>
#include<malloc.h>
using namespace std;
struct Betree{
	char c;
	Betree *lchild,*rchild;
};
char fore[100],mid[100];
void preorder(Betree *t)
{
	if(t==NULL)
		return;
	else {
		cout<<t->c<<" ";
		preorder(t->lchild);
		preorder(t->rchild);
	}
}
Betree* creatBt(int i,int j,int x,int y)
{
	if(i>j||x>y)
		return NULL;
	else {
		Betree* t=(Betree*)malloc(sizeof(Betree));
		t->c=fore[i];
		int L,k;
		k=x;
		while(fore[i]!=mid[k])
			k=k+1;
		L=k-x;
		if(k==x)
			t->lchild=NULL;
		else t->lchild=creatBt(i+1,i+L,x,k-1);
		if(k==y)
			t->rchild=NULL;
		else t->rchild=creatBt(i+L+1,j,x+L+1,y);
		return t;
	}
}
int main()
{
	int n,i;
	while(1)
	{
		cin>>n;
		Betree* tree=0;
		for(i=1;i<=n;i++)
			cin>>fore[i];
		for(i=1;i<=n;i++)
			cin>>mid[i];
		tree=creatBt(1,n,1,n);
		preorder(tree);
		cout<<endl;
	}
	return 0;
}

由前序和中序遍历构建一颗二叉树

原文：http://blog.csdn.net/killer_in_silence/article/details/19920843