首页 > > 程序设计 > C/C++ >

3143 二叉树的序遍历

2018-06-17 22:57:04来源：未知阅读 ()

3143 二叉树的序遍历

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 白银 Silver

题目描述 Description

求一棵二叉树的前序遍历，中序遍历和后序遍历

输入描述 Input Description

第一行一个整数n，表示这棵树的节点个数。

接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。

输出描述 Output Description

输出一共三行，分别为前序遍历，中序遍历和后序遍历。编号之间用空格隔开。

样例输入 Sample Input

2 3

4 5

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 }