数据结构---二叉搜索树

二叉搜索树

什么是二叉搜索树？

二叉搜索树(Binary Search Tree 简称BST)又称二叉排序树，是一种二叉树的特殊形式，它在每个节点上存储的键值满足以下性质：

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

根据这个性质，我们可以利用二叉搜索树进行高效的插入，删除和搜索操作。

二叉搜索树的操作

查找

• 从根节点开始比较，如果比根节点大则往右查找，反之往左查找。
• 最多查找高度次，走到空，还没找到，这个值不存在。

上面的图，比如果要查找4.

4 < 8，往左走，找到3，4大于3，往右走，找到6，6大于4，往左走，找到4，4 == 4，查找成功。

重复上面的操作，直到走到4，4小于5，往右走，为nullptr，不存在这个值，返回false。

void Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < 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

插入

• 树为空，则直接新增节点，赋值给root指针
• 树非空，按二叉搜索树性质查找插入位置，插入新节点。

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

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur) // 树非空
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	if (parent->_key > 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

如果要插入的值(val)比当前节点的key大，则往右子树移动；反之往左子树移动，直到找到合适的插入位置。

在找到插入位置的时候，不要直接 cur = new Node(val),这样创建的是临时变量，出了作用域会销毁，可以用一个临时变量(parent)记录查找过程中cur的上一个位置，在找到合适的位置的时候，与parent节点的key进行比较之后，在进行链接。

删除

删除有点麻烦，

看这棵树，把7删了，很简单，delete了就行了，把14给删了呢？右子树的所有节点一定大于根节点，把13链接在10的右子树即可，就算13下面还有子树，也不会导致这个树混乱。那么删3呢？3有两个孩子，这个时候可以找人把3给替代了，从左子树找最大的节点，或者找右子树的最小节点完成替代。

删除分三种情况

1. 没有孩子
2. 一个孩子
3. 两个孩子 (找左子树的最大节点 or 右子树的最小节点)

---

首先要找到要删除节点的位置(cur)，但光找到一个节点的位置不够，还要找到当前节点的父节点(parent)。如果说cur的左子树为空，并且要删除的节点为根节点。

也就是当前cur位于8的位置，此时要删除，把根节点移动到cur的右子树位置即可。

若要删的不是根节点。

此时cur=6，parent=3，要先判断cur与parent的关系，然后直接将parent与cur的子树链接在一起即可。这是要删除节点的左子树为空的情况，右子树为空与这个一样。

---

若要删除的节点有两个孩子。

要先找到左子树中最大的节点(leftMax)，将根节点的key与leftMax的key交换。在找leftMax的过程中记录下来其父节点(parent)，判断parent和leftMax的关系。最后将parent与leftMax的左右节点(都为空)链接一下即可。

---

当然还有一种特殊情况。

这里要删除8，而3就是左子树中最大的节点。所以这种情况下的parent初始值不能设为nullptr，而是初始化为cur。leftMax还是初始化为cur->left

---

		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;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				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;
						}
					}
				}
				else
				{}
				delete 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
46
47
48
49
50
51
52
53
54
55
56

源代码

非递归版

#pragma once


template 
class BSTreeNode
{
public:

	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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

	
};


template 
class BSTree
{
	typedef BSTreeNode Node;
public:
	BSTree()
		:_root(nullptr)
	{}

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

		Node* cur = _root;
		Node* parent = nullptr;
		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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		return true;
	}

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

	bool erase(const K& key)
	{
		Node* parent = _root;
		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
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				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;
						}
					}
				}
				else
				{
					Node* parent = cur;					
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}
					swap(leftMax->_key, _root->_key);
					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_right;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	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

递归版

#pragma once


template 
class BSTreeNode
{
public:

	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

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



};


template 
class BSTree
{
	typedef BSTreeNode Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	bool Insert(const K& key)
	{
		return _Insert(_root, key);
	}

	bool Find(const K& key)
	{
		return _Find(_root, key);
	}

	bool erase(const K& key)
	{
		return _erase(_root, key);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

private:

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

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

	bool _erase(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key > key)
		{
			return _erase(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _erase(root->_right,key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* leftMax = root->_left;

				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}

				swap(root->_key, leftMax->_key);

				return _erase(root->_left, key);
			}

			delete del;

			return true;
		}

		return false;
	}

	bool _Insert(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key > key)
		{
			return _Insert(root->_left,key);
		}
		else if (root->_key < key)
		{
			return _Insert(root->_right,key);
		}
		else
		{
			return false;
		}
	}

	bool _Find(Node* root, const K& key)
	{
		if (root == nullptr) {
			return false;
		}

		if (root->_key > key)
		{
			return _Find(root->_left);
		}
		else if (root->_key < key)
		{
			return _Find(root->_right);
		}
		else
		{
			return true;
		}
	}

	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