C++二叉树进阶——二叉搜索树

1. 二叉树的概念

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

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

2. 二叉树的实现

2.1创建节点类

template <class T>
struct BSTreeNode
{
	typedef BSTreeNode Node;
	Node* _left;
	Node* _right;
	T _key;

	BSTreeNode(const T& val)
		:_left(nullptr)
		,_right(nullptr)
		,_key(val)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 查找Find

• 查找就很简单了，因为搜索二叉树的结构特殊，任何一个节点的左节点都小于父节点，任何一个节点的右节点都大于父节点。所以搜索一个值只需要判断大于这个节点还是小于这个节点。如果小于则往左节点走，如果大于则往右节点走。

bool Find(const T& val)
{
	Node* cur = _root;
	while (cur)
	{
		if (val > cur->_key) 
			cur = cur->_right;
		else if (val < cur->_key) 
			cur = cur->_left;
		else return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 插入Insert

• 插入也是同样的道理，大于某个节点就往右走，小于某个节点就往左走。直到为空，这个节点就是我们要插入的点。但是因为树是单向的，所以同样要有个parent指针用来记录上一个节点，便于链接节点。

注意细节：

1. 当插入的节点是第一个节点的时候。
2. 链接的时候是连接左节点还是右节点。

bool Insert(const T& val)
{
	//记录链接的节点。
	Node* parent = nullptr;
	Node* cur = _root;
	//当插入的节点是第一个节点时
	if (_root == nullptr)
	{
		_root = new Node(val);
		return true;
	}
	while (cur)
	{
		if (val > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(val);
	//判断是链接右节点还是左节点。
	if (parent->_key < val)
		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

2.4 删除Erase

删除分三种情况：

1. 要删除的节点的左节点为空。
2. 要删除的节点的右节点为空。
3. 要删除的左右节点都不为空。

bool Erase(const T& val)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (val > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			if (cur->_left == nullptr)
			{
				//处理删除头节点的情况
				if (cur == _root)
				{
					_root = cur->_right;
				}
				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;
				}
				else
				{

					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
					delete cur;
				}
			}
			else
			{
				//替换法
				//这里要注意力RightMin不能定义成nullptr，因为如果删除的是头节点就会出现野指针的问题，所以这里要定义成cur
				Node* RightMin = cur;
				//定义右子树，找到右子树最左节点
				Node* RightCur = cur->_right;

				while (RightCur->_left)
				{
					RightMin = RightCur;
					RightMin = RightMin->_left;
				}
				
				//交换值
				swap(RightCur->_key, cur->_key);
				if (RightMin->_left == RightCur)
				{
					RightMin -> _left = RightCur->_right;
				}
				else
				{
					RightMin->_right = RightCur->_right;
				}
				delete RightCur;
			}
			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

2.5 中序遍历

这里我们会发现中序遍历搜索二叉树得到是一个有序的数列。

//这里说明一下，因为中序是要使用到递归的，也就是要传_root成员变量的。
//但是我们又不能修改_root所以要额外写一个函数来是由递归。
void Inorder()
{
	_Inorder(_root);
	cout << endl;
}
private:
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
15
16
17

2.6 构造/析构

BSTree(Node* root = nullptr)
	:_root(root)
{}

BSTree(const BSTree<T>& b)
{
	_root = Copy(b._root);
}

BSTree<T>& operator=(BSTree<T> b)
{
	swap(_root, b._root);
	return *this;
}

~BSTree()
{
	Destroy(_root);
}

private:
//前序常见节点
Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;

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

//后序delete节点
void Destroy(Node* root)
{
	if (root == nullptr)
		return;

	Destroy(root->_left);
	Destroy(root->_right);
}
		
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

3. 递归实现

递归版本的整体思路是一样的。

3.1 查找FindR

bool FindR(const T& val)
{
	return _FindR(val, _root);
}
bool _FindR(const T& val, Node* root)
{
	if (root == nullptr)
		return false;

	if (val > root->_key)
		return _FindR(val, root->_right);
	else if (val < root->_key)
		return _FindR(val, root->_left);
	else
		return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2 插入InsertR

bool InsertR(const T& val)
{
	return _InsertR(val, _root);
}

bool _InsertR(const T& val, Node*& root)
{
	if (root == nullptr)
	{
		root = new Node(val);
		return true;
	}

	if (val > root->_key)
		return _InsertR(val, root->_right);
	else if (val < root->_key)
		return _InsertR(val, root->_left);
	else
		return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.3 删除EraseR

删除也是一样的参数传递Node*& root
但是当删除的节点左右都不为空的时候就可以不用替换法了，只需要将将最左节点和删除的点swap一下，在递归删除节点指向的_right也就是右子树再次递归一下即可。

bool EraseR(const T& val)
{
	return _EraseR(val, _root);
}

bool _EraseR(const T& val, Node*& root)
{
	if (root == nullptr)
		return false;

	if (val > root->_key)
		return _EraseR(val, root->_right);
	else if (val < root->_key)
		return _EraseR(val, root->_left);
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			Node* cur = root->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			//交换cur节点和最左节点
			swap(root->_key, cur->_key);
			
			递归右子树
			return _EraseR(val, root->_right);
		}
		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
33
34
35
36
37
38
39
40
41
42

4.整体代码

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

template <class T>
struct BSTreeNode
{
	typedef BSTreeNode Node;
	Node* _left;
	Node* _right;
	T _key;

	BSTreeNode(const T& val)
		:_left(nullptr)
		,_right(nullptr)
		,_key(val)
	{}
};

template <class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
public:

	BSTree(Node* root = nullptr)
		:_root(root)
	{}

	BSTree(const BSTree<T>& b)
	{
		_root = Copy(b._root);
	}

	BSTree<T>& operator=(BSTree<T> b)
	{
		swap(_root, b._root);
		return *this;
	}

	~BSTree()
	{
		Destroy(_root);
	}

	bool Find(const T& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (val > cur->_key) 
				cur = cur->_right;
			else if (val < cur->_key) 
				cur = cur->_left;
			else return true;
		}
		return false;
	}

	bool Insert(const T& val)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		while (cur)
		{
			if (val > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (val < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(val);
		if (parent->_key < val)
			parent->_right = cur;
		else
			parent->_left = cur;
		return true;
	}

	bool Erase(const T& val)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (val > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (val < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					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;
					}
					else
					{

						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
						delete cur;
					}
				}
				else
				{
					//替换法
					Node* RightMin = cur;
					Node* RightCur = cur->_right;

					while (RightCur->_left)
					{
						RightMin = RightCur;
						RightMin = RightMin->_left;
					}

					swap(RightCur->_key, cur->_key);
					if (RightMin->_left == RightCur)
					{
						RightMin -> _left = RightCur->_right;
					}
					else
					{
						RightMin->_right = RightCur->_right;
					}
					delete RightCur;
				}
				return true;
			}
		}
		return false;
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}


///递归版本/


	bool FindR(const T& val)
	{
		return _FindR(val, _root);
	}

	bool InsertR(const T& val)
	{
		return _InsertR(val, _root);
	}

	bool EraseR(const T& val)
	{
		return _EraseR(val, _root);
	}

private:
	bool _EraseR(const T& val, Node*& root)
	{
		if (root == nullptr)
			return false;

		if (val > root->_key)
			return _EraseR(val, root->_right);
		else if (val < root->_key)
			return _EraseR(val, root->_left);
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* cur = root->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}

				swap(root->_key, cur->_key);
				
				return _EraseR(val, root->_right);
			}
			delete del;
			return true;
		}
	}

	bool _InsertR(const T& val, Node*& root)
	{
		if (root == nullptr)
		{
			root = new Node(val);
			return true;
		}

		if (val > root->_key)
			return _InsertR(val, root->_right);
		else if (val < root->_key)
			return _InsertR(val, root->_left);
		else
			return false;
	}

	bool _FindR(const T& val, Node* root)
	{
		if (root == nullptr)
			return false;

		if (val > root->_key)
			return _FindR(val, root->_right);
		else if (val < root->_key)
			return _FindR(val, root->_left);
		else
			return true;
	}
private:

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

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

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

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

	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
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
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305