【C++】学习笔记——二叉搜索树

---

十四、二叉搜索树

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

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

二叉搜索树的查找非常方便，最多查找 树的高度 次就能找到，他还有一个隐藏特点：二叉搜索树的中序遍历是有序的。

2. 二叉搜索树的实现

二叉搜索树，树是一种结构，需要用类来定义，节点也是一种结构，需要另一个类来定义。节点对数来说是完全公开的，所以节点我们使用 struct 。我们创建一个头文件：BinarySearchTree.h ，在里面先编写一个框架出来：

#pragma once

// struct BinarySearchTreeNode
// 节点结构体
template<class K>
struct BSTreeNode // 采用缩写
{
	typedef BSTreeNode<K> Node;

	// 指向左孩子的指针
	Node* _left;
	// 指向右孩子的指针
	Node* _right;
	// 关键字（存储的数据）
	K _key;

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

//class BinarySearchTree
// 二叉搜索树类
template<class K>
class BSTree // 采用缩写
{
	typedef BSTreeNode<K> Node;
public:
	//
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

查找

二叉搜索树非常适合查找，逻辑也非常简单。通过不断与当前节点比较而选择进入左子树或者右子树。

bool Find(const K& key)
{
	Node* cur = _root;

	// cur处有节点
	while (cur)
	{
		// 要查找的值比当前节点的值要小
		if (key < cur->_key)
		{
			// 前往左子树
			cur = cur->_left;
		}
		//要查找的值比当前节点的值要大
		else if (key > cur->_key)
		{
			// 前往右子树
			cur = cur->_right;
		}
		// 相等时
		else
		{
			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

插入

插入也是比较简单的，当插入的关键字已存在时，现阶段没有多大用处，我们就插入已有的关键字，当关键字不存在时，也是一种查找，当 找到空位置 时，该位置就可以插入。唯一需要注意的是，需要使用一个指针指向插入位置的父节点，否则无法进行节点之间的连接。

bool Insert(const K& key)
{
	// 注意空树
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 现阶段不插入相同的值
			return false;
		}
	}

	// 创建新节点
	cur = new Node(key);
	if (key < parent->_key)
	{
		// 新节点插在左子树
		parent->_left = cur;
	}
	else
	{
		// 新节点插在右子树
		parent->_right = 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
39
40
41
42
43
44
45

中序遍历

中序遍历需要借助当前节点，所以需要一个形参，但是根节点又是属于类的私有成员变量，在外部无法访问，所以我们需要嵌套一层函数来访问。

// private内
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	_InOrder(root->_left);
	std::cout << root->_key << " ";
	_InOrder(root->_right);
}

// 套一层函数来获取根节点
// public内
void InOrder()
{
	_InOrder(_root);
	std::cout << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们来测试一下：创建一个源文件 Test.cpp。

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main(void)
{
	BSTree<int> t;
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉搜索树的中序遍历确实是有序的，看来前面的函数都没有问题。

删除

前面的函数其实都是比较简单的，二叉搜索树的删除会比较困难。二叉搜索树的删除分为三种情况：

1. 删除没有孩子节点的节点。
   
   比如删除上图中的 1 4 7 13 。这种情况最简单，直接删掉即可。
2. 删除只有一个孩子的节点。
   
   如上图中的 10 14 。这种情况也算是比较简单的，比如说我们要删除 14 。我们只需要将 14 的孩子 托付给 14 的父节点 即可。
   
3. 删除有两个孩子的节点。

比如删除上图中的 8 3 6 。这种情况最为复杂，也最难。这种情况该怎么删除呢？有一种方法叫做 替换删除法 ，比如说我要删除 3 ，我可以从 3 的孩子里找出能够替换掉 3 的节点，即 左子树中的最右侧（最大）的节点，或者右子树中的最左侧（最小）的节点 。这两个节点与被删除的节点替换都可以完成删除操作。

其实情况1和情况2差不多，因为情况1同样可以理解为将 空托付给父节点 。

bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		// 找到了要删除的节点
		else
		{
			// 左子树为空，托付右子树
			if (cur->_left == nullptr)
			{
				if (cur == parent->_left)
				{
					parent->_left = cur->_right;
				}
				else
				{
					parent->_right = cur->_right;
				}
				delete cur;
				return true;
			}
			// 右子树为空，托付左子树
			else if (cur->_right == nullptr)
			{
				if (cur == parent->_left)
				{
					parent->_left = cur->_left;
				}
				else
				{
					parent->_right = cur->_left;
				}
				delete cur;
				return true;
			}
			// 都不为空使用替换删除法
			else
			{
				// 这里采用的是 找右子树的最小节点
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}
				// 赋值
				cur->_key = rightMin->_key;
				// 托付
				if (rightMin == rightMinParent->_left)
				{
					rightMinParent->_left = rightMin->_right;
				}
				else
				{
					rightMinParent->_right = rightMin->_right;
				}

				delete rightMin;
				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

上面的函数有两个小细节，①假如删除8，则其右孩子 10 就是要删除的节点，所以 rightMinParent 不能初始化为 nullptr。②假如删除8，则其右孩子 10 就是要删除的节点，此时 10 是 8 的右节点，所以 rightMin 不一定是 rightMinParent 的左节点。
测试一下：

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main(void)
{
	BSTree<int> t;
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	t.Erase(8);
	t.InOrder();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

已经没有问题了吗？NoNoNo，当要删除的节点是根节点，并且只有左子树或者只有右子树时就会出问题了。此时 Parent 为 nullptr 但是被解引用了，所以我们需要加一下判断：

bool Erase(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		// 找到了要删除的节点
		else
		{
			// 左子树为空，托付右子树
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}

				delete cur;
				return true;
			}
			// 右子树为空，托付左子树
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}

				delete cur;
				return true;
			}
			// 都不为空使用替换删除法
			else
			{
				// 这里采用的是 找右子树的最小节点
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}
				// 赋值
				cur->_key = rightMin->_key;
				// 托付
				if (rightMin == rightMinParent->_left)
				{
					rightMinParent->_left = rightMin->_right;
				}
				else
				{
					rightMinParent->_right = rightMin->_right;
				}

				delete rightMin;
				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
83
84
85
86
87
88
89
90
91
92
93
94

拷贝构造

由于默认生成的拷贝构造函数是浅拷贝，直接拷贝构造会导致两个对象指向同一个二叉搜索树，我们要实现深拷贝所以要手动写一个拷贝构造函数。

// 强制生成默认构造函数
BSTree() = default;

// 拷贝构造函数
BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

// private内
Node* Copy(Node* root)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	Node* newRoot = new Node(root->_key);
	newRoot->_left = Copy(root->_left);
	newRoot->_right = Copy(root->_right);
	return newRoot;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

析构函数

~BSTree()
{
	Destroy(_root);
}

// private内
void Destroy(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试一下：

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main(void)
{
	BSTree<int> t;
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	BSTree<int> t1(t);
	t1.InOrder();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

赋值重载

BSTree<K>& operator=(BSTree<K> t)
{
	std::swap(_root, t._root);
	return *this;
}
1
2
3
4
5

完整代码

#pragma once

// struct BinarySearchTreeNode
template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	// 指向左孩子的指针
	Node* _left;
	// 指向右孩子的指针
	Node* _right;
	// 关键字（存储的数据）
	K _key;

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

//class BinarySearchTree
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	// 强制生成默认构造函数
	BSTree() = default;

	// 拷贝构造函数
	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		std::swap(_root, t._root);
		return *this;
	}

	// 析构函数
	~BSTree()
	{
		Destroy(_root);
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 现阶段不插入相同的值
				return false;
			}
		}

		// 创建新节点
		cur = new Node(key);
		if (key < parent->_key)
		{
			// 新节点插在左子树
			parent->_left = cur;
		}
		else
		{
			// 新节点插在右子树
			parent->_right = cur;
		}

		return true;
	}

	bool Find(const K& key)
	{
		Node* cur = _root;

		// cur处有节点
		while (cur)
		{
			// 要查找的值比当前节点的值要小
			if (key < cur->_key)
			{
				// 前往左子树
				cur = cur->_left;
			}
			//要查找的值比当前节点的值要大
			else if (key > cur->_key)
			{
				// 前往右子树
				cur = cur->_right;
			}
			// 相等时
			else
			{
				return true;
			}
		}
		// 没找到
		return false;
	}

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

	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			// 找到了要删除的节点
			else
			{
				// 左子树为空，托付右子树
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}

					delete cur;
					return true;
				}
				// 右子树为空，托付左子树
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				// 都不为空使用替换删除法
				else
				{
					// 这里采用的是 找右子树的最小节点
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					// 赋值
					cur->_key = rightMin->_key;
					// 托付
					if (rightMin == rightMinParent->_left)
					{
						rightMinParent->_left = rightMin->_right;
					}
					else
					{
						rightMinParent->_right = rightMin->_right;
					}

					delete rightMin;
					return true;
				}
			}
		}

		return false;
	}
private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		std::cout << root->_key << " ";
		_InOrder(root->_right);
	}

	void Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	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
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

3. 二叉搜索树的应用

K搜索模型

K搜索模型主要运用于想要 快速找到某个值在不在 。比如说门禁系统。

KV搜索模型

KV搜索模型主要运用于想要 通过某个值（key）查找另一个值（value）在不在 。比如说商场车库，通过车牌号找到进车库的时间好用来计费。

上面实现的就是 K搜索模型 ，如何实现 KV搜索模型 呢？其实也不难，节点结构体内多存入一个 value 即可，然后输入 key 的时候也要输入 value。逻辑与 K搜索模型 大差不差。

---

未完待续