【问题描述】已知一棵二叉树的先序和中序遍历，可以求它的后序遍历，相应的，已知一棵二叉树的后序和中序遍历，也能求它的先序遍历。然而给定一棵二叉树的先序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
        a             a                 a                         a
     b            b                          b                        b
 c                    c                 c                                  c
所有的这些二叉树都有着相同的先序和后续遍历，但中序遍历却不相同。
【输入】输入数据共两行，第一行表示该二叉树的先序遍历结果s1，第二行表示该二叉树的后续遍历结果s2。
【输出】输出可能的中序遍历序列的总数，结果不超过长整型数。
【样例】
      travel.in
      abc
      bca

      travel.out
      4

相应的PASCAL语言代码如下：
program E2_3;{Travel}
var s1,s2:string;  {存放原始输入的先序遍历和后续遍历结果}
procedure init;    {初始化，读入两个字符串}
begin
  assign(input,'tranel.in');reset(input);
  readln(s1);readln(s2);close(input);
end;
Function check(f,l:string):boolean;
var i:byte;
begin
  if lenght(f)=0 then check:=true  {空字符串也认为符合条件}
  else
    begin
      check:=true;
      check:=f[l]=l[lenght(l)];  {对比F的首字符和L的尾字符}
      for i:=2 to lenght(f) do   {检查其他字符在F中有的L中也是否有}
      if pos(f[i],l)=0 then check:=false;
    end;
end;
Function count(first,last:string):longint;
var i,len:byte; t:longint
    lf,ll,rf,rl:string;
begin
  if len<=1 then count:=1  {只有1个或0个字符时返回结果1}
     else
       begin
         len:=lenght(last); t:=0;
         for i:=len-1 downto 0 do
           begin
             lf:=copy(first,2,i);  {取先序的左子串}
             ll:=copy(last,l,i);   {取后序的左子串}
             rf:=copy(first,i+2,len-l-i);  {取先序的右子串}
             rl:=copy(last,i+1,len-l-i);   {取后序的右子串}
             if check(lf,ll) and check(rf,rl) then
             t:=t+count(lf,ll)*count(rf,rl);  {递归调用；分布相乘；分类相加}
           end;
       count:=t;
      end;
end;
begin  {main}
  init;
  assign(output,'travel.out');rewrite(output);
  writeln(count(s1,s2));close(output)
end.

能不能把这个代码翻译成C语言代码，谢谢啦。

懂原理就行，树形结构比较麻烦点

木有啊

[ 本帖最后由 hsmiaomiao 于 2011-4-13 14:09 编辑 ]

就是，我对C语言比较犯怵