c++高阶数据结构 二叉搜索树的实现

二叉搜索树

二叉搜索树的基本概念

二叉搜索树的特点：

1. 左子树都小于根节点，右子树都大于根节点。
2. 右子树都大于根节点，左子树都小于根节点。

二叉搜索树的查找方法

大于则去左侧，小于则去右侧。

二叉搜索树的代码实现

二叉搜索树的结点

二叉树的构造函数 析构函数

二叉树的构造函数很简单，对一般二叉排序树。构造方法简单。析构函数需要重点说析构函数，析构的时候需要销毁所有的结点。然后，在释放根结点。
销毁的时候需要后序遍历销毁所有结点。

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

后序遍历才可以，否则删除不干净。

二叉排序树的插入

二叉排序树的插入就是和二叉排序树的查找一致。二叉排序树插入时，大了就去右树，小了就去左树。

bool insert(const k& val)
	{
		
		if (_root == nullptr)//如果根为空则插入
		{
			_root = new Node(val);
			return true;
		}
		Node* cur = _root;
		Node* parent = cur;
		
		while (cur)
		{

			if (cur->value == val)//等于则说明已经有了，插入失败
			{

				return false;
			}
			else if (cur->value < val)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				parent = cur;
				cur = cur->left;
			}
		}
		cur = new Node(val);//创建新节点
		if (parent->value < 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
37
38
39
40
41

二叉树的删除

删除的第一步是查找的删除的位置cur. 我们和插入一样的做法。

1. 删除叶子

if (cur->right == nullptr && cur->left == nullptr)
				{
					if (cur == parentcur->right)
					{
						parentcur->right = nullptr;
					}
					else
					{
						parentcur->left = nullptr;
					}
					delete cur;
				}
1
2
3
4
5
6
7
8
9
10
11
12

2. 删除只有左子树
   删除拥有左子树的结点时，将左子树接到该结点原来所在位置即可。

删除左子树为空 注意两种可能：
1
2

else if (cur->left == nullptr)
				{
					// 判断他是那个子树
					//链接到父子树后面
					if (cur == _root)
					{
						_root = cur->right;
					}
					else
					{
						if (cur == parentcur->right)
						{
							parentcur->right = cur->right;
						}
						else
						{
							parentcur->left = cur->right;
						}
					}
					
					delete cur;
					break;
				}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3. 删除只有右子树
   删除只有右子树和删除只有左子树一样。
4. 删除左右子树都有
   
   交换结点的值 然后转化成删除 只有右孩子的树。

else
				{
					Node* newcurfath = cur;//这里不能空 否则删除头结点会报错。
					Node* newcur = nullptr;
					newcur = cur->right;
					while (newcur->left)//找可以替换的子结点
					{
						newcur = newcur->left;
					}
					cur->value = newcur->value;//交换结点
					if (newcur == newcurfath->right)
					{
						newcurfath->right = newcur->right;
					}
					else
					{
						newcurfath->left = newcur->right;
					}
					

					delete newcur;
				}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二叉树的拷贝构造

二叉树的拷贝构造是需要通过递归，也就是前序遍历。边前序遍历边开辟空间拷贝构造。

最后 拷贝构造的经典问题，传引用 不能传指针。

递归删除版本

递归是借助引用。每递归一次，进入一颗子树。恰好引用的就是当前的头结点。

完整代码

#pragma once
#include<iostream>
#include<string>

using namespace std;
template <class k>
struct BsNode
{	BsNode(const k& val = k())
		:right (nullptr)
		, left (nullptr)
		, value (val)
	{

	}
	typedef BsNode<k> Node;
	Node* right;
	Node* left;
	k value;
};
template <class k>
class BsTree
{
   typedef BsNode<k> Node;

public:
	BsTree()
		:_root(nullptr)
	{
		
	}
	BsTree(BsTree<k>& newroot)
	{
		_root = Copy(newroot._root);
	}
	bool insert(const k& val)
	{
		
		if (_root == nullptr)//如果根为空则插入
		{
			_root = new Node(val);
			return true;
		}
		Node* cur = _root;
		Node* parent = cur;
		
		while (cur)
		{

			if (cur->value == val)//等于则说明已经有了，插入失败
			{

				return false;
			}
			else if (cur->value < val)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				parent = cur;
				cur = cur->left;
			}
		}
		cur = new Node(val);//创建新节点
		if (parent->value < val)
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;
		}
			return true;
	}

	bool find(const k& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->value == val)
			{
				return true;
			}
			else if (cur->value>val)
			{
				cur = cur->right;
			}
			else
			{
				cur = cur->left;
			}
		}
		return false;
	}

	bool Erase(const k& val)
	{
		Node* cur = _root;
		Node* parentcur = _root;
		while (cur)
		{
			if (cur->value == val)
			{
				if (cur->right == nullptr && cur->left == nullptr)
				{
					if (cur == parentcur->right)
					{
						parentcur->right = nullptr;
					}
					else
					{
						parentcur->left = nullptr;
					}
					delete cur;
					break;
				}
				else if (cur->right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->left;
					}
					else
					{
						if (cur == parentcur->right)
						{
							parentcur->right = cur->left;
						}
						else
						{
							parentcur->left = cur->left;
						}
					}
					
					delete cur;
					break;
				}
				else if (cur->left == nullptr)
				{
					// 判断他是那个子树
					//链接到父子树后面
					if (cur == _root)
					{
						_root = cur->right;
					}
					else
					{
						if (cur == parentcur->right)
						{
							parentcur->right = cur->right;
						}
						else
						{
							parentcur->left = cur->right;
						}
					}
					
					delete cur;
					break;
				}
				else
				{
					Node* newcurfath = cur;
					Node* newcur = nullptr;
					newcur = cur->right;
					while (newcur->left)
					{
						newcur = newcur->left;
					}
					cur->value = newcur->value;
					if (newcur == newcurfath->right)
					{
						newcurfath->right = newcur->right;
					}
					else
					{
						newcurfath->left = newcur->right;
					}
					

					delete newcur;
				}
			}
			else if (cur->value > val)
			{
				parentcur = cur;
				cur = cur->left;
			}
			else
			{
				parentcur = cur;
				cur = cur->right;
			}
		}
		return true;
	}
	void print()
	{
		inorder(_root);
		cout << endl;
	}
	
	bool Eraser(const k& val)
	{
		return _Eraser(_root, val);
		
	}

	~BsTree()
	{
		destroy(_root);
		_root = nullptr;
	}
private:
	bool _Eraser(Node* &root, const k& val)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->value > val)
		{
			_Eraser(root->left,val);
		}
		else if (root->value < val)
		{
			_Eraser(root->right,val);
		}
		else
		{
			Node* tmp = root;
			if (root->left == nullptr)
			{
				root = root->right;
			}
			else if (root->right == nullptr)
			{
				root = root->left;
			}
			else
			{

				
				Node* newcur = nullptr;
				newcur = root->right;
				while (newcur->left)
				{
				  	newcur = newcur->left;
				}
				swap(newcur->value,_root->value);
				return _Eraser(root->right, val);
			}
			delete tmp;
			return true;
		}

	}
	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->value << ' ';
		inorder(root->right);
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* Newroot = new Node(root->value);
		Newroot->left = Copy(root->left);
		Newroot->right = Copy(root->right);
		return Newroot;
	}
	Node* _root;
};
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