手撕BST
题目描述:
对一棵初始为空的二叉查找树 (Binary Search Tree, BST) 进行若干插入或删除操作, 请输出最后的二叉查找树.
graph TB
5
5-->3
5-->7
3-->1
3-->4
1-->null
1-->2
7-->6
7-->9
9-->8
9-->10
输入:
输入第一行为一个整数 $ T $, 表示操作数目. 随后 $ T $ 行,每行为 Insert K (表示插入整数K) 或 Remove K (表示删除整数K).
$ T $ 不超过 $ 2 \times 10^5 $, 树高不超过 $ 10^4 $.
输出:
输出经上述操作后得到的二叉查找树的中根序列和先根序列, 序列中每个整数后一个空格 (包括最后一个), 两个序列之间用空行间隔 (最后也要有个空行).
输入样例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 16
Insert 17
Insert 31
Insert 13
Insert 11
Insert 20
Insert 35
Insert 25
Insert 8
Insert 4
Insert 11
Insert 24
Insert 40
Insert 27
Insert 9
Remove 17
Remove 13
|
输出样例:
1
2
3
| 4 8 9 11 20 24 25 27 31 35 40
20 11 8 4 9 31 25 24 27 35 40
|
C++
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
struct Node {
int data;
Node *left, *right;
explicit Node(const int& data) {
left = right = nullptr;
this->data = data;
}
};
class BSTree {
private:
Node* root = nullptr;
public:
BSTree() = default;
explicit BSTree(const int& data) {
root = new Node(data);
}
~BSTree() {
destroy(root);
}
bool insert(const int& data) {
if (root == nullptr) {
root = new Node(data);
return true;
}
Node *parent = nullptr, *cur = root;
while (cur != nullptr) {
if (cur->data < data) {
parent = cur;
cur = cur->right;
}
else if (cur->data > data) {
parent = cur;
cur = cur->left;
}
else
return false;
}
cur = new Node(data);
if (parent->data > data)
parent->left = cur;
else
parent->right = cur;
return true;
}
bool remove(const int& data) {
Node *parent = nullptr,
*cur = root;
while (cur != nullptr) {
if (cur->data > data) {
parent = cur;
cur = cur->left;
}
else if (cur->data < data) {
parent = cur;
cur = cur->right;
}
else {
if (cur->left == nullptr) {
if (parent == nullptr)
root = root->right;
else {
if (cur == parent->left)
parent->left = cur->right;
else
parent->right = cur->right;
}
delete cur;
}
else if (cur->right == nullptr) {
if (parent == nullptr)
root = root->left;
else {
if (cur == parent->left)
parent->left = cur->left;
else
parent->right = cur->left;
}
delete cur;
}
else {
auto minNodeParent = cur;
auto minNode = cur->right;
while (minNode->left != nullptr) {
minNodeParent = minNode;
minNode = minNode->left;
}
std::swap(cur->data, minNode->data);
if (minNodeParent->left == minNode)
minNodeParent->left = minNode->right;
else
minNodeParent->right = minNode->right;
delete minNode;
}
return true;
}
}
return false;
}
std::vector<int> preOrder() {
auto res = std::vector<int>();
preOrder(this->root, res);
return res;
}
std::vector<int> inOrder() {
auto res = std::vector<int>();
inOrder(this->root, res);
return res;
}
private:
static void destroy(Node* root) {
if (root == nullptr) {
delete (root->left);
delete (root->right);
delete root;
}
}
void inOrder(const Node* root, std::vector<int>& res) {
if (root != nullptr) {
if (root->left != nullptr)
inOrder(root->left, res);
res.push_back(root->data);
if (root->right != nullptr)
inOrder(root->right, res);
}
}
void preOrder(const Node* root, std::vector<int>& res) {
if (root != nullptr) {
res.push_back(root->data);
if (root->left != nullptr)
preOrder(root->left, res);
if (root->right != nullptr)
preOrder(root->right, res);
}
}
};
using std::cin;
using std::cout;
using std::endl;
int main() {
int T, data;
cin >> T;
BSTree root;
char order[7];
for (int i = 0; i < T; i++) {
scanf("%s %d", order, &data);
if (std::strcmp(order, "Insert") == 0)
root.insert(data);
if (std::strcmp(order, "Remove") == 0)
root.remove(data);
}
size_t size;
auto inOrder = root.inOrder();
size = inOrder.size();
for (int i = 0; i < size; i++)
cout << inOrder[i] << ' ';
auto preOrder = root.preOrder();
size = preOrder.size();
cout << endl
<< endl;
for (int i = 0; i < size; i++)
cout << preOrder[i] << ' ';
cout << endl;
}
|
写在最后
本答案是应 Mao-Bro 写的答案题解.
Mro-Bro 是来自 JLU 的高材生, 因为近期课业繁忙, 不得不出此下策让我替他写几道题.
不过也好, 正好锻炼一下我的编码能力. 如果有兴趣, 大家可以在 GitHub 上关注一下他.
为了保护他的个人隐私, 这里就不贴他的照片了.
今个是破题, 文章还在后头呢
2023-04-21
IP属地: 北京