【C++】二叉搜索树

喜欢的点赞，收藏，关注一下把！

1.二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

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

注意二查搜索树是一个单值树。 如下图：

2.二叉搜索的实现

2.1结点

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2.1基本框架

template<class T>
class BSTree
{
	typedef BSTreeNode<K> Node;

public:
	//构造等。。

	bool Insert(const K& key)
	{}

	bool Erase(const K& key)
	{}

	bool Find(const K& key)
	{}

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

二叉搜索树，没有提供改的成员函数。更准确来说二叉搜索树K模型不能去任意修改key值，可能会破坏二叉搜索树的结构。KV模型可以修改值这个我们下面说。

2.2插入

二叉搜索树的插入不像是普通二叉树插入那样，插入结点之后还需要保持二叉搜索树的形状。因此我们需要先找到要插入结点的位置，然后再插入。

bool Insert(const K& key)
{
	//树为空
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	
	//寻址
	Node* cur = _root;
	while (cur)
	{
		if (_root->_key < key)
			cur = cur->_right;
		else if (_root->_key > key)
			cur = cur->_left;
		else //相等
			return false;
	}
	//插入
	cur = new Node(key);
	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

我这样插入，有没有什么问题？

我们需要一个parent的指针，指向它的父亲结点，然后把9插入到父亲结点指针里，这样才能真正插入到树里。

但是这样写需要注意的是需要知道是插入父亲的左指针，还是右指针。

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

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		//往下走之前，记录一下父亲
		parent = cur;
		if (cur->_key < key)
			cur = cur->_right;
		else if (cur->_key > key)
			cur = cur->_left;
		else
			return false;
	}
	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
27
28
29
30
31
32
33

2.3查找

bool Find(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* cur = _root;
		while(cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			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
21
22
23

2.4删除

删除是二叉搜索树中最难的，情况很多，都需要考虑到。

1. 删7（叶子结点），可以直接删除，但是直接删除7，父亲结点右指针就野指针了。因此我们需要把父亲结点指针置为空。指向7左孩子还是右孩子都可以。
   

2. 删14（只有一个左孩子，右为空），需要找到14的父亲结点，然后让父亲结点右指针指向14的左孩子结点。
   

3. 那还有一种情况肯定是只有一个右孩子，左为空，让父亲指针指向这个右孩子。

其实上面三种情况，可以总结成两种情况。

1. 左孩子为空
2. 右孩子为空

叶子结点，让父亲指向左孩子右孩子都可以。

左为空，父亲指针指向右孩子，右为空，父亲指针指向左孩子。

bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* parent = nullptr;
		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
			{
				//1.左为空
				if (cur->_left == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					delete cur;
				}
				//2.右为空
				else if (cur->_right == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					delete cur;
				}
				//3.左右都不为空
				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
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

先看前左为空，和右为空两种情况，请问有没有上面bug？
如果要被删除的是根节点呢？当前代码行不行？

是不是要报野指针的错误，根本没有parent指针。
那该如何解决呢？
是不是让根结点往下走一步就行了。

	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* parent = nullptr;
		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
			{
				//1.左为空
				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;
				}
				//2.右为空
				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;
				}
				//3.左右都不为空
				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
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

3.左右都不为空

删3，左右都不为空，具体做法如下：
方法1：找左子树最大结点替换删除

将左边最大孩子1，赋值给3，把删3转换成删1。
方法2：找右子树最小结点替换删除

左边最大----->左孩子最右结点
右边左小----->右孩子最左结点

//3.左右都不为空
else
{
	//1.右孩子最小
	Node* Minright = cur->_right;
	Node* parent = nullptr;
	while (Minright->_left)
	{
		parent = Minright;
		Minright = Minright->_left;
	}
	parent->_left = Minright->_right;
	delete Minright;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上面代码有没有上面问题？

对于删除3没有问题。那删除8呢？

10就是右边最小结点，不需要再往下找了。

循环进不去，parent又会带来野指针得问题。该怎么解决？

所以parent初始值不能置为空，设置为cur最好，并且parent的指针也不能那样随意指向，需要判断，Minright是parent的左孩子还是右孩子。

//3.左右都不为空
else
{
	//1.右孩子最小
	Node* Minright = cur->_right;
	Node* parent = cur;
	while (Minright->_left)
	{
		parent = Minright;
		Minright = Minright->_left;
	}
	if (parent->_left == Minright)
	{
		parent->_left = Minright->_right;
	}
	else
	{
		parent->_right == Minright->_right;
	}
	delete Minright;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

完整代码

bool Erase(const K& key)
{
	if (_root == nullptr)
		return false;

	Node* parent = nullptr;
	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
		{
			//1.左为空
			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;
			}
			//2.右为空
			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;
			}
			//3.左右都不为空
			else
			{
				//1.右孩子最小
				Node* Minright = cur->_right;
				Node* parent = cur;
				while (Minright->_left)
				{
					parent = Minright;
					Minright = Minright->_left;
				}
				cur->_key=Minright->_key;
				if (parent->_left == Minright)
				{
					parent->_left = Minright->_right;
				}
				else
				{
					parent->_right = Minright->_right;
				}
				delete Minright;

			}
			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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

如果想替换成左孩子最大，代码完全类似。

//3.左右都不为空
else
{
	//2.左孩子最大
	Node* Maxleft = cur->_left;
	Node* parent = cur;
	while (Maxleft->_right)
	{
		parent = Maxleft;
		Maxleft = Maxleft->_right;
	}
	cur->_key = Maxleft->_key;
	if (parent->_left == Maxleft)
	{
		parent->_left = Maxleft->_left;
	}
	else
	{
		parent->_right = Maxleft->_left;
	}
	delete Maxleft;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.5打印

二叉搜索树中序是一个递增序列。
中序遍历代码很简单。但是注意我们这是在类里面的中序遍历。

	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

中序需要把_root传就去，但是_root是一个私有成员变量不能访问。
在类里面写递归函数都会遇到这样的问题。
1.写一个Getroot的函数
2.套一层，写个子函数

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

private:
	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
12
13
14
15

3.二叉搜索树递归实现

递归代码量少，但是理解起来比较困难。一般建议有循环先写循环，然后再考虑写递归。

对于二叉树的递归，我们要有分治的思想，先处理根结点这棵树，然后再左子树右子树，因为左子树和右子树的处理方法和根结点这个树是一样的。

其实二叉搜索树的递归都是一个思想，空要怎么处理，比根大递归往右，比根小递归往左。

3.1查找

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

private:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (root->_key < key)
			return _FindR(root->_right, key);
		else if (root->_key > key)
			return _Findr(root->_left, key);
		else
			return true;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.2插入

如果为空就申请结点插入，比根大往右，比根小往左，和根相等插入失败。

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

		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left,key);
		else
			return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个代码还不完整，有问题。
假如插入为空的时候，插入8，再插入3。

插入3的时候，根本没有插上。
这里只修改一处地方就成了。

//给指针加个别名
bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left,_key);
		else
			return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

root虽然指向你，但是同时又是父亲的左指针或右指针的别名

3.3删除

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

		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _Erase(root->_left, key);
		}
		else
		{
			//1.左为空
			//2.右为空
			//3.左右都为空
			if (root->_left == nullptr)
			{

			}
			else if (root->_right == nullptr)
			{

			}
			else
			{

			}
			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

这里还需要再去申请一个parent吗？还需要知道7是父亲的左孩子还是右孩子吗？

显然是不用的，刚才说过，root虽然指向你，但是同时又是父亲的左指针或右指针的别名

root是父亲(6)的右指针的别名。这里就已经知道7是父亲的右指针了。并且也不用担心父亲为空的情况。

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

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

	}
	else
	{
		//1.左为空
		//2.右为空
		//3.左右都为空
		Node* cur = root;//注意不能直接删除root，因为下面root已经改变了，所以必须保存要被删除的结点
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_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

左右都不为空，可以向非递归那样删除。也可以交换删除。

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

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

	}
	else
	{
		//1.左为空
		//2.右为空
		//3.左右都为空
		Node* cur = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			Node* Minright = root->_right;
			while (Minright->_left)
			{

				Minright = Minright->_left;
			}
			swap(root->_key, Minright->_key);
			return _EraseR(root->_right, key);
		}
		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

非递归删除

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

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

		}
		else
		{
			//1.左为空
			//2.右为空
			//3.左右都为空
			Node* cur = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* Minright = root->_right;
				Node* parent = root;
				while (Minright->_left)
				{
					parent = Minright;
					Minright = Minright->_left;
				}
				root->_key = Minright->_key;
				if (Minright == parent->_left)
				{
					parent->_left = Minright->_right;
				}
				else
				{
					parent->_right = Minright->_right;
				}
				delete Minright;
				return true;
			}
			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

4.二叉搜索树默认成员函数

4.1构造

//构造
BSTree()
	:_root(nullptr)
{}
1
2
3
4

4.2析构

删除二叉树一般采用后序递归删除。

~BSTree()
{
	Delete(_root);
}
	
private:
	void Delete(Node* root)
	{
		if (root == nullptr)
			return;

		Delete(root->_left);
		Delete(root->_right);
		delete root;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.3拷贝构造

构建一个二叉树一般建议前序递归创建

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newnode = new Node(root->_key);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.4赋值重载

传统写法

BSTree<K>& operator=(const BSTree<K>& t)
{
	if (this != &t)
	{
		Delete(_root);
		_root = Copy(t._root);
	}
	return *this;
}
1
2
3
4
5
6
7
8
9

现代写法，复用拷贝构造函数

//现代写法
BSTree<K>& operator=(BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}
1
2
3
4
5
6

6.二叉搜索树的应用

6.1K模型

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

K模型不允许插入相同的key值，也不允许修改key，否则可能破坏K模型的结构。

假设让写一段程序，用来检测英语作家，写作内容是否拼写错误。
这时可以采用K模型。

1. 把词库中的单词作为Key，构建一颗搜索二叉树
2. 在二叉搜索树中检索每个单词是否在这个树中，不再就报错。

Key的搜索模型------>判断在不在？

6.2KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

通过Key查找或修改Value。 K模型不允许修改，KV模型允许修改。

KV模型就是增加了一个V类型。Find成员函数的返回值需要修改一下。

template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;

		BSTreeNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};


template<class K,class V>
class BSTree
{
	typedef BSTreeNode<K,V> Node;

public:
	//构造
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K,V>& t)
	{
		_root = Copy(t._root);
	}


	//现代写法
	BSTree<K,V>& operator=(BSTree<K,V> t)
	{
		swap(_root, t._root);
		return *this;
	}


	~BSTree()
	{
		Delete(_root);
		_root = nullptr;
	}


	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)
		{
			//往下走之前，记录一下父亲
			parent = cur;
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				return false;
		}
		cur = new Node(key,value);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;

	}

	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		Node* parent = nullptr;
		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
			{
				//1.左为空
				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;
				}
				//2.右为空
				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;
				}
				//3.左右都不为空
				else
				{
					//1.右孩子最小
					/*Node* Minright = cur->_right;
					Node* parent = cur;
					while (Minright->_left)
					{
						parent = Minright;
						Minright = Minright->_left;
					}
					if (parent->_left == Minright)
					{
						parent->_left = Minright->_right;
					}
					else
					{
						parent->_right = Minright->_right;
					}
					delete Minright;*/
					//2.左孩子最大
					Node* Maxleft = cur->_left;
					Node* parent = cur;
					while (Maxleft->_right)
					{
						parent = Maxleft;
						Maxleft = Maxleft->_right;
					}
					cur->_key = Maxleft->_key;
					if (parent->_left == Maxleft)
					{
						parent->_left = Maxleft->_left;
					}
					else
					{
						parent->_right = Maxleft->_left;
					}
					delete Maxleft;

				}
				return true;
			}

		}
		return false;

	}

	Node* Find(const K& key)
	{
		if (_root == nullptr)
			return nullptr;

		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}


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

private:

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newnode = new Node(root->_key,root->_value);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}

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

		Delete(root->_left);
		Delete(root->_right);
		delete root;
	}


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

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

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

假设，实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文。
我们可以采用KV模型实现。

void TestBSTree4()
{
	KV::BSTree<string ,string> kv;
	kv.Insert("sort", "排序");
	kv.Insert("search", "搜索");
	kv.Insert("left", "左边");
	kv.Insert("right", "右边");
	string str;
	while (cin >> str)
	{
		auto* ptr = kv.Find(str);
		if (ptr)
		{
			cout << ptr->_key << ":" << ptr->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

统计每样水果出现的次数

void TestBSTree5()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	KV::BSTree<string, int> count;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		auto* ret = count.Find(str);
		if (ret == nullptr)
		{
			count.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	count.InOrder();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

KV搜索模型------>通过一个值去查找或者修改另一个值。

那以后想用二叉搜索树难道要手撕一个出来吗？
其实后面学的map对应KV模型，set对应模型，不用担心。

7.二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$lo{g}_{2}N$

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？
那么我们后续学习的AVL树和红黑树就可以上场了。