求一个数据结构的经典算法！！课程设计啊，想了好久都没有想出来。

Question

已知中根遍历和前根遍历（或后根遍历），求这棵唯一确定的二叉树，可能我的描述不太好。比如说，已知两个字符串abc和bac分别是中根遍历和前根遍历，求这棵树，节点的结构体定义如下：
struct Btree
{
int data;
struct Btree *rchild,*lchild;
}

Answer 1

另外举一个例子，前序abecfg和中序beafcg。
前序先遍历根，故a为根，所以中序的be和fcg分别为左子树和右子树，前序对应是be和cfg，然后对左右子树用递归，很简单的：
struct Btree *tree(char *front,char *middle, int length)
//middle为中序遍历的字符串，front为前序遍历的字符串。
//length为字符串长度。
struct Btree *root,
//root为待建树的根结点
{
int position;
if(length>0)
{
root=(struct Btree *)malloc(sizeof(Btree));
root->data=front[0];//middle[0]是根
if(length!=1){//如果等于1，则已经完成该子树构建，否则需要递归构建左和右子树。
position=find(middle,front[0];//找到根在前序遍历中的位置，字符串第一个字符从零开始计算。
root->lchild=tree(front+1,middle,position);//中序遍历的左子树在根后面，而前序遍历则在根前，就是最前面，这个递归就可以构造左子树。注意子树对应的字符串长度缩小了。
root->rchild=tree(front+position,middle+positon+1,length-position-1);//构造右子树。
}
else
{
root->lchild=null;
root->rchild=null;
}//已完成构建，设置左右子树为空
else
root=null;//长度为零，说明该子树不存在，所以直接设置为空。
return(null);
}

Answer 2

我大一时候学的，主要背一些模式