C++数据结构：二叉搜索树的原理以及实现_c++设计一个算法读入一串整数,然后构造二叉排序树,进行查找。

前言

我们今天在二叉树的基础上来梳理学习二叉搜索树的相关知识点，二叉搜索树也常被归类为一种搜索算法，并且在后续map和set的学习中需要二叉搜索树作为铺垫，有助于我们理解map和set的特性，不仅如此，二叉搜索树自身也是有着非常多的特性和优势。

一：二叉搜索树的概念

二叉搜索树（Binary Search Tree）又称二叉排序树和二叉查找树。它可以是一颗空树，也可以是具有以下性质的二叉树：

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

图解：

二：二叉搜索树的实现

BST.hpp：

实现了二叉搜索树的插入、查找、删除等功能，具体注意的点：

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

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

template<class K>
class BSTree{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key){
		if (_root == nullptr){
			_root = new Node(key);
			return true;
		}
		// parent起到连接新结点的作用
		Node* parent = nullptr;
		Node* cur = _root;
		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 ture;
			}
		}
		return false;
	}

	// 删除的结点存在左右孩子
	// 则找左子树的最右结点或右子树的最左结点进行替代
	bool Erase(const K& key){
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur){
			if (cur->_key < key){
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key){
				parent = cur;
				cur = cur->_left;
			}
			else{
				// 找到了需要删除的结点
				// 需要判断cur是parent的左孩子还是右孩子
				if (cur->_left == nullptr){
					// 被删除的结点是根结点
					if (cur == _root){
						_root = cur->_right;
					}
					// 被删除的结点存在父结点
					else{
						if (parent->_right == cur){
							parent->_right = cur->_right;
						}
						else{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr){
					if (cur == _root){
						_root = cur->_left;
					}
					else{
						if (parent->_right == cur){
							parent->_right = cur->_left;
						}
						else{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}
				else{
					// 替代
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					// 若while循环没有进入则Parent就会为nullptr
					// 初始化时Parent就为cur
					while (rightMin->_left){
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					// 替代删除结点
					cur->_key = rightMin->_key;
					// 删除rightMin
					// 右子树的最左结点可能是父结点的右孩子
					if (rightMin == rightMinParent->_left){
						rightMinParent->_left = rightMin->_right;
					}
					else{
						rightMinParent->_right = rightMin->_right;
					}
					delete rightMin;
				}
				return true;
			}
		}
		return false;
	}

	void _Inorder(Node* root){
		if (root == nullptr){
			return;
		}
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}

	void Inorder(){
		_Inorder(_root);
		cout << endl;
	}
private:
	Node* _root = nullptr;
};

void TestBSTree(){
	BSTree<int> tree;
	int array[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (const auto& e : array){
		tree.Insert(e);
	}
	tree.Inorder();
	tree.Erase(7);
	tree.Inorder();
}
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

三：二叉搜索树的应用

3.1 K模型

K模型即只有Key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

1. 以单词集合中的每个单词作为key，构建一棵二叉搜索树。
2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

3.2 KV模型

KV模型即每一个关键码Key，都有与之对应的值Value，即<Key, Value>的键值对。

比如：实现一个简单的英汉词典，可以通过英文找到与其对应的中文，具体实现方式如下：

1. <英文单词，中文含义>为键值对构造二叉搜索树。
2. 查询英文单词时，只需给出英文单词，就可快速找到与其对应的中文含义。

KV模型的实现：

#pragma once
template<class K,class V>
struct BSTreeNode{
	BSTreeNode<K,V>* _left;
	BSTreeNode<K,V>* _right;
	K _key;
	V _value;

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

template<class K, class V>
class BSTree{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value){
		if (_root == nullptr){
			_root = new Node(key,value);
			return true;
		}
		// parent起到连接新结点的作用
		Node* parent = nullptr;
		Node* cur = _root;
		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,value);
		// 连接
		if (parent->_key < key){
			parent->_right = cur;
		}
		else{
			parent->_left = cur;
		}
		return true;
	}

	Node* 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 cur;
			}
		}
		return nullptr;
	}

	// 删除的结点存在左右孩子
	// 则找左子树的最右结点或右子树的最左结点进行替代
	bool Erase(const K& key){
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur){
			if (cur->_key < key){
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key){
				parent = cur;
				cur = cur->_left;
			}
			else{
				// 找到了需要删除的结点
				// 需要判断cur是parent的左孩子还是右孩子
				if (cur->_left == nullptr){
					// 被删除的结点是根结点
					if (cur == _root){
						_root = cur->_right;
					}
					// 被删除的结点存在父结点
					else{
						if (parent->_right == cur){
							parent->_right = cur->_right;
						}
						else{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr){
					if (cur == _root){
						_root = cur->_left;
					}
					else{
						if (parent->_right == cur){
							parent->_right = cur->_left;
						}
						else{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}
				else{
					// 替代
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					// 若while循环没有进入则Parent就会为nullptr
					// 初始化时Parent就为cur
					while (rightMin->_left){
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					// 替代删除结点
					cur->_key = rightMin->_key;
					// 删除rightMin
					// 右子树的最左结点可能是父结点的右孩子
					if (rightMin == rightMinParent->_left){
						rightMinParent->_left = rightMin->_right;
					}
					else{
						rightMinParent->_right = rightMin->_right;
					}
					delete rightMin;
				}
				return true;
			}
		}
		return false;
	}

	void _Inorder(Node* root){
		if (root == nullptr){
			return;
		}
		_Inorder(root->_left);
		cout << root->_key << "：" << root->_value << " ";
		_Inorder(root->_right);
	}

	void Inorder(){
		_Inorder(_root);
		cout << endl;
	}
private:
	Node* _root = nullptr;
};

void TestBSTree(){
	BSTree<string, string> dict;
	dict.Insert("sort", "排序");
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("insert", "插入");

	string str;
	while (cin >> str){
		// 查找
		BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret != nullptr){
			cout << ret->_value << endl;
		}
		else{
			cout << "未找到" << endl;
		}
	}

	// 统计水果出现的次数
	string strArray[] = { "西瓜", "苹果", "樱桃", "西瓜", "樱桃" };
	BSTree<string, int> countTree;
	for (auto str: strArray){
		BSTreeNode<string, int>* ret = countTree.Find(str);
		if (ret == nullptr){
			countTree.Insert(str, 1);
		}
		else{
			ret->_value++;
		}
	}
	countTree.Inorder();
}
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

四：二叉搜索树的性能

若插入的数据是有序或者接近有序时，二叉搜索树会从普通的二叉树结构化为单支树的形式，这样二叉搜索树的效率就没有办法保证。

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2^N

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

注意：二叉搜索树中Key是不允许修改的，可能会破坏二叉搜索树的性质。