💐专栏导读

🌸作者简介：花想云，在读本科生一枚，致力于 C/C++、Linux 学习。

🌸本文收录于 C++系列，本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等，专为大学生打造全套 C++ 学习教程，持续更新！

🌸相关专栏推荐：C语言初阶系列 、C语言进阶系列 、数据结构与算法、Linux从入门到精通

💐文章导读

本章我们将认识一种新的二叉树——搜索二叉树。这棵树有个神奇的功能就是会对数据自动排序且有着非常高的查找效率。搜索二叉树作为set、map的基础结构，同样又是接下来将要学到的AVL树以及红黑树的实现基础非常值得我们去深入学习~

🌷搜索二叉树概念

二叉搜索树本质上也是一种二叉树，只不过多了一个约束规则——

若一棵二叉树不为空，则：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
• 它的左右子树也分别为搜索二叉树；

所以构建一个搜索二叉树，只需要在插入结点时满足约束规则即可。

🌷二叉搜索树的构建

与二叉树相同，二叉搜索树由一个个结点链接而成。每个结点包含三个成员——

• _left（左孩子）；
• _right（有孩子）；
• _key（键值）；

所以首先定义一个BSTNode（Binary Search Tree简写）结构体——

template <class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;

BSTreeNode(const K& key) // 构造函数
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

同样的，再定义一个搜索二叉树的类，即class BSTree——

template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
// 成员函数的实现
// 插入、删除、查找...
private:
Node* _root = nullptr;
};
1
2
3
4
5
6
7
8
9
10

接着就是各种成员函数的实现了~

🌺查找操作

搜索二叉树的查找比较简单而且更容易帮助我们理解搜索二叉树的性质，所以先从查找入手。

以上图为例，倘若我们要查找 7，具体的思路是这样的——

1. 7 < 8，因此去 8 的左子树去查找；
2. 7 > 3，因此去 3 的右子树去查找；
3. 7 > 6，因此去 6 的右子树去查找；
4. 7 = 7，找到了，返回true；

于是我们试着着手实现一个Find函数。

bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key) // 大于则去右子树查找
cur = cur->_right;
else if (cur->_key > key) // 小于则去左子树查找
cur = cur->_left;
else
return true; // 找到返回true
}
return false; // 未找到返回false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

🌺插入操作

理解了如何查找，插入也就非常简单。

还是以此图为例，倘若我们要插入 9 ，具体步骤为——

1. 首先确定cur的位置，并随时更新parent；
2. 最终，cur走到10的左节点的位置，即cur = nullptr，循环结束；
3. 此时patent = Node*(10)；
4. 最后一步，new一个结点Node*(key)并赋值给parent->_left即可。

bool Insert(const K& key)
{
// 如果是第一次插入，直接new一个新结点给_root
if (_root == nullptr)
{
_root = new Node(key);
return true;
}

Node* cur = _root; // cur用来定位插入的位置
Node* parent = cur; // 记录parent的父亲

while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if(cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 插入
cur = new Node(key);
// 插入时依旧要进行判断
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
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

🌺删除操作

二叉搜索树的删除是最精华的部分。对与叶子节点，例如4、7、13，删除非常简单，只需将自身的位置替换为nullptr即可。

如果要删除14或者10，也是比较简单的，因为10的左右子树只有一方为nullptr（10的左子树为空），所以只需要载删除的时候让父结点接管自己不为空的子树即可。

倘若要删除6或者3，由于它们的左右子树都不为空，删除时无法将两个子树都交给父结点，情况就较为复杂。

所以此种情况，我们只能想办法请一个人来接替自己的位置，但是并不是谁来都能胜任这个位置的。这个接替者必须满足二叉搜索树的条件——左子树都比它小，右子树都比它大。那么这个接替者的人选只能有这两个——

• 左子树的最大（最右）节点；
• 或右子树的最小（最左）节点；

例如，倘若要删除3，此时有两种做法都可行——

1. 用1替换3；
2. 用7替换3；

综上所述，删除操作共分为一下几种情况——

1. 左子树为空；
2. 右子树为空；
3. 左右子树都不为空 ；
4. （左右子树都为空其实可以归并到1或2的情况中）；

bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = cur;
while (cur)
{
// 找到值为key的结点
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 找到了
{
// 删除
if (cur->_left == nullptr) // 1.左子树为空
{
if (cur == _root) // 根节点的删除
{
_root = cur->_right;
return true;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
}
}
else if (cur->_right == nullptr) // 2.右子树为空
{
if (cur == _root) // 根节点的删除
{
_root = cur->_left;
return true;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
}
}
else // 左右子树都不为空
{
// 找左子树的最大结点 或者 右子树的最小结点
Node* minRight = cur->_right;
Node* pminRight = cur;

while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}

cur->_key = minRight->_key; // 替换

if (pminRight->_left == minRight)
{
pminRight->_left = minRight->_right;
}
else
{
pminRight->_right = minRight->_right;
}

delete minRight;
}
return true;
}
}
return false;
}
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

🌺遍历操作

最后，二叉搜索树的遍历非常简单，就是之前学习过的二叉树的中序遍历。

void InOrder()
{
_InOrder(_root);
cout << endl;
}

void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ' ';
_InOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注：由于调用函数时C++封装的特性，需设计两个函数，InOrder接口对外提供，-—_InOrder不对外提供。

☘️测试

我们可以构建一棵这样的搜索二叉树，再对每一个结点进行删除操作，验证代码是否正确~

void BTreeTest()
{
BSTree<int> tree;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
tree.InsertR(e);
}

for (auto e : a)
{
tree.EraseR(e);
tree.InOrder();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🏵️拓展——递归实现

对于搜索二叉树来说，上面实现的非递归版本是比递归版本更优的。此处的递归实现完全属于多余了，但是作为拓展内容看一看也未尝不可。

🍃递归查找

bool FindR(const K& key)
{
return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key == key)
return true;
if (root->_key > key)
_FindR(root->_left, key);
else
_FindR(root->_right, key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

🍃递归插入

bool EraseR(const K& key)
{
return _EraseR(_root, key);
}

bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
return _InsertR(root->_right, key);
else if (root->_key > key)
return _InsertR(root->_left, key);
else
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🍃递归删除

bool EraseR(const K& key)
{
return _EraseR(_root, key);
}

bool _EraseR(Node*& root,const K& key)
{
if (root == nullptr)
return false;
if (root->_key < key)
return _EraseR(root->_right, key);
else if (root->_key > key)
return _EraseR(root->_left, key);
else
{
Node* del = root;
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{
Node* maxLeft = root->_left;
while (maxLeft->_right)
maxLeft = maxLeft->_right;
std::swap(root->_key, maxLeft->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
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

❄️完整源码

🐙非递归版

#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;

BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};

template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() = default;
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}

Node* cur = _root;
Node* parent = cur;

while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if(cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 插入
cur = new Node(key);
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}

bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key > key)
cur = cur->_left;
else
return true;
}
return false;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 删除
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
return true;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
}
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
return true;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
}
}
else
{
// 找左子树的最大结点 或者 右子树的最小结点
Node* minRight = cur->_right;
Node* pminRight = cur;

while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}

cur->_key = minRight->_key;
if (pminRight->_left == minRight)
{
pminRight->_left = minRight->_right;
}
else
{
pminRight->_right = minRight->_right;
}

delete minRight;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
protected:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ' ';
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
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

🐌递归版本

#pragma once
#include<iostream>
using namespace std;

template <class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;

BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};

template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() = default;
void InOrder()
{
_InOrder(_root);
cout << endl;
}

bool FindR(const K& key)
{
return _FindR(_root, key);
}

bool InsertR(const K& key)
{
return _InsertR(_root, key);
}

bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
protected:
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key == key)
return true;
if (root->_key > key)
_FindR(root->_left, key);
else
_FindR(root->_right, key);
}
bool _EraseR(Node*& root,const K& key)
{
if (root == nullptr)
return false;
if (root->_key < key)
return _EraseR(root->_right, key);
else if (root->_key > key)
return _EraseR(root->_left, key);
else
{
Node* del = root;
if (root->_left == nullptr)
root = root->_right;
else if (root->_right == nullptr)
root = root->_left;
else
{
Node* maxLeft = root->_left;
while (maxLeft->_right)
maxLeft = maxLeft->_right;
std::swap(root->_key, maxLeft->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}

bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
return _InsertR(root->_right, key);
else if (root->_key > key)
return _InsertR(root->_left, key);
else
return false;
}

void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ' ';
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
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

⭐抽奖活动⭐

抽奖文章链接——Spring Cloud——演进与应用的分布式系统开发利器（文末赠书3册）

⭐感谢赞助⭐

618，清华社 IT BOOK 多得图书活动开始啦！活动时间为2023年6月7日至6月18日，清华社为您精选多款高分好书，涵盖了C++、Java、Python、前端、后端、数据库、算法与机器学习等多个IT开发领域，适合不同层次的读者。全场5折，扫码领券更有优惠哦！

优惠购书请戳这里