3540. 二叉搜索树
摘要
Title: 3540. 二叉搜索树
Tag: BST
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3540. 二叉搜索树
-
题意
输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。
-
思路
用数组模拟链表，即用数组下标模拟为链表节点的地址
判断val是否为0，是判断节点是否空的依据 -
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2022-08-11 11:48:28
* @FilePath: \Acwing\3540\3540.cpp
* @LastEditTime: 2022-08-13 09:58:07
*/
using namespace std;
typedef pair<int, int> PII;
const int INF = INT_MAX;
const int N = 1e6 + 10;
signed main()
{
IOS;
int n;
cin >> n;
struct sa
{
int l, r, val;
};
vector<sa> tr(n + 100);
// 1是根节点的链表结点
int root, idx = 1;
cin >> root;
tr[idx++].val = root;
function<void(int, int)> insert = [&](int u, int x) {
if (!tr[u].val)
{
tr[u].val = x;
return;
}
// 相当于创建空结点
if (!tr[u].l)
tr[u].l = idx++;
if (!tr[u].r)
tr[u].r = idx++;
if (x < tr[u].val)
insert(tr[u].l, x);
if (x > tr[u].val)
insert(tr[u].r, x);
};
function<void(int, int)> dfs = [&](int u, int p) {
if (p == 1)
cout << tr[u].val << " ";
if (tr[tr[u].l].val)
dfs(tr[u].l, p);
if (p == 2)
cout << tr[u].val << " ";
if (tr[tr[u].r].val)
dfs(tr[u].r, p);
if (p == 3)
cout << tr[u].val << " ";
};
for (int i = 1; i < n; i++)
{
int x;
cin >> x;
insert(1, x);
}
for (int i = 1; i <= 3; ++i)
{
dfs(1, i);
cout << '\n';
}
return 0;
}