1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include <iostream>
#include <vector>
#include <algorithm>
using std::vector;
using std::ios_base;
using std::cin;
using std::cout;
class TreeOrders {
int n;
vector <int> key;
vector <int> left;
vector <int> right;
public:
void read() {
cin >> n;
key.resize(n);
left.resize(n);
right.resize(n);
for (int i = 0; i < n; i++) {
cin >> key[i] >> left[i] >> right[i];
}
}
vector <int> in_order() {
vector<int> result;
in_order_visit(0, result);
return result;
}
vector <int> pre_order() {
vector<int> result;
pre_order_visit(0, result);
return result;
}
vector <int> post_order() {
vector<int> result;
post_order_visit(0, result);
return result;
}
private:
void in_order_visit(int n, vector<int> &r)
{
if (left[n] != -1)
in_order_visit(left[n], r);
r.push_back(key[n]);
if (right[n] != -1)
in_order_visit(right[n], r);
}
void pre_order_visit(int n, vector<int> &r)
{
r.push_back(key[n]);
if (left[n] != -1)
pre_order_visit(left[n], r);
if (right[n] != -1)
pre_order_visit(right[n], r);
}
void post_order_visit(int n, vector<int> &r)
{
if (left[n] != -1)
post_order_visit(left[n], r);
if (right[n] != -1)
post_order_visit(right[n], r);
r.push_back(key[n]);
}
};
void print(vector <int> a) {
for (size_t i = 0; i < a.size(); i++) {
if (i > 0) {
cout << ' ';
}
cout << a[i];
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
TreeOrders t;
t.read();
print(t.in_order());
print(t.pre_order());
print(t.post_order());
return 0;
}
|
