二叉树（进阶）

1.内容安排说明

二叉树在前面c数据结构阶段；已经讲过了；本节取名二叉树进阶的原因是：
1.map和set特性需要先铺垫二叉搜索树 ，而二叉搜索树也是一种树形结构；
2. 二叉搜索树的特性了解，有助于更好的理解map和set的特性
3. 二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘
4. 有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。

因此本节借二叉树搜索树，对二叉树部分进行收尾总结。

2. 二叉搜索树

2.1二叉搜索树的概念

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

2.2二叉搜索树的实现

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

};
template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	
	void Swap(Node* a, Node* b)
	{
		Node s = *a;
		*a = *b;
		*b = s;
	}
	
   //出先两个函数的原因是：这里使用了递归；递归需要使用递归类控制循环次数；所以使用类get函数进行调用；
	bool Find(const K& key)
	{
		return _Find(_root, key);

	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	bool Insert(const K& key)
	{
		return _Insert(_root, key);
	}
	bool Erase(const K& key)
	{
		return _Erase(_root, key);
	}
	~BSTree()
	{
		Destroy(_root);
	}
	BSTree()
	{

	}
	BSTree(const BSTree<K>& t )
	{
		_root = Copy(t._root);
	}
	BSTree<K>& operator = (const BSTree<K> t)
	{
		swap(_root,t._root);
	    return *this;
	}
	

private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	bool _Find(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		else
		{
			if (key > root->_key)
			{
				_Find(root->_right, key);
			}
			else if (key < root->_key)
			{
				_Find(root->_left, key);
			}
			else
			{
				return true;
			}
		}

	}
	bool _Insert(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key > root->_key)
		{
			_Insert(root->_right, key);

		}
		else if (key < root->_key)
		{
			_Insert(root->_left, key);

		}
		else
		{
			return false;
		}

	}
	bool _Erase(Node*& root, const K& key)
	{
	if (root == nullptr)
	{
		return false;
	}
	else
	{
		if (key > root->_key)
		{
			return _Erase(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _Erase(root->_left, key);

		}
		else
		{
			if (root->_right == nullptr)
			{
				Node* n = root;
				root = root->_left;
				delete n;
				return true;
			}
			else if (root->_left == nullptr)
			{
				Node* n = root;
				root = root->_right;
				delete n;
				return true;
			}
			else
			{
				Node* cur = root->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				swap(cur->_key, root->_key);
				return _Erase(_root->_right, key);

			}
		}
	}
    }
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

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

2.3二叉树的性能：

二叉树的时间复杂度：这里的是时间复杂度测量的是查找的时间复杂度；原因：删除和添加都修要使用查找哦来进行；
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$lo{g}_{2}N$
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

搜索二叉树的应用

k 模型

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

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

kv模型

定义：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：

• 比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
 {
 BSTNode(const K& key = K(), const V& value = V())
   : _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value)
 {}
  BSTNode<T>* _pLeft;
 BSTNode<T>* _pRight;
 K _key;
    V _value
 };
template<class K, class V>
class BSTree
 {
 typedef BSTNode<K, V> Node;
 typedef Node* PNode;
public:
 BSTree(): _pRoot(nullptr){}
 PNode Find(const K& key);
 bool Insert(const K& key, const V& value)
 bool Erase(const K& key)
private:
 PNode _pRoot;
比特就业课
2.5 二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
 };
void TestBSTree3()
{
 // 输入单词，查找单词对应的中文翻译
 BSTree<string, string> dict;
 dict.Insert("string", "字符串");
 dict.Insert("tree", "树");
 dict.Insert("left", "左边、剩余");
 dict.Insert("right", "右边");
 dict.Insert("sort", "排序");
 // 插入词库中所有单词
 string str;
 while (cin>>str)
 {
 BSTreeNode<string, string>* ret = dict.Find(str);
 if (ret == nullptr)
 {
 cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;
 }
 else
 {
 cout << str << "中文翻译:" << ret->_value << endl;
 }
 }
}
void TestBSTree4()
{
 // 统计水果出现的次数
 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", 
"苹果", "香蕉", "苹果", "香蕉" };
 BSTree<string, int> countTree;
 for (const auto& str : arr)
 {
 // 先查找水果在不在搜索树中
 // 1、不在，说明水果第一次出现，则插入<水果, 1>
 // 2、在，则查找到的节点中水果对应的次数++
 //BSTreeNode* ret = countTree.Find(str);
 auto ret = countTree.Find(str);
 if (ret == NULL)
 {
 countTree.Insert(str, 1);
 }
 else
 {
 ret->_value++;
 }
 }
 countTree.InOrder();
}
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

搜索二叉树的实现和应用源码