【深入C++】二叉搜索树

什么是二叉搜索树

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点最多有两个子节点，分别称为左子节点和右子节点。BST具有以下性质：

1. 左子树的所有节点值都小于根节点的值：即对于每一个节点，其左子树上所有节点的值都比该节点的值小。
2. 右子树的所有节点值都大于根节点的值：即对于每一个节点，其右子树上所有节点的值都比该节点的值大。
3. 每个子树也是二叉搜索树：这意味着BST的定义在每个节点的子树上都成立。

形如下面这棵树就是一颗二叉搜索树：

       8
     /   \
    3     10
   / \      \
  1   6      14
     / \     /
    4   7   13

1
2
3
4
5
6
7
8

二叉搜索树的接口

要写二叉搜索树的接口，我们先得定义一颗二叉搜索树：

定义二叉搜索树的节点：

template<class K>
struct BSTreeNode
{
	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};
1
2
3
4
5
6
7
8

定义二叉搜索树：

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
private:
	Node* _root = nullptr;
};
1
2
3
4
5
6
7
8

1.查找操作

由于二叉搜索树的性质，所以这里我们可以直接用while循环来查找，不需要进行递归来查找：

bool Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		//小于当前节点，在左子树
		if (cur->_key > key)cur = cur->_left;
		//大于当前节点，在右子树
		else if (cur->_key < key) cur = cur->_right;
		//等于当前节点，返回true
		else return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.插入操作

插入操作我们只需要找到插入的位置，然后插入节点即可，如果没有找到，则返回false，如果找到了并成功插入了，则返回true。

bool Insert(const K& key)
{
	//没有根节点的情况
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	//遍历节点
	Node* cur = _root;
	//记录当前节点的父节点
	Node* parent = nullptr;
	while (cur)
	{
		parent = cur;
		if (cur->_key > key)cur = cur->_left;
		else if (cur->_key < key) cur = cur->_right;
		else return false;
	}
	//找到插入的地方，直接new
	cur = new Node(key);
	//判断插入到父节点的左节点还是右节点
	if (parent->_key < key) 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

3.中序遍历

对于中序遍历，我们需要写一个辅助函数，来传递当前this指针对应的root。

void InOrder()
{
	_InOrder(_root);
}
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

4.删除操作

插入操作分三种情况：

我们拿下面这个二叉搜索树为例子：

将节点进行归类：

我们先讨论删除没有孩子的节点，对于没有孩子的节点我们可以直接进行删除。
其次，我们来讨论删除一个孩子的节点，假如我们删除14，我们需要知道14的父亲，将10和14的左孩子串起来。

可以将一个孩子的节点归结为这几种情况。
接下来就是有两个孩子的节点：

我们拿3这个节点为例子：

删除3节点，我们应该用左子树最大，或者右子树最小进行替换，然后转化成删除左子树最大，或者右子树最小的节点，就相当于把删除有两个孩子的节点转换成删除一个孩子的节点或者没有孩子的节点。

bool Erase(const K& key)
{
	//三种情况：
	//1.一个孩子
	//2.没有孩子
	//3.两个孩子：左子树的最大，右子树的最小
	//左子树的最左，右子树的最右
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			//删除
			//0-1个孩子的情况
			if (cur->_left == nullptr)
			{
				//删除根节点的情况
				if (parent == nullptr)_root = cur->_right;
				else
				{
					if (parent->_left == cur) parent->_left = cur->_right;
					else parent->_right = cur->_right;
				}
				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				//删除根节点
				if (parent == nullptr) _root = cur->_left;
				else
				{
					if (parent->_left == cur)parent->_left = cur->_left;
					else parent->_left = cur->_left;
				}
				delete cur;
				return true;
			}
			//两个孩子的情况
			else
			{
				//找右子树最小的节点作为最大的节点
				Node* rightminp = nullptr;
				Node* rightmin = cur->_right;
				//left不为空就一直向left走
				while (rightmin->_left != nullptr)
				{
					rightminp = rightmin;
					rightmin = rightmin->_left;
				}
				cur->_key = rightmin->_key;
				if (rightminp != nullptr) rightminp->_left = rightmin->_right;
				else cur->_right = rightmin->_right;
				delete rightmin;
				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

删除成功返回true，删除失败没找到则返回false。

所有代码

#pragma once
#include<iostream>
using namespace std;
template<class K>
struct BSTreeNode
{
	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (cur->_key > key)cur = cur->_left;
			else if (cur->_key < key) cur = cur->_right;
			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->_left;
			else if (cur->_key < key) cur = cur->_right;
			else return true;
		}
		return false;
	}

	bool Erase(const K& key)
	{
		//三种情况：
		//1.一个孩子
		//2.没有孩子
		//3.两个孩子：左子树的最大，右子树的最小
		//左子树的最左，右子树的最右
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//删除
				//0-1个孩子的情况
				if (cur->_left == nullptr)
				{
					//删除根节点的情况
					if (parent == nullptr)_root = cur->_right;
					else
					{
						if (parent->_left == cur) parent->_left = cur->_right;
						else parent->_right = cur->_right;
					}
					delete cur;
					return true;
				}
				else if (cur->_right == nullptr)
				{
					//删除根节点
					if (parent == nullptr) _root = cur->_left;
					else
					{
						if (parent->_left == cur)parent->_left = cur->_left;
						else parent->_left = cur->_left;
					}
					delete cur;
					return true;
				}
				//两个孩子的情况
				else
				{
					//找右子树最小的节点作为最大的节点
					Node* rightminp = nullptr;
					Node* rightmin = cur->_right;
					//left不为空就一直向left走
					while (rightmin->_left != nullptr)
					{
						rightminp = rightmin;
						rightmin = rightmin->_left;
					}
					cur->_key = rightmin->_key;
					if (rightminp != nullptr) rightminp->_left = rightmin->_right;
					else cur->_right = rightmin->_right;
					delete rightmin;
					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 = 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

总结

二叉搜索树（BST）是一种在计算机科学中广泛应用的数据结构，具有高效的查找、插入和删除操作。通过遵循节点值的有序性规则，BST能够在平均情况下实现对数时间复杂度的操作，使其成为处理动态数据集的理想选择。

在本篇博客中，我们详细介绍了二叉搜索树的定义和性质，并通过示例展示了其基本结构。我们还探讨了BST的三大主要操作：插入、查找和删除，并分析了这些操作的实现方法和时间复杂度。

尽管二叉搜索树在平衡状态下具有高效的性能，但在最坏情况下，BST可能会退化成链表。因此，在实际应用中，经常需要采用自平衡二叉搜索树（如AVL树和红黑树）来保证其性能。

通过对BST的深入理解和实践，相信你能够在各种编程场景中灵活运用这一重要的数据结构，从而提高程序的效率和性能。如果你对二叉搜索树有任何疑问或希望了解更多高级应用，欢迎在评论区留言讨论。