问题描述

　　给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=）。

输入格式

　　两行，每行一个字符串，分别表示中序和后序排列

输出格式

　　一个字符串，表示所求先序排列

　　样例输入

　　BADC

　　BDCA

样例输出

ABCD

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 char mid[],later[];    

 void tree(int l,int r,int start,int end)

 {

     int i;

     int temp = later[end];        //后序中的末尾为对应区间中序的根

     if (l>r || start>end)

         return ;

     else

     {

         printf("%c",temp);

         for (i=l ; i<=r ; i++)

         {

             if (temp == mid[i])    //寻找中序中的根结点

             {

                 tree(l,i-,start,start+(i--l));        //遍历中序左子树

                 tree(i+,r,start+(i-l-)+,end-);    //遍历中序右子树

                 return ;

             }

         }

     }    

     return ;

 }

 int main(void)

 {

     int len;

     scanf("%s",mid);    //输入中序

     scanf("%s",later);    //输入后序

     len = strlen(mid);

     tree(,len-,,len-);

     return ;

 }