题目描述
已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历。
输入
输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的先序遍历序列，第二个字符串表示二叉树的中序遍历序列。
输出
每组第一行输出二叉树的后序遍历序列，第二行输出二叉树的层次遍历序列
示例输入
2
abdegcf
dbgeafc
xnliu
lnixu
示例输出
dgebfca
abcdefg
linux
xnuli
1 #include<stdio.h>
2 #include<
string.h>
3 #include<stdlib.h>
4 struct tree
5 {
6 char data;
7 struct tree *lchild,*
rchild;
8 };
9 struct tree *creat(
struct tree *root,
int len,
char *s1,
char *
s2 )
10 {
11 if(len==
0)
12 {
13
14 return NULL;
15 }
16 root=(
struct tree *)malloc(
sizeof(
struct tree));
17 root->data=s1[
0];
18 char *
p;
19 for(p=s2;p!=NULL;p++
)
20 if(*p==*
s1)
21 break;
22 int k=p-
s2;
23 root->lchild=creat(root->lchild,k,s1+
1,s2);
24 root->rchild=creat(root->rchild,len-
1-k,s1+k+
1,s2+k+
1);
25 return root;
26 }
27 void posorder(
struct tree *
root)
28 {
29 if(root)
30 {
31 posorder(root->
lchild);
32 posorder(root->
rchild);
33 printf(
"%c",root->
data);
34 }
35 }
36 void enqueue(
struct tree *
root)
37 {
38 int front=
0,rear=
1;
39 struct tree *q[
100],*
p;
40 q[
0]=
root;
41 while(front<
rear)
42 {
43 p=q[front++
];
44 printf(
"%c",p->
data);
45 if(p->lchild!=NULL) q[rear++]=p->
lchild;
46 if(p->rchild!=NULL) q[rear++]=p->
rchild;
47 }
48 printf(
"\n");
49 }
50 void delqueue(
struct tree *
root)
51 {
52 if(root==NULL)
return;
53 delqueue(root->
lchild);
54 delqueue(root->
rchild);
55 free(root);
56 }
57 int main ()
58 {
59 int t,len;
60 struct tree *
root;
61 char pre[
1001],
in[
1001];
62 scanf(
"%d",&
t);
63 while(t--
)
64 {
65 scanf(
"%s %s",pre,
in);
66 len=
strlen(pre);
67 root=creat(root,len,pre,
in);
68 posorder(root);
69 printf(
"\n");
70 enqueue(root);
71 delqueue(root);
72 }
73 return 0;
74 }
75
76
View Code
转载于:https://www.cnblogs.com/LK1994/p/3161691.html
