ChristmasError-Blog

C++ BST-binary search tree 二叉搜索树的实现

C++ 数据结构 BST
字数统计: 1.2k阅读时长: 6 min
2018/12/27 Share

BST 二叉搜索树(binary search tree)

二叉搜索树只能为空树，或者是具有下列性质的二叉树

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

    树节点

1
2
3
4
5
6
7
8
9
10
//Tree_Node.h
#pragma once
struct TreeNode
{
	int val;
	TreeNode* left = nullptr;
	TreeNode* right=nullptr;
	TreeNode* parent = nullptr;
	TreeNode(int v) :val(v) {  };
};

BST树

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
//Binary_Search_Tree.h
#pragma once
#include"Tree_Node.h"
#include<vector>
#include<iostream>
class BST 
{
private:
	TreeNode* _root=nullptr;
	//typedef TreeNode Node;

	void _createBST( std::vector<int>vec);
	TreeNode* _find(int k);
	void _insertnode(int a);
	void _removenode( int a);
	void _inorderprint(TreeNode * node);
	void _preorderprint(TreeNode * node);
	void _postorderprint(TreeNode * node);
	//void _destory();
	TreeNode* Predecessor(int a);//寻找前驱节点
	TreeNode* Successor(int a);//寻找后继节点
	
public:
	BST() {};
	BST(std::vector<int>vec) { _createBST( vec); };
	
	//~BST() { _destory(); };
	void inorderprint() { _inorderprint(_root); };
	void preorderprint() { _preorderprint(_root); };
	void postorderprint() { _postorderprint(_root); };
	void insert(int a) { _insertnode(a); };
	void remove(int a) { _removenode( a); };
};
//vector<int>构造BST
void BST::_createBST(std::vector<int>vec)
{
	for (int val : vec)
		_insertnode(val);
}
//查找key的结点
TreeNode* BST::_find(int key)
{
	TreeNode* cur=_root;
	while (cur->val!=key && cur!=nullptr)
	{
		if (key > cur->val)
			cur = cur->right;
		else
			cur = cur->left;
	}
	if(cur!=nullptr)
		return cur;
	else
	{
		std::cout << "BST do not have this node!\n ";
		return nullptr;
	}
}
//插入结点
void BST::_insertnode(int a)
{
	TreeNode* node = new TreeNode(a);
	if (_root == nullptr)
	{
		_root = node;
		return;
	}
	else
	{
		TreeNode* cur = _root;
		while (true)
		{
			//新结点的值大于当前结点cur
			if (node->val > cur->val)
			{
				if(cur->right!=nullptr)
					cur = cur->right;
				else
				{
					cur->right = node;
					node->parent = cur;
					return;
				}
			}
			//新结点的值小于当前结点cur
			else
			{
				if (cur->left!= nullptr)
					cur = cur->left;
				else
				{
					cur->left = node;
					node->parent = cur;
					return;
				}
			}
		}
	}
}
//寻找前驱节点
TreeNode* BST::Predecessor(int a)
{
	TreeNode* cur = _find(a);
	if (cur->left != nullptr)
	{
		cur = cur->left;
		while (cur->right != nullptr)
			cur = cur->right;
		return cur;
	}
	while (cur->parent != nullptr && cur->parent->left == cur)
		cur = cur->parent;
	return cur->parent;
}

//寻找后继节点
TreeNode* BST::Successor(int a)
{
	TreeNode* cur = _find(a);
	//cur右结点不为空，则cur后继结点为右子树最靠左的结点
	if (cur->right != nullptr)
	{
		cur = cur->right;
		//存在左子树
		while (cur->left != nullptr)
			cur = cur->left;
		return cur;
	}
	//cur的右结点不存在左子树，向上找父节点第一个有右孩子且不存在cur的祖先
	while (cur->parent != nullptr && cur->parent->right != cur)
		cur = cur->parent;
	return cur->parent;
}
//删除值为a的结点
void BST::_removenode(int a)
{
	if (_root == nullptr)
		throw("error : it's an empty BSTtree!\n");
	TreeNode* dnode = _find(a);//找出需要删除的结点dnode
	TreeNode* temp;//temp为取代dnode的结点
	if (dnode->left == nullptr && dnode->right == nullptr)//情况1，删除节点为子节点
		temp = nullptr;
	else if (dnode->left == nullptr || dnode->right == nullptr)//情况2，删除节点只有左或者右子树
	{
		temp = (dnode->left == nullptr) ? dnode->right : dnode->left;
		temp->parent = dnode->parent;
	}
	else
	{
		temp = Successor(a);
		TreeNode* temp_right;
		if (temp->right == nullptr)
			temp_right = nullptr;
		else
		{
			temp_right = temp->right;
			temp_right->parent = temp->parent;
		}

		if (temp->parent->right == temp)
			temp->parent->right = temp_right;
		else
			temp->parent->left = temp_right;

		//temp取代dnode，注意dnode为根节点情况
		if (dnode->parent == nullptr)
		{
			temp->right = dnode->right;
			temp->left = dnode->left;
			_root = temp;
			delete dnode;
		}
		else if (dnode->parent->right == dnode)
		{
			dnode->parent->right = temp;
			temp->parent = dnode->parent;
			temp->right = dnode->right;
			temp->left = dnode->left;
			delete dnode;
		}
		else
		{
			dnode->parent->left = temp;
			temp->parent = dnode->parent;
			temp->right = dnode->right;
			temp->left = dnode->left;
			delete dnode;
		}

		//或者不取代dnode，将temp和dnode进行数据交换
		//dnode->val = temp->val;
		//delete temp;
		return;
	}
	//情况1,2余下操作，注意删除节点为根节点的特殊情况
	if (dnode->parent != nullptr)
	{
		if (dnode->parent->right == dnode)
			dnode->parent->right = temp;
		else
			dnode->parent->left = temp;
	}
	else
		_root = temp;
	delete dnode;
	return;
}
//前中后序打印BST
void BST::_inorderprint(TreeNode * node)
{
	if (node == nullptr)
		return;
	std:: cout << node->val << ' ';
	_inorderprint(node->left);
	_inorderprint(node->right);
}
void BST::_preorderprint(TreeNode * node)
{
	if (node == nullptr)
		return;
	_preorderprint(node->left);
	std::cout << node->val << ' ';
	_preorderprint(node->right);
}
void BST::_postorderprint(TreeNode * node)
{
	if (node == nullptr)
		return;
	_postorderprint(node->left);
	_postorderprint(node->right);
	std::cout << node->val<<' ';
}

测试运行结果

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
//test.cpp
#include"Binary_Search_Tree.h"
#include<iostream>
using namespace std;
int main()
{
	vector<int> vec{8,3,10,1,6,4,7,14,13 };
	BST bstree(vec);
	bstree.inorderprint();
	cout<<"\n";
	bstree.preorderprint();
	cout << "\n";
	bstree.postorderprint();
	cout << "\ndelete node key = 6\n";
	bstree.remove(6);
	bstree.preorderprint();
	cout << "\ndelete node key = 8\n";
	bstree.remove(8);
	bstree.preorderprint();
	cout << "\ndelete node key = 13\n";
	bstree.remove(13);
	bstree.preorderprint();
	cout << "\n";
	system("pause");
	return 0;
}

在这里插入图片描述

代码：
https://github.com/ChristmasError/Data_Structure/tree/master/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%20BST-Binary%20Search%20Tree

CATALOG
  1. 1. BST 二叉搜索树(binary search tree)
  2. 2. 树节点
  3. 3. BST树
  4. 4. 测试运行结果
Total : 16
2018
C++ 数据结构 BST Lambda表达式 Lambda函数 C++ 数据结构 广义表 指针，const C++ 红黑树 数据结构 RBTree hash_map 哈希表 这是建立个人Blog来的第一篇测试博客 RAII 智能指针 很基础的Markdown语法及其效果演示 《深入了解计算机系统》 leetcode刷题笔记 STL学习笔记