标签

题目描述

二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入格式

两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出

输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

样例输入

ABC
CBA
ABCDEFG
DCBAEFG

样例输出

CBA
DCBGFEA

 1 #include <stdio.h> 2 #include <string.h> 3 int postrun(char s1[],char s2[]) 4 { 5     int len; 6     len=strlen(s1); 7     char st1[30],st2[30];//存放左右子树  8     if(len<=1) 9     {10         printf("%s",s1);//最后只有一个值时，后面还是有‘\0’。所以仍然输出字符串 ,另外当s1为空时 也会输出 。可修改 11         return 0;12     }13     int i,j,mid;14     for(i=0;i<len;i++)15     {16         if(s1[0]==s2[i])   //查找s1根结点在s2中的位置，则在s2中，其左为左子树，其右为右字数17             break; 18     }19     mid=i;20     for(i=0;i<mid;i++)21     {22         st1[i]=s1[i+1];23         st2[i]=s2[i];     //两颗左子树 24         25     }26     st1[i]=st2[i]=‘\0‘;27     postrun(st1,st2);28     for(i=0;i<(len-mid-1);i++)29     {30         st1[i]=s1[mid+1+i];31         st2[i]=s2[mid+1+i];32     }33     st1[i]=st2[i]=‘\0‘;34     postrun(st1,st2);35     printf("%c",s1[0]);36     37     38     39 }40 int main(void)41 {42     char str1[30];43     char str2[30];44     while(gets(str1)&&gets(str2))45     {46         postrun(str1,str2);47         printf("\n");48     }49     50     return 0;51 }

 1 #include <stdio.h> 2 #include <string.h> 3 int postrun(char s1[],char s2[])//s1为后序，s2为中序  4 { 5     int len; 6     len=strlen(s1); 7     char st1[30],st2[30];//存放左右子树  8     if(len<=1) 9     {10         printf("%s",s1);//最后只有一个值时，后面还是有‘\0’。所以仍然输出字符串 ,另外当s1为空时 也会输出 。可修改 11         return 0;12     }13     int i,j,mid;14     for(i=0;i<len;i++)15     {16         if(s1[len-1]==s2[i])   //查找s1根结点在s2中的位置，则在s2中，其左为左子树，其右为右字数17             break; 18     }19     mid=i;20     for(i=0;i<mid;i++)21     {22         st1[i]=s1[i];23         st2[i]=s2[i];     //两颗左子树 24         25     }26     st1[i]=st2[i]=‘\0‘;27     printf("%c",s1[len-1]);28     postrun(st1,st2);29     for(i=0;i<(len-mid-1);i++)30     {31         st1[i]=s1[mid+i];32         st2[i]=s2[mid+1+i];33     }34     st1[i]=st2[i]=‘\0‘;35     postrun(st1,st2);36     37     38     39     40 }41 int main(void)42 {43     char str1[30];44     char str2[30];45     while(gets(str1)&&gets(str2))46     {47         postrun(str1,str2);48         printf("\n");49     }50     51     return 0;52 }