這是一個樹的遍歷轉(zhuǎn)換問題，已知樹的前序遍歷和中序遍歷，求出樹的后序遍歷。一開始的想法是先利用前序遍歷和中序遍歷，構(gòu)造出二叉樹，再對這個二叉樹進行后序遍歷輸出但
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 typedef struct node{
5 char e;
6 struct node *l,*r;
7 }*tree;
8 tree t;
9 char s1[27],s2[27];
10 tree create(int pa,int pb,int ia,int ib);
11 void postorder(tree T);
12 int main()
13 {
14 int len;
15 while(scanf("%s%s",s1,s2) != EOF){
16 len = strlen(s1);
17 t = create(0,len-1,0,len-1);
18 postorder(t);
19 printf("\n");
20 }
21 system("pause");
22 return 0;
23 }
24 tree create(int pa,int pb,int ia,int ib)
25 {
26 int i;
27 tree T;
28 if(pa <= pb && ia <= ib){
29 T = (tree)malloc(sizeof(struct node));
30 T->e = s1[pa];
31 for(i = ia;i <= ib;i++){
32 if(s1[pa] == s2[i])break;
33 }
34 int len1 = i - ia;
35 T->l = create(pa+1,pa+len1,ia,i-1);
36 T->r = create(pa+len1+1,pb,i+1,ib);
37 }
38 else
39 T = NULL;
40 return T;
41 }
42 void postorder(tree T)
43 {
44 if(T != NULL){
45 postorder(T->l);
46 postorder(T->r);
47 printf("%c",T->e);
48 }
49 }
50
是后來在網(wǎng)上看到一些大牛的作法：直接利用遞歸，就可以后序輸出結(jié)果這
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 char s1[27],s2[27];
5 void createprint(int pa,int pb,int ia,int ib);
6 int main()
7 {
8 int len;
9 while(scanf("%s%s",s1,s2) != EOF){
10 len = strlen(s1);
11 createprint(0,len-1,0,len-1);
12 printf("\n");
13 }
14 system("pause");
15 return 0;
16 }
17 void createprint(int pa,int pb,int ia,int ib)
18 {
19 int i;
20 if(pa == pb){
21 printf("%c",s1[pa]);
22 return;
23 }
24 if(pa > pb || ia > ib)return;
25 for(i = ia;i <= ib;i++)
26 if(s1[pa] == s2[i])break;
27 int len1 = i - ia;
28 createprint(pa+1,pa+len1,ia,i-1);
29 createprint(pa+len1+1,pb,i+1,ib);
30 printf("%c",s1[pa]);
31 }
32
是太巧妙了，可以省略掉建樹這一步。這道題的代碼雖然不長，也可以因此減少幾乎一半的代碼。我還得好好體會體會。