转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1299063032
提示：二叉树遍历而已。。。给出前序和中序，求后序
解题思路
1、前序遍历的第一个字母必是 根
2、在中序遍历的字母串中找出 根字母，那么根字母左右两边的字符串就分别是它的左、右子树
3、利用递归复原二叉树（把子树看作新的二叉树）
4、后序遍历特征：后序遍历字母串 自右至左 依次为：
最外层（总树，设为第0层）右子树的根，内1层右子树的根，内2层右子树的根….内n层右子树的根，内n层左子树的根，内n-1层左子树的根……内1层左子树的根，最外层（总树，第0层）左子树的根。把总树的左子树作为新的总树，继续递归即可。 （注意：总树的叶就是作为“单叶”这棵树本身的右根）
5、输出后序遍历时，只需按4的顺序从左到右排列，再倒置输出即可
1 //Memory Time
2 //180K 0MS
3
4 #include<iostream>
5 #include<cstring>
6 using namespace std;
7
8 char post[26];
9 int point=0;
10
11 void right_to_left(char preo[],char inor[])
12 {
13 post[point++]=preo[0]; //根
14
15 const int length=strlen(inor);
16 if(length==1)
17 return;
18 int j=0;
19 for(;j<length;j++)
20 if(inor[j]==preo[0])
21 break;
22 const int flag=j;
23 int i=++j;
24 char preo_temp[26],inor_temp[26];
25 bool tag=false;
26
27 for(j=0;i<length;++i,++j) //提取右子树中序
28 {
29 inor_temp[j]=inor[i];
30 tag=true;
31 }
32
33 if(tag)
34 {
35 inor_temp[j]='\0';
36 for(i=0,j=length-j;j<length;++i,++j) //提取右子树前序
37 preo_temp[i]=preo[j];
38 preo_temp[i]='\0';
39
40 right_to_left(preo_temp,inor_temp);
41 }
42 //↑↑↑↑↑
43 //处理右子树
44 //===============================================================
45 //处理左子树
46 //↓↓↓↓↓
47 tag=false;
48 for(i=0;i<flag;i++) //提取左子树中序
49 {
50 inor_temp[i]=inor[i];
51 tag=true;
52 }
53
54 if(tag)
55 {
56 inor_temp[i]='\0';
57 for(i=0,j=1;i<flag;++i,++j) //提取左子树前序
58 preo_temp[i]=preo[j];
59 preo_temp[i]='\0';
60
61 right_to_left(preo_temp,inor_temp);
62 }
63 return;
64 }
65
66 int main(void)
67 {
68 char preo[26],inor[26];
69
70 while(cin>>preo>>inor)
71 {
72 right_to_left(preo,inor);
73
74 for(--point;point>=0;point--)
75 cout<<post[point];
76 cout<<endl;
77
78 point=0;
79 }
80 return 0;
81 }