C++之二叉搜索树详解

前言

对于已经学习C++/C语言的朋友来说，二叉树这个概念相信已经再熟悉不过了，我们平时接触的二叉树可能都很简单，今天我们来看一个比较有难度的二叉树，他的名字就是——二叉搜索树，只是听名字就知道他其实是用来搜索数据用的，那么他到底有什么特别之处呢？下面让我们一起来看看吧。

一、二叉搜索树的概念

二叉搜索树又称二叉排序树(二叉查找树)，它或者是一棵空树，或者是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
2.若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
3.他的左右子树也分别为二叉树搜索树

上面的这棵树就是一个典型的二叉搜索树。

二、二叉搜索树的操作

既然已经大概知道一棵二叉搜索树是什么样子的了，那么就让我们一起来实现一下吧。

1.节点类

我们知道二叉树其实就是一个一个的结点连接在一起，然后遵循我们前面所说的概念，就能够形成一棵二叉搜索树了，所以结点类是必不可少的。

template  //模板参数
struct BSTreeNode
{
	struct BSTreeNode* _left;//左指针
	struct BSTreeNode* _right;//右指针
	K _key;  //结点存储的值(节点值)
//构造函数，实现对创建的结点的初始化
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

注: 因为我们后面定义的二叉搜索树需要用到我们这里定义的结点类，所以直接将他定义为struct的形式，因为struct中的成员函数和成员变量默认是共有的，这样方便我们后面的调用。

2.二叉搜索树类内部定义

template
class BSTree
{
	typedef BSTreeNode Node; //typedef使代码更简洁
public:
	//构造函数
	//这样可以让编译器强制自己生成默认构造函数
	BSTree() = default;

	//拷贝构造
	BSTree(const BSTree& t){}

	//析构函数
	~BSTree(){}

	BSTree& operator=(BSTree t){}
	//插入操作
	bool Insert(const K& key){}
	//删除操作
	bool Erase(const K& key){}
	//中序遍历
	void InOrder(){}
	//查找操作
	bool Find(const K& key)

private:
	//子函数
	Node* _Copy(Node* root){}
	void _InOrder(Node* root){}
	void _Destory(Node* root){}
private:
	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

3.遍历操作

因为我们之后要查看我们创建的树到底符不符合我们的要求以及一些接口实现的正确性，所以我们需要将其中存储的数据打印出来，这里还有一个细节，如果我们以中序遍历的方式去遍历整棵二叉树的话，最后的打印结果是以升序的方式排布的，这样方便我们查看。

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left);//遍历左子树
	cout << root->_key << " ";
	_InOrder(root->_right);//遍历右子树
}
void InOrder()
{
	_InOrder(_root);//调用子函数
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里大家可以看到我们上面给出了两个函数，其中_InOrder是用访问限定符private修饰的，这里为什么要这么操作呢？
解释:
这里的_InOrder是InOrder函数的子函数，因为_root是私有成员，用户去调用这里的遍历函数的话就需要传入根结点，但是我们经过封装后，用户是无法访问_root这个成员变量的，所以才有了这里的子函数的诞生，类内的函数是可以访问类内的所有成员变量的，我们可以通过子函数去实现函数的功能，用户在调用函数的不需要传入任何参数，这样既没有会暴露我们的底层实现，也实现了函数的功能。
在后面的操作中涉及到递归函数的时候，也会这样使用。

4.构造函数

这里得构造函数是一定要自己实现的，因为后面我们需要拷贝构造函数，他其实也是一个构造函数，根据我们前面所学的，当我们自己写了一个构造函数的时候，编译器是无法再自动生成默认构造函数的。就不能再像下面的这种情况进行树的定义，所以构造函数一定要自己显示写一个。

//没有默认构造函数的话，就不能像这样进行构造
BSTree t;
1
2

构造函数有三种写法:

//1.可以这么写,顺便进行初始化
BSTree()
	:_root(nullptr)//创建一个空树
{}
//2.可以这么写，内置类型编译器可以自动初始化
BSTree(){}
//3.可以这么写
//这样可以让编译器强制自己生成默认构造函数
BSTree() = default;
1
2
3
4
5
6
7
8
9

5.拷贝构造函数

这里又要用到我们前面遍历函数所讲的子函数，道理是相同的，这里就不再进行描述。

//利用递归实现拷贝构造的子函数
Node* _Copy(Node* root)
{
	//如果是空树的话直接返回
	if (root == nullptr)
		return nullptr;
	Node* copyRoot = new Node(root->_key);//先拷贝根结点
	copyRoot->_left = _Copy(root->_left);//拷贝左子树
	copyRoot->_right = _Copy(root->_right);//拷贝右子树
	return copyRoot; //返回拷贝的树的根结点
}
BSTree(const BSTree& t)
{
//因为需要_root私有成员，所以需要一个子函数。
	_root = _Copy(t._root); //拷贝子函数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

注意: 这里的拷贝构造函数实现的是深拷贝。

6.赋值运算符重载

关于赋值运算符重载一般情况下是有两种方法的，我们将其称为现代写法和传统写法。
现代写法

BSTree& operator=(BSTree t)//函数在接收传入的参数的时候会先自动调用拷贝构造函数创建t对象
{
	swap(_root, t._root);//将本对象的_root结点与t对象中的_root进行交换，就实现可两棵树数据互换，即拷贝成功
	return *this; //这样返回的话也就可以支持连续赋值
}
1
2
3
4
5

传统写法
传统写法就是将传入的树的结点一一进行拷贝后再链接在一起就可以了。

BSTree& operator=(BSTree& t)
{
	if (this != &t) //防止自己给自己赋值
	{
		_root = _Copy(t._root);
	}
	return *this;//支持连续赋值
}
1
2
3
4
5
6
7
8

7.析构函数

这里也需要实现一个子函数，因为我们在销毁树的时候也需要传入私有成员–根结点。

void _Destory(Node* root)
{
	//空树直接返回
	if (root == nullptr)
	{
		return;
	}
	//转化为子问题
	_Destory(root->_left);//销毁左子树
	_Destory(root->_right);//销毁右子树
	delete root; //释放根结点
	root = nullptr;
}
//析构函数
~BSTree()
{
	//调用子函数
	_Destory(_root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8.插入函数

二叉搜索树的插入
插入的具体过程如下：
a. 树为空，则直接新增结点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新结点
若树不为空其具体操作如下:
1.若插入的结点的值小于根结点的值，则需要进入左子树进行插入
2.若插入的结点的值大于根结点的值，则需要进入右子树进行插入
3.若插入的结点的值与根结点的值相等，则插入失败

---

重复上面的操作，找到与自己相等的结点，插入失败，直接返回。若是走到了空结点的位置，则说明在该树中没有与之相等的值，进行插入操作即可。

非递归实现

下面的key变量即为我们要插入的值，因为我们最后还要将新建的节点与前面的结点(也就是父结点)连接起来，所以还需要个结点记录父结点(即parent)

bool Insert(const K& key)
{
//刚进入查找时，根结点为空，说明是空树，直接插入即可
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	//循环找空,cur走到空则找到了自己的位置
	while (cur)//(cur != nullptr)
	{
		//key大于当前结点的值，根据性质需要到右子树去寻找
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		//key小于当前结点的值，根据性质需要到左子树去寻找
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//上面的两种情况都不是的话，说明key值与当前节点的值相等，插入失败
		else
			return false;
	}
	//循环结束后说明找到了属于自己的位置，创建结点
	cur = new Node(key);
	//此时还需要判断一下节点与父结点的关系
	//大于父结点的值，插入到父结点的右边
	if (key > parent->_key)
		parent->_right = cur;
	//否则插入父结点的左边
	else
		parent->_left = cur;
	//插入成功返回true
	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

递归实现

//子函数实现递归
bool _InsertR(Node*& root, const K& key)//注意引用，十分重要
{
	//查找时，根结点为空，说明是空树或找到了插入的位置，直接插入
	if (root == nullptr)
	{
		root = new Node(key);
		//插入成功，返回true
		return true;
	}
	//key大于当前结点的值，根据性质需要到右子树去寻找
	if (key > root->_key)
	{
		//进入右子树
		return _InsertR(root->_right, key);
	}
	//key小于当前结点的值，根据性质需要到左子树去寻找
	else if (key < root->_key)
	{
		//进入左子树
		return _InsertR(root->_left, key);
	}
	//上面的两种情况都不是的话，说明key值与当前结点的值相等，插入失败
	else
		return false;
}
//外部函数对递归函数实现封装
bool InsertR(const K& key)
{
	//直接调用子函数
	return _InsertR(_root, key);
}
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

注意: 本函数中最精华的地方就是传的是引用参数，因为有引用的存在，我们就不需要去记录父节点所在的位置，直接修改root的指向，同时也就修改了父结点的指向。

9.删除函数

在实现二叉搜索树的函数中，删除操作是最复杂的，其中的情况有很多。
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面的四种情况:
a.要删除的结点无孩子结点
b.要删除的结点左子树为空
c.要删除的结点右子树为空
d.要删除的结点左右子树均不为空
看起来要删除结点是有4中情况，实际情况中情况a可以与情况b或者情况c合并起来，因此真正的删除过程如下:
1.要删除的结点左子树为空(左右子树均为空)
2.要删除的结点右子树为空
3.要删除的结点左右子树均不为空
只是这么看的话，可能比较抽象，下面我们将其分开剖析，然后再结合画图，一起看看如何实现其代码。
情况1:要删除的结点左子树为空(左右子树均为空)
这里我们将前面所说的情况a放入情况b中一起讲解。
这里为了更好地演示，我会将几个空结点也画出来。
1.先来看左右子树均为空的场景

2.再来看一下左子树为空的场景
场景1:

通过上面两个图的对比，我们可以看出在情况a与情况b中的操作是相同的，所以我们可以将他们归为一种情况去操作。
其实在删除左子树为空的结点的时候是有两个场景的，上面的场景是要删除的结点在父节点的左边，下面的这种场景是要删除的结点在父节点的右边，但是他们共有的特性都是左子树为空。所以只是在处理父节点的时候不同而已
场景2:

情况2:要删除的结点右子树为空
这种情况其实与情况1中的左子树为空一样，也有两种场景，与父结点有关系，所以我们就直接放在一起了。

情况3.要删除的结点左右子树均不为空

其实除了我们上面举出的例子外，还有删除父结点的值的情况，其实他们的操作都是类似的，都是将要删除的值换出去，进而delete其他的结点。

非递归实现

bool Erase(const K& key)
{
	//定义一个cur结点指针，进行查找
	Node* cur = _root;
	//定义一个结点保存父结点的指针
	Node* parent = nullptr;
	//查找我们要删除的结点
	while (cur)
	{
		//key大于当前结点的值，根据性质需要到右子树去寻找
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		//key小于当前结点的值，根据性质需要到左子树去寻找		
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//上面两种情况都不是，就是已经找到了，开始删除
		else
		{
			//1.左为空，只有右孩子
			if (cur->_left == nullptr)
			{
				//如果是根结点，直接让_root指向当前结点的右结点
				if (cur == _root)
				{
					_root = cur->_right;
				}
				//如果不是根结点，需要判断要删除的结点是父节点的左结点还是右结点			
				else
				{
					//是父节点的左结点，则让父亲的左结点指向要删除节点的右结点
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					//是父节点的右结点，则让父亲的右结点指向要删除节点的右结点
					else
					{
						parent->_right = cur->_right;
					}
				}
				//释放结点的空间
				delete cur;
				cur = nullptr;//置空
			}
			//2.右为空，只有左孩子
			else if (cur->_right == nullptr)
			{
				//如果是根结点，直接让_root指向当前结点的右结点
				if (cur == _root)
				{
					_root = cur->_left;
				}
				//如果不是根结点，需要判断要删除的结点是父节点的左结点还是右结点							
				else
				{
					//是父节点的左结点，则让父亲的左结点指向要删除节点的左结点
					if (parent->_left = cur)
					{
						parent->_left = cur->_left;
					}
					//是父节点的右结点，则让父亲的右结点指向要删除节点的左结点
					else
					{
						parent->_right = cur->_left;
					}
				}
				//释放结点的空间
				delete cur;
				cur = nullptr;
			}
			//3.有左右孩子，替换法
			//这里我们找右子树的最小值
			else
			{
				//定义一个结点记录找到的最小值所在的结点
				Node* min = cur->_right;
				//定义一个结点记录找到的最小值所在的结点的父节点
				Node* minParent = cur;
				//循环查找最小值所在的结点
				while (min->_left)
				{
					minParent = min;//min结点发生变化的时候父节点也要变化
					min = min->_left;//min结点变化
				}
				//循环结束表示已经找到最小值所在的结点
				swap(cur->_key, min->_key);//交换数据
				//min结点在父结点的左边
				if (minParent->_left == min)
				{
					minParent->_left = min->_right;
				}
				//min结点在父节点的右边
				else
				{
					minParent->_right = min->_right;
				}
				//释放结点的空间
				delete min;
				min = nullptr;//置空
			}
			//删除成功返回true
			return true;
		}
	}
	//删除失败返回false
	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
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

递归实现

递归实现删除操作的思路:
1.若树为空树(这里所说的树可能是整棵大树，也可能是递归时的子树)，则结点删除失败，直接返回false。
2.若所传入的key值小于当前树的根节点的值，则问题变为删除左子树中值为key的结点。
3.若所传入的key值大于当前树的根节点的值，则问题变为删除右子树中值为key的结点。
4.若所传入的key值等于当前树的根节点的值，则分析该结点满足的我们上面分析的哪一种情况，删除该结点。

bool _EraseR(Node*& root, const K& key)//注意引用
{
	//若根节点为空，直接返回false
	if (root == nullptr)
		return false;
	//若传入的key值大于当前结点的值，则要删除的结点在右子树中
	if (key > root->_key)
		return _EraseR(root->_right, key);
	//若传入的key值小于当前结点的值，则要删除的结点在左子树中
	else if(key < root->_key)
		return _EraseR(root->_left, key);
	//走到这里这里表示当前节点就为要删除的的结点
	else
	{
		//定义一个节点保存要删除的结点的地址
		Node* del = root;
		//1.左为空，只有右孩子
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		//2.右为空，只有左孩子
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		//3.有左右孩子
		else
		{
			//定义一个结点记录找到的最小值所在的结点
			Node* min = root->_right;
			//循环查找最小值，左为空，则当前节点中的值就为最小值
			while (min->_left)
			{
				min = min->_left;
			}
			//交换最小值与要删除的值
			swap(root->_key, min->_key);
			//替换后转化为删除右子树中的节点(转化为子问题)。
			//因为我们的操作就是去右子树中查找最小值，所以要删除的结点一定在右子树中。
			return _EraseR(root->_right, key);
		}
		//释放要删除的结点的空间
		delete del;
		del = nullptr;//置空
		//删除成功，返回true
		return true;
	}
}
bool EraseR(const K& key)
{
	//调用子函数
	return _EraseR(_root, key);
}
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

---

注意: 本函数中最精华的地方就是传的是引用参数，因为有引用的存在，我们就不需要去记录父节点所在的位置，直接修改root的指向，同时也就修改了父结点的指向。

10.查找函数

查找函数就非常简单了，我们只需要根据二叉搜索树的性质去进行查找就可以了。
查找操作的思路:
1.若树为空树，则查找失败，直接返回false
2.若所传入的key值小于当前树的根节点的值，则应该去左子树中查找
3.若所传入的key值大于当前树的根节点的值，则应该去右子树中查找
4.若所传入的key值等于当前树的根节点的值，就找到了，直接返回true

非递归实现

bool Find(const K& key)
{
	//定义一个cur负责查找我们要找的值
	Node* cur = _root;
	//如果cur!=nullptr，就可以一直进行查找
	while (cur)
	{
		//如果key的值大于当前结点的值，则要找的值在右子树中
		if (key > cur->_key)
			cur = cur->_right;
		//如果key的值小于当前结点的值，则要找的值在左子树中
		else if (key < cur->_key)
			cur = cur->_left;
		//走到这里表示当前的值就为我们要找的值
		else
			//直接返回true，表示树中存在key值
			return true;
	}
	//循环结束，表示cur走到了空，即树中没有该key值
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递归实现

bool _FindR(Node* root,const K& key)
{
	//如果根节点为空，则直接返回
	if (root = nullptr)
		return false;
	//如果key的值大于当前结点的值，则要找的值在右子树中
	if (key > root->_key)
		return _FindR(root->_right, key);
	//如果key的值小于当前结点的值，则要找的值在左子树中
	else if (key < root->_key)
		return _Find(root->_left, key);
	//到这一步则证明已经找到与key值相同的值，返回true
	else
		return true;
}

bool FindR(const K& key)
{
	//调用子函数
	return _FindR(_root,key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、二叉搜索树的应用

K模型

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型

每一个关键码key，都有与之对应的值Value，即的键值对。
该种方式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

四、二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树，如下

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为:logN
最差情况下，二叉搜索树退化为单枝树(或者类似单支)，其比较次数最坏能达到n。
如果退化成单枝树，二叉搜索树的性能就失去了。所以我们在后面要对其进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优。这里就涉及到了我们后面要学习的AVL树和红黑树。

总结

以上就是我们所讲的二叉搜索树的全部内容了，其中的重点和难点其实都是删除操作，其他的一些操作还是比较容易理解的，后面我们还会讲述更AVL树、红黑树等更高阶的树的实现，大家可以先关注博主，方便以后查看。如果你觉得我的内容对你有用的话，记得给波三连呦！！！