请高手赐教!!!一个算法的问题

Question

一个算法的问题:输入二叉树的前序遍历和中序遍历序列，怎样能生成此二叉树?
我想了一个算法都非常复杂.
希望您最好用pascal或者c语言给出一个简单经济的算法.
多谢赐教,承蒙关照!

Answer 1

算法思想
依次从前序遍历序列中取结点，每取出一个结点就与中序遍历序列中的各结点进行比较，当相等时，中序遍历序列便被分成以该结点为根结点的两棵子树，左部分为左子树，右部分为右子树。直至取完前序遍历序列中所有所有的结点，则该树构造完毕。
设树组A存放前序序列，B为中序序列。
算法描述如下：
TYPE node=RECORD
lchild,rchild:integer;
ch:char
END;
PROCEDURE ds(A:ARRAY[1..N] OF char;
             B:ARRAY[1..N] OF node);
VAR s:stack;
    top:integer;
    i,j,t:integer;
BEGIN
  top:=0;
  FOR i:+1 TO n DO
    BEGIN
      j:=1;
      WHILE B[i].ch<>A[i] DO
         j:=j+1;
      IF top=0
         THEN BEGIN 
                top:=top+1;
                s[top]:=j
              END
         ELSE IF j<s[top]
                 THEN BEGIN
                        B[s[top]].lchild:=j;
                        top:=top+1;
                        s[top]:=j
                      END
                 ELSE BEGIN
                        WHILE (j>s[top]) AND (top<>0) DO
                           BEGIN t:=s[top];
                                 top:=top-1
                           END;
                        B[t].rchild:=j;
                        top:=top+1;
                        s[top]:=j
                      END
   END
END;可直接运行ANSI C 
#include "stdio.h" struct node
 {
 char ch;
 int lchild,rchild;
 
 };
 void tree(char a[10],struct node b[11])
 {
  int s[10],top,i,j,t;
  top=-1;//stack empty
  for (i=0;i<10;i++)
  {
  j=0;
  while (b[j].ch!=a[i])
        j=j+1;
  if (top==-1)
  {
  top=top+1;
  s[top]=j;
}
  else if (j<s[top])
  {
  b[s[top]].lchild=j;
  top=top+1;
  s[top]=j;
  }
  else
  {
  while (j>s[top]&&top!=-1)
  {
  t=s[top];
  top=top-1;
  }
  b[t].rchild=j;
  top=top+1;
  s[top]=j;
  }
  }
  for (i=0;i<10;i++)
  {
  
  
  printf("%c leftchild-> %c rightchild-> %c\n",b[i].ch,b[b[i].lchild].ch,b[b[i].rchild].ch);
     //if (b[e].lchild!=-1)
  //printf("%d ",b[b[e].rchild],ch);
 //if (
      //printf("/n"); }
  getchar();
 }
void main()
{
struct node b[11]={{'c',10,10},{'b',10,10},{'e',10,10},{'d',10,10},{'a',10,10},{'h',10,10},{'g',10,10},{'i',10,10},{'j',10,10},{'f',10,10},{'^',0,0}};
char a[10]="abcdefghij";//测试用例子
tree(a,b);
}