数据结构实验之求二叉树后序遍历跟层次遍历

题目描述

输入

输出

示例输入

2
abdegcf
dbgeafc
xnliu
lnixu

示例输出

dgebfca
abcdefg
linux
xnuli

提示

来源

示例程序

1. #include<stdio.h>  
2. #include<string.h>  
3.   
4. char st1[100],st2[100];  
5.   
6. struct node  
7. {  
8.     char c;  
9.     struct node *lnext,*rnext;  
10. };  
11.   
12. void build(int n,char *s1,char *s2,struct node *&p)  
13. {  
14.   
15.     if(n<=0)  
16.         return ;  
17.     p=new node;  
18.     p->c=s1[0];  
19.     int num=strchr(s2,s1[0])-s2;  
20.     build(num,s1+1,s2,p->lnext);  
21.     build(n-num-1,s1+num+1,s2+num+1,p->rnext);  
22. }  
23.   
24. void last(struct node *t)  
25. {  
26.     if(t==NULL)  
27.         return ;  
28.     else  
29.     {  
30.         last(t->lnext);  
31.         last(t->rnext);  
32.         printf("%c",t->c);  
33.     }  
34. }  
35.   
36.   
37. void cengci(struct node *t)  
38. {  
39.     int s=0,e=0;  
40.     struct node *que[100100],*now,*tmp;  
41.     que[s++]=t;  
42.   
43.     while(s>e)  
44.     {  
45.         now=que[e++];  
46.         printf("%c",now->c);  
47.   
48.         tmp=now;  
49.         if(tmp->lnext!=NULL)  
50.             que[s++]=tmp->lnext;  
51.         if(tmp->rnext!=NULL)  
52.             que[s++]=tmp->rnext;  
53.     }  
54. }  
55.   
56. int main()  
57. {  
58.     int n;  
59.     scanf("%d%*c",&n);  
60.     while(n--)  
61.     {  
62.         scanf("%s%s",st1,st2);  
63.         int len=strlen(st1);  
64.         struct node *q;  
65.         build(len,st1,st2,q);  
66.         last(q);  
67.         printf("\n");  
68.         cengci(q);  
69.         printf("\n");  
70.     }  
71.     return 0;  
72. }  
73.