二叉搜索树_二叉搜索树的时间复杂度

---

一、什么是二叉搜索树

二叉搜索树又称为二叉排序树，是具有以下性质的二叉树：

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

比如这一棵树：

每棵子树的左孩子都比子树的根节点小，右孩子比子树的根节点大，也就意味着二叉搜索树中不能出现两个值相同的节点。实际上我们在构建二叉搜索树时，如果树中有节点和待插入节点的值相同，我们不会将这个节点进行插入。

1.1. 二叉搜索树查找的时间复杂度

二叉搜索树如果是完全二叉树，查找的效率很高，为O(logN)：

因为我们每次查找时只需要判断是否比根节点大就能够确定目标值在左子树还是在右子树，相当于每一次比较都会减少一层树的深度，最多只需要查找树的深度层logN：

当二叉搜索树为单支树时，其深度为N，此时查找的时间复杂度为O(N)：

综上，二叉搜索树最好的时间复杂度为O(logN)，最坏为O(N)，整体时间复杂度取其最坏的情况为O(N)。

---

二、二叉搜索树的实现

2.1. 接口概览

//树的结点类
template<class K>
struct BSTreeNode
{
	K _key;                 //结点值
	BSTreeNode<K>* _left;   //指向左孩子
	BSTreeNode<K>* _right;  //指向右孩子

	//构造函数
	BSTreeNode(const K& key = 0)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};
//二叉搜索树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//构造函数
	BSTree();

	//拷贝构造函数
	BSTree(const BSTree<K>& t);

	//赋值运算符重载函数
	BSTree<K>& operator=(BSTree<K> t);

	//析构函数
	~BSTree();

	//插入函数
	bool Insert(const K& key);

	//删除函数
	bool Erase(const K& key);

	//查找函数
	Node* Find(const K& key);

	//中序遍历
	void InOrder();
private:
	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

2.2. 构造函数和析构函数

构造和拷贝构造

//构造函数
BSTree()
  :_root(nullptr)
{}


//拷贝整个树
Node* _Copy(Node* root)
{
	if (root == nullptr) //如果一开始就是空树，或者递归到叶子节点的左右子树，则返回空
		return nullptr;

	Node* copyNode = new Node(root->_key); //拷贝根结点
	copyNode->_left = _Copy(root->_left); //递归拷贝左子树
	copyNode->_right = _Copy(root->_right); //递归拷贝右子树
	return copyNode; //返回拷贝的树
}
//拷贝构造函数
BSTree(const BSTree<K>& t)
{
	_root = _Copy(t._root); //拷贝t对象的二叉搜索树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

重载=运算符

	//重载=运算符
	BSTree<K>& operator=(BSTree<K> t) //编译器接收右值的时候自动调用拷贝构造函数
	{
		std::swap(_root, t._root); //交换这两个对象的二叉搜索树
		return *this; //支持连续赋值
	}
1
2
3
4
5
6

析构函数

	//释放树中结点
	void _Destory(Node* root)
	{
		if (root == nullptr) //如果一开始就是空树，或者递归到叶子节点的左右子树则返回
			return;

		_Destory(root->_left); //递归释放左子树中的结点
		_Destory(root->_right); //递归释放右子树中的结点
		delete root; //释放根结点
	}
	//析构函数
	~BSTree()
	{
		_Destory(_root); //释放二叉搜索树中的结点
		_root = nullptr; //将根节点置空
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3. 插入节点的函数

非递归实现

插入分为两种情况：

1. 如果为空，则创建一个节点做根，_root指向这个节点
2. 如果不为空，则需要按照二叉搜索树的性质寻找插入的位置，插入新节点：
   使用parent，cur两个指针，parent记录cur的父节点
   key大于当前节点，cur往当前节点的右子树走，key小于当前节点则cur往左子树走，如果等于返回false，因为二叉搜索树不会出现两个节点相同的情况。
   当节点为空的时候，需要判断是parent左节点还是右节点，此时用key和parent节点的值进行比较，如果key小于parent对应的值，则连接在左边，否则连接在右边。

//插入函数
bool Insert(const K& key)
{
	if (_root == nullptr) //空树
	{
		_root = new Node(key); //直接申请值为key的结点作为二叉搜索树的根结点
		return true; //插入成功，返回true
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_key) //key值小于当前结点的值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key) //key值大于当前结点的值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //key值等于当前结点的值
		{
			return false; //不会进行插入，返回false
		}
	}
	//到这里只能说明cur遇到了空节点，但是不知道是parent的左孩子还是右孩子，还需要判断
	cur = new Node(key); //申请值为key的结点
	if (key < parent->_key) //key值小于当前parent结点的值
	{
		parent->_left = cur; //将结点连接到parent的左边
	}
	else //key值大于当前parent结点的值
	{
		parent->_right = cur; //将结点连接到parent的右边
	}
	return true; //插入成功，返回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

递归实现

相比于非递归的实现，递归实现不需要key的父节点，因为是通过递归的方式寻找左子树或右子树中的空节点来插入的，所以可以确定是左孩子还是右孩子。递归插入函数的子函数接收参数root时，必须采用引用接收，否则传入的root只是根节点指针的一份拷贝，当执行root = new Node(key);这条语句时，只是这个拷贝指针指向了new出来的节点，root节点仍然是nullptr。

//递归插入函数的子函数
bool _InsertR(Node*& root, const K& key) //注意引用
{
	if (root == nullptr) //空树
	{
		root = new Node(key); //直接申请值为key的结点作为树的根结点
		return true; //插入成功，返回true
	}

	if (key < root->_key) //key值小于根结点的值
	{
		return _InsertR(root->_left, key); //应将结点插入到左子树当中
	}
	else if (key > root->_key) //key值大于根结点的值
	{
		return _InsertR(root->_right, key); //应将结点插入到右子树当中
	}
	else //key值等于根结点的值
	{
		return false; //插入失败，返回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

2.4. 查找的函数

根据二叉搜索树的特性，我们在二叉搜索树当中查找指定值的结点的方式如下：

• 如果二叉搜索树一开始为空树，或者查找到了叶子节点的左右孩子节点，则查找失败，返回nullptr。
• 如果key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
• 如果key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
• 如果key值等于当前结点的值，则查找成功，返回对应结点的地址。

非递归实现

//查找函数
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_key) //key值小于该结点的值
		{
			cur = cur->_left; //在该结点的左子树当中查找
		}
		else if (key > cur->_key) //key值大于该结点的值
		{
			cur = cur->_right; //在该结点的右子树当中查找
		}
		else //找到了值为key的结点
		{
			return cur; //查找成功，返回结点地址
		}
	}
	return nullptr; //树为空或查找到了叶子节点的左右子节点，则查找失败，返回nullptr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递归实现

//递归查找函数的子函数
Node* _FindR(Node* root, const K& key)
{
	if (root == nullptr) //树为空
		return nullptr; //查找失败，返回nullptr

	if (key < root->_key) //key值小于根结点的值
	{
		return _FindR(root->_left, key); //在根结点的左子树当中查找
	}
	else if (key > root->_key) //key值大于根结点的值
	{
		return _FindR(root->_right, key); //在根结点的右子树当中查找
	}
	else //key值等于根结点的值
	{
		return root; //查找成功，返回根结点地址
	}
}
//递归查找函数
Node* FindR(const K& key)
{
	return _FindR(_root, key); //在_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

2.5. 删除节点的函数

首先查找元素是否在树之中，如果不存在返回false。

存在的话要删除的节点可能有下面四种情况：

1. 要删除的节点没有孩子节点 ，也就是叶子节点，此时可以直接删除。
2. 要删除的节点只有左孩子节点，此时让父节点连接它的左节点，然后删除该节点。
3. 要删除的孩子只有右孩子节点 ，此时让父节点连接它的右节点，然后删除节点
4. 要删除的孩子有左右孩子节点 ，找到其左子树的最大值或者右子树的最小值，替换根节点的值，然后删除该节点。在删除时，有两种方法：(1)注意右子树的最小节点或左子树的最大节点是其父节点的左孩子还是右孩子，然后让其父节点指向该节点的左树或右树。(2)该节点符合上面三种情况，因此可以直接递归调用该函数删除该节点。

非递归实现

//删除节点的函数
bool Erase(const K& key)
{
	Node* parent = nullptr; //待删除结点的父结点
	Node* cur = _root; //待删除结点
	while (cur)
	{
		//查找key节点，逻辑类似于查找函数
		if (key < cur->_key) //key值小于该结点的值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key) //key值大于该结点的值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //找到了待删除结点
		{
			if (cur->_left == nullptr) //待删除结点的左子树为空
			{
				if (cur == _root) //待删除结点是根结点，此时parent为nullptr
				{
					_root = cur->_right; //二叉搜索树的根结点改为根结点的右孩子
				}
				else //待删除结点不是根结点，此时parent不为nullptr
				{
					if (cur == parent->_left) //待删除结点是其父结点的左孩子
					{
						parent->_left = cur->_right; //父结点的左指针指向待删除结点的右子树即可
					}
					else //待删除结点是其父结点的右孩子
					{
						parent->_right = cur->_right; //父结点的右指针指向待删除结点的右子树即可
					}
				}
				delete cur; //释放待删除结点
				return true; //删除成功，返回true
			}
			else if (cur->_right == nullptr) //待删除结点的右子树为空
			{
				if (cur == _root) //待删除结点是根结点，此时parent为nullptr
				{
					_root = cur->_left; //二叉搜索树的根结点改为根结点的左孩子即可
				}
				else //待删除结点不是根结点，此时parent不为nullptr
				{
					if (cur == parent->_left) //待删除结点是其父结点的左孩子
					{
						parent->_left = cur->_left; //父结点的左指针指向待删除结点的左子树即可
					}
					else //待删除结点是其父结点的右孩子
					{
						parent->_right = cur->_left; //父结点的右指针指向待删除结点的左子树即可
					}
				}
				delete cur; //释放待删除结点
				return true; //删除成功，返回true
			}
			//方法一：
			//else //待删除结点的左右子树均不为空
			//{
				替换法删除
				//Node* minParent = cur; //标记待删除结点右子树当中值最小结点的父结点
				//Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
				寻找待删除结点右子树当中值最小的结点
				//while (minRight->_left)
				//{
				//	//一直往左走，直到找到叶子节点
				//	minParent = minRight;
				//	minRight = minRight->_left;
				//}
				//cur->_key = minRight->_key; //将待删除结点的值改为minRight的值
				此时有两种情况，一种是进入了while循环，minRight是minParent的左孩子
				一种是没有进入while循环，minRight是minParent的右孩子
				//if (minRight == minParent->_left) //minRight是其父结点的左孩子
				//{
				//	minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
				//}
				//else //minRight是其父结点的右孩子
				//{
				//	minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
				//}
				//delete minRight; //释放minRight
				//return true; //删除成功，返回true
	
			//}
			//方法二：
			else //待删除结点的左右子树均不为空
			{
			//替换法删除
			Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
			//寻找待删除结点右子树当中值最小的结点
			while (minRight->_left)
			{
				//一直往左走
				minRight = minRight->_left;
			}
			K minKey = minRight->_key; //记录minRight结点的值
			Erase(minKey); //调用递归删除minKey，minKey是其叶子节点
			cur->_key = minKey; //将待删除结点的值改为代替其被删除的结点的值，即minRight
			}
		}
	}
	return false; //没有找到待删除结点，删除失败，返回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

递归实现

递归的思路和非递归相同。递归实现也要传引用，因为要删除根节点，_root的指向会发生改变，如果不传引用改变的是其拷贝的指向，_root的指向没有发生改变。

//递归删除函数的子函数
bool _EraseR(Node*& root, const K& key)
{
	if (root == nullptr) //空树
		return false; //删除失败，返回false

	if (key < root->_key) //key值小于根结点的值
		return _EraseR(root->_left, key); //待删除结点在根的左子树当中
	else if (key > root->_key) //key值大于根结点的值
		return _EraseR(root->_right, key); //待删除结点在根的右子树当中
	else //找到了待删除结点
	{
		if (root->_left == nullptr) //待删除结点的左子树为空
		{
			Node* del = root; //保存根结点
			root = root->_right; //根的右子树作为二叉树新的根结点
			delete del; //释放根结点
		}
		else if (root->_right == nullptr) //待删除结点的右子树为空
		{
			Node* del = root; //保存根结点
			root = root->_left; //根的左子树作为二叉树新的根结点
			delete del; //释放根结点
		}
		//方法一：
		//else //待删除结点的左右子树均不为空
		//{
		//	Node* minParent = root; //标记根结点右子树当中值最小结点的父结点
		//	Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
		//	//寻找根结点右子树当中值最小的结点
		//	while (minRight->_left)
		//	{
		//		//一直往左走
		//		minParent = minRight;
		//		minRight = minRight->_left;
		//	}
		//	root->_key = minRight->_key; //将根结点的值改为minRight的值
		此时有两种情况，一种是进入了while循环，minRight是minParent的左孩子
		一种是没有进入while循环，minRight是minParent的右孩子
		//	if (minRight == minParent->_left) //minRight是其父结点的左孩子
		//	{
		//		minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树
		//	}
		//	else //minRight是其父结点的右孩子
		//	{
		//		minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树
		//	}
		//	delete minRight; //释放minRight
		//}
		//return true; //删除成功，返回true
		//方法二：递归删除这个节点
		else //待删除结点的左右子树均不为空
		{
			Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
			//寻找根结点右子树当中值最小的结点
			while (minRight->_left)
			{
				//一直往左走
				minRight = minRight->_left;
			}
			K minKey = minRight->_key; //记录minRight结点的值
			_EraseR(root->_right, minKey); //递归调用，删除右子树当中值为minkey的结点
			root->_key = minKey; //将根结点的值改为minRight的值
		}
	}
}
//递归删除函数
bool EraseR(const K& key)
{
	return _EraseR(_root, key); //删除_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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

---

三、二叉搜索树的应用模型及实例

3.1. k模型

K模型，即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值。比如排序去重；宿舍楼门禁，根据同学的学号是否在BSTree中查询该同学是否在宿舍中。

#include<iostream>
using namespace std;
//树的结点类
template<class K>
struct BSTreeNode
{
	K _key;                 //结点值
	BSTreeNode<K>* _left;   //左指针 
	BSTreeNode<K>* _right;  //右指针

	//构造函数
	BSTreeNode(const K& key = 0)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};
//二叉搜索树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//构造函数
	BSTree()
		:_root(nullptr)
	{}


	//拷贝树
	Node* _Copy(Node* root)
	{
		if (root == nullptr) //如果一开始就是空树，或者递归到叶子节点的左右子树，则返回空
			return nullptr;

		Node* copyNode = new Node(root->_key); //拷贝根结点
		copyNode->_left = _Copy(root->_left); //递归拷贝左子树
		copyNode->_right = _Copy(root->_right); //递归拷贝右子树
		return copyNode; //返回拷贝的树
	}


	//拷贝构造函数
	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root); //拷贝t对象的二叉搜索树
	}


	//现代写法
	BSTree<K>& operator=(BSTree<K> t) //编译器接收右值的时候自动调用拷贝构造函数
	{
		std::swap(_root, t._root); //交换这两个对象的二叉搜索树
		return *this; //支持连续赋值
	}

//const BSTree<K>& operator=(const BSTree<K>& t)
//{
//	if (this != &t) //防止自己给自己赋值
//	{
//		_root = _Copy(t._root); //拷贝t对象的二叉搜索树
//	}
//	return *this; //支持连续赋值
//}
	//释放树中结点
	void _Destory(Node* root)
	{
		if (root == nullptr) //如果一开始就是空树，或者递归到叶子节点的左右子树则返回
			return;

		_Destory(root->_left); //递归释放左子树中的结点
		_Destory(root->_right); //递归释放右子树中的结点
		delete root; //释放根结点
	}
	//析构函数
	~BSTree()
	{
		_Destory(_root); //释放二叉搜索树中的结点
		_root = nullptr; //将根节点置空
	}


	//插入函数
	bool Insert(const K& key)
	{
		if (_root == nullptr) //空树
		{
			_root = new Node(key); //直接申请值为key的结点作为二叉搜索树的根结点
			return true; //插入成功，返回true
		}
		Node* parent = nullptr;//记录cur的父节点
		Node* cur = _root;//找插入位置
		while (cur)
		{
			if (key < cur->_key) //key值小于当前结点的值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key) //key值大于当前结点的值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //key值等于当前结点的值
			{
				return false; //不会进行插入，返回false
			}
		}
		//到这里只能确定cur遇到了空节点，但是不知道是parent的左孩子还是右孩子，还需要判断
		cur = new Node(key); //申请值为key的结点
		if (key < parent->_key) //key值小于当前parent结点的值
		{
			parent->_left = cur; //将结点连接到parent的左边
		}
		else //key值大于当前parent结点的值
		{
			parent->_right = cur; //将结点连接到parent的右边
		}
		return true; //插入成功，返回true
	}

	//递归插入函数的子函数
	bool _InsertR(Node*& root, const K& key) //注意引用
	{
		if (root == nullptr) //空树
		{
			root = new Node(key); //直接申请值为key的结点作为树的根结点
			return true; //插入成功，返回true
		}

		if (key < root->_key) //key值小于根结点的值
		{
			return _InsertR(root->_left, key); //应将结点插入到左子树当中
		}
		else if (key > root->_key) //key值大于根结点的值
		{
			return _InsertR(root->_right, key); //应将结点插入到右子树当中
		}
		else //key值等于根结点的值
		{
			return false; //插入失败，返回false
		}
	}
	//递归插入函数
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key); //调用子函数进行插入
	}

	//查找函数
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (key > cur->_key) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了值为key的结点
			{
				return cur; //查找成功，返回结点地址
			}
		}
		return nullptr; //树为空或查找失败，返回nullptr
	}
	//递归查找函数的子函数
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr) //树为空
			return nullptr; //查找失败，返回nullptr

		if (key < root->_key) //key值小于根结点的值
		{
			return _FindR(root->_left, key); //在根结点的左子树当中查找
		}
		else if (key > root->_key) //key值大于根结点的值
		{
			return _FindR(root->_right, key); //在根结点的右子树当中查找
		}
		else //key值等于根结点的值
		{
			return root; //查找成功，返回根结点地址
		}
	}
	//递归查找函数
	Node* FindR(const K& key)
	{
		return _FindR(_root, key); //在_root当中查找值为key的结点
	}
	//删除节点的函数
	bool Erase(const K& key)
	{
		Node* parent = nullptr; //待删除结点的父结点
		Node* cur = _root; //待删除结点
		while (cur)
		{
			//查找key节点，逻辑类似于查找函数
			if (key < cur->_key) //key值小于该结点的值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key) //key值大于该结点的值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //找到了待删除结点
			{
				if (cur->_left == nullptr) //待删除结点的左子树为空
				{
					if (cur == _root) //待删除结点是根结点，此时parent为nullptr
					{
						_root = cur->_right; //二叉搜索树的根结点改为根结点的右孩子
					}
					else //待删除结点不是根结点，此时parent不为nullptr
					{
						if (cur == parent->_left) //待删除结点是其父结点的左孩子
						{
							parent->_left = cur->_right; //父结点的左指针指向待删除结点的右子树即可
						}
						else //待删除结点是其父结点的右孩子
						{
							parent->_right = cur->_right; //父结点的右指针指向待删除结点的右子树即可
						}
					}
					delete cur; //释放待删除结点
					return true; //删除成功，返回true
				}
				else if (cur->_right == nullptr) //待删除结点的右子树为空
				{
					if (cur == _root) //待删除结点是根结点，此时parent为nullptr
					{
						_root = cur->_left; //二叉搜索树的根结点改为根结点的左孩子即可
					}
					else //待删除结点不是根结点，此时parent不为nullptr
					{
						if (cur == parent->_left) //待删除结点是其父结点的左孩子
						{
							parent->_left = cur->_left; //父结点的左指针指向待删除结点的左子树即可
						}
						else //待删除结点是其父结点的右孩子
						{
							parent->_right = cur->_left; //父结点的右指针指向待删除结点的左子树即可
						}
					}
					delete cur; //释放待删除结点
					return true; //删除成功，返回true
				}
				//else //待删除结点的左右子树均不为空
				//{
					替换法删除
					//Node* minParent = cur; //标记待删除结点右子树当中值最小结点的父结点
					//Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
					寻找待删除结点右子树当中值最小的结点
					//while (minRight->_left)
					//{
					//	//一直往左走，直到找到叶子节点
					//	minParent = minRight;
					//	minRight = minRight->_left;
					//}
					//cur->_key = minRight->_key; //将待删除结点的值改为minRight的值
					此时有两种情况，一种是进入了while循环，minRight是minParent的左孩子
					一种是没有进入while循环，minRight是minParent的右孩子
					//if (minRight == minParent->_left) //minRight是其父结点的左孩子
					//{
					//	minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树
					//}
					//else //minRight是其父结点的右孩子
					//{
					//	minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树
					//}
					//delete minRight; //释放minRight
					//return true; //删除成功，返回true
				//}
				else //待删除结点的左右子树均不为空
				{
					//替换法删除
					Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
					//寻找待删除结点右子树当中值最小的结点
					while (minRight->_left)
					{
						//一直往左走
						minRight = minRight->_left;
					}
					K minKey = minRight->_key; //记录minRight结点的值
					Erase(minKey); //minRight代替待删除结点被删除
					cur->_key = minKey; //将待删除结点的值改为代替其被删除的结点的值，即minRight
				}
			}
		}
		return false; //没有找到待删除结点，删除失败，返回false
	}
	//递归删除函数的子函数
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr) //空树
			return false; //删除失败，返回false

		if (key < root->_key) //key值小于根结点的值
			return _EraseR(root->_left, key); //待删除结点在根的左子树当中
		else if (key > root->_key) //key值大于根结点的值
			return _EraseR(root->_right, key); //待删除结点在根的右子树当中
		else //找到了待删除结点
		{
			if (root->_left == nullptr) //待删除结点的左子树为空
			{
				Node* del = root; //保存根结点
				root = root->_right; //根的右子树作为二叉树新的根结点
				delete del; //释放根结点
			}
			else if (root->_right == nullptr) //待删除结点的右子树为空
			{
				Node* del = root; //保存根结点
				root = root->_left; //根的左子树作为二叉树新的根结点
				delete del; //释放根结点
			}
			//方法一：
			else //待删除结点的左右子树均不为空
			{
				Node* minParent = root; //标记根结点右子树当中值最小结点的父结点
				Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
				//寻找根结点右子树当中值最小的结点
				while (minRight->_left)
				{
					//一直往左走
					minParent = minRight;
					minRight = minRight->_left;
				}
				root->_key = minRight->_key; //将根结点的值改为minRight的值
			//此时有两种情况，一种是进入了while循环，minRight是minParent的左孩子
			//一种是没有进入while循环，minRight是minParent的右孩子
				if (minRight == minParent->_left) //minRight是其父结点的左孩子
				{
					minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树
				}
				else //minRight是其父结点的右孩子
				{
					minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树
				}
				delete minRight; //释放minRight
			}
			return true; //删除成功，返回true
			//方法二：
			//else //待删除结点的左右子树均不为空
			//{
			//	Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
			//	//寻找根结点右子树当中值最小的结点
			//	while (minRight->_left)
			//	{
			//		//一直往左走
			//		minRight = minRight->_left;
			//	}
			//	K minKey = minRight->_key; //记录minRight结点的值
			//	_EraseR(root->_right, minKey); //递归调用，删除右子树当中值为minkey的结点
			//	root->_key = minKey; //将根结点的值改为minRight的值
			//}
		}
	}
	//递归删除函数
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key); //删除_root当中值为key的结点
	}



	//中序遍历的子函数
	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; //指向二叉搜索树的根结点
};
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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396

宿舍门禁

3.2. KV模型：

每一个关键码都有对应的value值，即二叉搜索树的参数为<key,value>。
KV模型在K模型应用的基础上，增加了一些用法。
比如：中英对应字典，通过中文查找英文，统计次数。

KV模型和K模型相比只是多了一个参数：

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode(const K& key, const V& value)
		:_key(key)
		, _value(value)
		, left(nullptr)
		, right(nullptr)
	{}

	const K _key;//KV模式、key不允许修改
	V _value;
	BSTreeNode* left;
	BSTreeNode* right;
};

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;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->left;
			}

			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				return false;//不允许相等
			}
		}

		Node* newnode = new Node(key, value);
		if (parent->_key > key)
			parent->left = newnode;
		else
			parent->right = newnode;
		return true;
	}

	void _InOrder(Node* root)
	{
		if (!root)
			return;
		_InOrder(root->left);
		cout << root->_key << ":" << root->_value << " ";
		_InOrder(root->right);
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	Node* Find(const K& key)//KV模式、value允许修改
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
				cur = cur->left;
			else if (cur->_key < key)
				cur = cur->right;
			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->left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else//找到了、准备进行删除
			{
				if (cur->left == nullptr)//左子树为空
				{
					if (cur == _root)//特殊情况：删除根
					{
						_root = cur->right;
					}
					else
					{
						if (parent->left == cur)//为父节点的左子树
						{
							parent->left = cur->right;
						}
						else if (parent->right == cur)//为父节点的右子树
						{
							parent->right = cur->right;
						}
					}
					delete cur;
				}
				else if (cur->right == nullptr)//右子树为空
				{
					if (cur == _root)//特殊情况：删除根
						_root = cur->left;
					else
					{
						if (parent->left == cur)//为父节点的左子树
						{
							parent->left = cur->left;
						}
						else if (parent->right == cur)//为父节点的右子树
						{
							parent->right = cur->left;
						}
					}
					delete cur;
				}
				else//左右子树都不为空、替代法删除
				{
					Node* smParent = cur;//不能给空、防止Submax就是根
					Node* SubMax = cur->left;//找左树的最大值
					while (SubMax->right)//不断的往右走
					{
						smParent = SubMax;
						SubMax = SubMax->right;
					}
					//找到了左树的最大节点、挪到cur处&&submax一定是右为空的节点
					cur->_key = SubMax->_key;//替代

					if (smParent->right == SubMax)//父节点右边连接
						smParent->right = SubMax->left;
					else//父节点左边连接
						smParent->left = SubMax->left;

					delete SubMax;//释放替代节点
				}
				return true;
			}

		}
		return false;//表示没有找到
	}

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
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

中英文对应字典

统计次数