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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
|
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
class BSTNode {
public:
int key;
BSTNode* lchild;
BSTNode* rchild;
BSTNode* parent;
BSTNode(int _key):lchild(nullptr), rchild(nullptr), parent(nullptr) {
key = _key;
}
};
/*
二叉查找树:
1. 首先是二叉树，每个节点最多有两个子树，称为“左子树”和“右子树”。二叉树还用于实现二叉堆。
2. 左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于跟节点的值。
平衡二叉树：AVL树，红黑树。
*/
class BSTree {
private:
// 销毁二叉树，使用后续遍历
void Destroy(BSTNode* node) {
if (node->lchild != nullptr)
Destroy(node->lchild);
if (node->rchild != nullptr)
Destroy(node->rchild);
delete node;
node = nullptr;
}
public:
BSTNode* root;
BSTree() {
root = nullptr;
}
~BSTree() {
Destroy(root);
}
// 插入节点，不允许插入值相等的元素
bool Insert(int key) {
BSTNode* parentNode = nullptr;
BSTNode* node = root;
// 先寻找合适的位置再插入
while (node != nullptr) {
parentNode = node;
if (key > node->key) {
node = node->rchild;
} else if (key < node->key) {
node = node->lchild;
} else {
return false;
}
}
node = new BSTNode(key);
// 父节点指向新节点，完成插入
if (parentNode == nullptr) {
root = node;
} else {
if (key > parentNode->key) {
parentNode->rchild = node;
} else {
parentNode->lchild = node;
}
}
node->parent = parentNode;
return true;
}
// 删除节点
void Remove(int key) {
BSTNode* node = root;
bool found = false;
// 当前节点是否为左节点
bool isLeft = false;
while (node != nullptr) {
// 找到要删除的节点
if (key > node->key) {
node = node->rchild;
isLeft = false;
} else if (key < node->key) {
node = node->lchild;
isLeft = true;
} else {
found = true;
break;
}
}
if (found) {
if (node->lchild == nullptr && node->rchild == nullptr) {
// 没有左节点，也没有右节点，直接删除，当前节点可能是root
if (node->parent == nullptr) {
root = nullptr;
} else {
if (isLeft) {
node->parent->lchild = nullptr;
} else {
node->parent->rchild = nullptr;
}
}
} else if (node->lchild == nullptr && node->rchild != nullptr) {
// 只有右节点，用右节点顶替，当前节点可能是root
if (node->parent == nullptr) {
root = node->rchild;
} else {
if (isLeft) {
node->parent->lchild = node->rchild;
} else {
node->parent->rchild = node->rchild;
}
}
} else if (node->lchild != nullptr && node->rchild == nullptr) {
// 只有左节点，用左节点顶替，当前节点可能是root
if (node->parent == nullptr) {
root = node->lchild;
} else {
if (isLeft) {
node->parent->lchild = node->lchild;
} else {
node->parent->rchild = node->lchild;
}
}
} else {
// 左右节点都存在，当前节点可能是root
// 两种方法：在左子树找到最大的节点来顶替；或者在右子树中找最小的来顶替
// 这里使用第二种方法，寻找node的右子树中最小节点m
BSTNode* m = node->rchild;
// m是否为左节点
bool mIsLeft = false;
while (m->lchild != nullptr) {
m = m->lchild;
mIsLeft = true;
}
// m可能有右节点，但一定没有左节点
if (mIsLeft) {
// 先剔除掉m
if (m->rchild == nullptr) {
m->parent->lchild = nullptr;
} else {
m->parent->lchild = m->rchild;
m->rchild->parent = m->parent;
}
} else {
// 先剔除掉m
if (m->rchild == nullptr) {
m->parent->rchild = nullptr;
} else {
m->parent->rchild = m->rchild;
m->rchild->parent = m->parent;
}
}
// 替换节点
m->lchild = node->lchild;
node->lchild->parent = m;
if (node->rchild == nullptr) {
m->rchild = nullptr;
} else {
m->rchild = node->rchild;
node->rchild->parent = m;
}
// 设置父节点
if (node->parent == nullptr) {
m->parent = nullptr;
root = m;
} else {
m->parent = node->parent;
if (isLeft) {
m->parent->lchild = m;
} else {
m->parent->rchild = m;
}
}
}
delete node;
}
}
// 层次遍历，相当于(BFS)广度优先遍历，一般用队列实现
void LevelOrder(BSTNode* node) {
queue<BSTNode*> q;
if (node != nullptr)
q.push(node);
BSTNode* t;
while (!q.empty()) {
t = q.front();
cout << t->key << " ";
q.pop();
if (t->lchild != nullptr)
q.push(t->lchild);
if (t->rchild != nullptr)
q.push(t->rchild);
}
}
// 前序遍历，相当于(DFS)深度优先遍历
// 如果不用递归，需要用栈来实现
void PreOrder(BSTNode* node) {
if (node != nullptr) {
cout << node->key << " ";
PreOrder(node->lchild);
PreOrder(node->rchild);
}
}
// 中序遍历
void InOrder(BSTNode* node) {
if (node != nullptr) {
InOrder(node->lchild);
cout << node->key << " ";
InOrder(node->rchild);
}
}
// 后续遍历
void PostOrder(BSTNode* node) {
if (node != nullptr) {
PostOrder(node->lchild);
PostOrder(node->rchild);
cout << node->key << " ";
}
}
// 查找
BSTNode* Find(int key) {
BSTNode* node = root;
while (node != nullptr) {
if (key < node->key)
node = node->lchild;
else if (key > node->key)
node = node->rchild;
else
return node;
}
return nullptr;
}
// 求二叉树的深度，根节点不为空时，深度为1+左右深度大的
int GetDepth(BSTNode* node) {
if (node == nullptr) return 0;
int nLeft = GetDepth(node->lchild);
int nRight = GetDepth(node->rchild);
return nLeft > nRight ? nLeft+1 : nRight+1;
}
// 求两个节点的最低公共祖先节点，此方法必须保证node1和node2已经在树中，否则答案有误
BSTNode* FindLCA(BSTNode* node, BSTNode* node1, BSTNode* node2) {
if (node == nullptr) return nullptr;
// 任何一个节点匹配即可
if (node == node1 || node == node2) return node;
BSTNode* left = FindLCA(node->lchild, node1, node2);
BSTNode* right = FindLCA(node->rchild, node1, node2);
// 如果都非空, 说明两个节点分别出现了在两个子树中，则当前节点肯定为LCA
if (left != nullptr && right != nullptr)
return node;
// 如果一个为空，在说明LCA在另一个子树
return left != nullptr ? left : right;
}
};
/*
--------------10------------------
------5---------------15----------
---1-----8-------12-------17------
-------------------13---------20--
*/
int main()
{
BSTree tree;
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Insert(1);
tree.Insert(8);
tree.Insert(12);
tree.Insert(17);
tree.Insert(13);
tree.Insert(20);
tree.PreOrder(tree.root);
cout << endl;
tree.InOrder(tree.root);
cout << endl;
tree.PostOrder(tree.root);
cout << endl;
tree.LevelOrder(tree.root);
cout << endl;
cout << tree.GetDepth(tree.root) << endl;
BSTNode* node1 = tree.Find(13);
BSTNode* node2 = tree.Find(17);
if (node1 != nullptr && node2 != nullptr) {
cout << tree.FindLCA(tree.root, node1, node2)->key << endl;
}
}
|