时间限制: 1 s
空间限制: 32000 KB
题目等级 : 白银 Silver
题目描述 Description
求一棵二叉树的前序遍历,中序遍历和后序遍历
输入描述 Input Description
第一行一个整数n,表示这棵树的节点个数。
接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。
输出描述 Output Description
输出一共三行,分别为前序遍历,中序遍历和后序遍历。编号之间用空格隔开。
样例输入 Sample Input
5
2 3
4 5
0 0
0 0
0 0
样例输出 Sample Output
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
1 #include<iostream>
2 using namespace std;
3 int root;
4 struct node
5 {
6 int parent;
7 int date;
8 int lchild;
9 int rchild;
10 }a[101];
11 void xianxu(int i)
12 {
13 cout<<i<<" ";
14 if(a[i].lchild!=0)
15 {
16 xianxu(a[i].lchild);
17 }
18 if(a[i].rchild!=0)
19 {
20 xianxu(a[i].rchild);
21 }
22 }
23 void zhongxu(int i)
24 {
25 if(a[i].lchild!=0)
26 {
27 zhongxu(a[i].lchild);
28 }
29 cout<<i<<" ";
30 if(a[i].rchild!=0)
31 {
32 zhongxu(a[i].rchild);
33 }
34 }
35 void houxu(int i)
36 {
37
38 if(a[i].lchild!=0)
39 {
40 houxu(a[i].lchild);
41 }
42 if(a[i].rchild!=0)
43 {
44 houxu(a[i].rchild);
45 }
46 cout<<i<<" ";
47 }
48 int main()
49 {
50 int n;
51 cin>>n;
52 for(int i=1;i<=n;i++)
53 {
54 cin>>a[i].lchild>>a[i].rchild;
55 a[a[i].lchild].parent=i;
56 a[a[i].rchild].parent=i;
57 }
58 for(int i=1;i<=n;i++)
59 {
60 if(a[i].parent==0)
61 {
62 root=i;
63 }
64 }
65 xianxu(root);
66 cout<<endl;
67 zhongxu(root);
68 cout<<endl;
69 houxu(root);
70 return 0;
71 }