• ＜二叉搜索树＞——《C++高阶》

    目录

    1.内容说明： 

    2. 二叉搜索树

    2.1 二叉搜索树概念

    2.2 二叉搜索树操作

    1. 二叉搜索树的查找

    2. 二叉搜索树的插入

    3. 二叉搜索树的删除

    2.3 二叉搜索树的实现

    2.4 二叉搜索树的应用

    2.5 二叉搜索树的性能分析

    3.二叉搜索树的模拟实现：

    3.1二叉搜索树（K模型）

    3.1.1定义二叉搜索树的结构：​

    3.1.2功能函数：

    （1）非递归版Insert：​

    （2）非递归版Find​

    （3）非递归版Erase​

    （4）递归版InsertR：

    ​（5）递归版FindR​

    （6）递归版EraseR：​

    3.1.3: 遍历（递归版）：

    3.1.4完整源码：

    （1）BSTreeKey.h:

    （2）test.cpp:

    3.2二叉搜索树（KV模型） 

    3.2.1 二叉树KV模型结构定义：​

    3.2.2功能函数

    （1）非递归版Insert、Find、Erase​

    （2）递归版InsertR、FindR、EraseR：​

     3.2.3遍历（递归版）：

     3.2.4完整源码：

    （1）BSTreeKeyValue.h:

    （2）test.cpp:

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

    1.内容说明： 

    二叉树在前面C数据结构阶段已经学习了解，这里开始新的章节学习：
    1. map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构
    2. 二叉搜索树的特性了解，有助于更好的理解map和set的特性
    3. 二叉树中部分面试题稍微有点难度，在前面学习不容易接受，且时间长容易忘
    4. 有些OJ题使用C语言方式实现比较麻烦
    因此这里学习二叉树搜索树，对二叉树部分进行总结。

    2. 二叉搜索树

    2.1 二叉搜索树概念

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

     int a [] = {5,3,4,1,7,8,2,6,0,9};

    2.2 二叉搜索树操作

    1. 二叉搜索树的查找

    2. 二叉搜索树的插入

    插入的具体过程如下：
    a. 树为空，则直接插入

     

     b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

    3. 二叉搜索树的删除

    首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
    a. 要删除的结点无孩子结点
    b. 要删除的结点只有左孩子结点
    c. 要删除的结点只有右孩子结点
    d. 要删除的结点有左、右孩子结点
    看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
    情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
    情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
    情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中， 再来处理该结点的删除问题

     2.3 二叉搜索树的实现 

    1. template<class T>
    2. struct BSTNode
    3. {
    4. 	BSTNode(const T& data = T())
    5. 		: _pLeft(nullptr), _pRight(nullptr), _data(data)
    6. 	{}
    7. 	BSTNode* _pLeft;
    8. 	BSTNode* _pRight;
    9. 	T _data;
    10. };
    11. template<class T>
    12. class BSTree
    13. {
    14. 	typedef BSTNode Node;
    15. 	typedef Node* PNode;
    16. public:
    17. 	BSTree() : _pRoot(nullptr)
    18. 	{}
    19. 	// 同学们自己实现，与二叉树的销毁类似
    20. 	~BSTree();
    21. 	// 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置
    22. 	PNode Find(const T& data);
    23. 	bool Insert(const T& data)
    24. 	{
    25. 		// 如果树为空，直接插入
    26. 		if (nullptr == _pRoot)
    27. 		{
    28. 			_pRoot = new Node(data);
    29. 			return true;
    30. 		}
    31. 		// 按照二叉搜索树的性质查找data在树中的插入位置
    32. 		PNode pCur = _pRoot;
    33. 		// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置
    34. 		PNode pParent = nullptr;
    35. 		while (pCur)
    36. 		{
    37. 			pParent = pCur;
    38. 			if (data < pCur->_data)
    39. 				pCur = pCur->_pLeft;
    40. 			else if (data > pCur->_data)
    41. 				pCur = pCur->_pRight; // 元素已经在树中存在
    42. 			else
    43. 				return false;
    44. 		}
    45. 		// 插入元素
    46. 		pCur = new Node(data);
    47. 		if (data < pParent->_data)
    48. 			pParent->_pLeft = pCur;
    49. 		else
    50. 			pParent->_pRight = pCur; return true;
    51. 	}
    52. 	bool Erase(const T& data)
    53. 	{
    54. 		// 如果树为空，删除失败
    55. 		if (nullptr == _pRoot)
    56. 			return false;
    57. 		// 查找在data在树中的位置
    58. 		PNode pCur = _pRoot;
    59. 		PNode pParent = nullptr;
    60. 		while (pCur)
    61. 		{
    62. 			if (data == pCur->_data)
    63. 				break;
    64. 			else if (data < pCur->_data)
    65. 			{
    66. 				pParent = pCur;
    67. 				pCur = pCur->_pLeft;
    68. 			}
    69. 			else
    70. 			{
    71. 				pParent = pCur;
    72. 				pCur = pCur->_pRight;
    73. 			}
    74. 		}
    75. 		// data不在二叉搜索树中，无法删除
    76. 		if (nullptr == pCur)
    77. 			return false;
    78. 		// 分以下情况进行删除，同学们自己画图分析完成
    79. 		if (nullptr == pCur->_pRight)
    80. 		{
    81. 			// 当前节点只有左孩子或者左孩子为空---可直接删除
    82. 		}
    83. 		else if (nullptr == pCur->_pRight)
    84. 		{
    85. 			// 当前节点只有右孩子---可直接删除
    86. 		}
    87. 		else
    88. 		{
    89. 			// 当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，比如：
    90. 			// 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节点，即右子树中最小的节点
    91. 				// 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
    92. 		}
    93. 		return true;
    94. 	}
    95. 	// 同学们自己实现
    96. 	void InOrder();
    97. private:
    98. 	PNode _pRoot;
    99. }

    2.4 二叉搜索树的应用

    1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
    以单词集合中的每个单词作为key，构建一棵二叉搜索树
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
    2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。
    比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下： <单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较 Key 查询英文单词时，只需给出英文单词，就可快速找到与其对应的key 

    1. template<class K, class V>
    2. struct BSTNode
    3. {
    4. 	BSTNode(const K& key = K(), const V& value = V())
    5. 		: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
    6. 	{}
    7. 	BSTNode* _pLeft;
    8. 	BSTNode* _pRight;
    9. 	K _key;
    10. 	V _value
    11. };
    12. template<class K, class V>
    13. class BSTree
    14. {
    15. 	typedef BSTNode Node;
    16. 	typedef Node* PNode;
    17. public:
    18. 	BSTree() : _pRoot(nullptr)
    19. 	{}
    20. 	// 同学们自己实现，与二叉树的销毁类似
    21. 	~BSTree();
    22. 	// 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置
    23. 	PNode Find(const K& key);
    24. 	bool Insert(const K& key, const V& value)
    25. 	{
    26. 		// ...
    27.  
    28. 		PNode pCur = _pRoot;
    29. 		PNode pParent = nullptr;
    30. 		while (pCur)
    31. 		{
    32. 			pParent = pCur;
    33. 			if (key < pCur->_key)
    34. 				pCur = pCur->_pLeft;
    35. 			else if (key > pCur->_key)
    36. 				pCur = pCur->_pRight; // 元素已经在树中存在
    37. 			else
    38. 				return false;
    39. 		}
    40. 		// ...
    41. 		return true;
    42. 	}
    43. 	bool Erase(const K& key)
    44. 	{
    45. 		// ...
    46. 		return true;
    47. 	}
    48. private:
    49. 	PNode _pRoot;
    50. };

    插入数据，然后去重，进行排序

    递归的问题：虽然代码简短，但如果深度太大，可能会溢出。

    2.5 二叉搜索树的性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
    对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
    但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
    问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？

    3.二叉搜索树的模拟实现：

    3.1二叉搜索树（K模型）

     3.1.1定义二叉搜索树的结构：

     

    3.1.2功能函数：

    （1）非递归版Insert：

     （2）非递归版Find

     （3）非递归版Erase

    （4）递归版InsertR：

     （5）递归版FindR

    （6）递归版EraseR： 3.1.3: 遍历（递归版）：

    中序遍历、前序遍历、后序遍历

     

    3.1.4 完整源码：

    （1）BSTreeKey.h:

    1. #pragma once
    2. //二叉搜索树  BinarySearchTree  K模型
    3. //一般不允许冗余，会进行去重，所以可有使用搜索树去重
    4. #include
    5. using namespace std;
    6. template<class K>      //根据传过来的值类型，K即为类型。例int、double等
    7. struct BSTreeNode
    8. {
    9. 	BSTreeNode* _left;
    10. 	BSTreeNode* _right;
    11.  
    12. 	K _key;     //类型为K的类型，一般不允许修改，防止破坏树形结构
    13. 	BSTreeNode(const K& key)
    14. 		:_left(nullptr)
    15. 		, _right(nullptr)
    16. 		, _key(key)
    17. 	{}
    18. };
    19.  
    20. template<class K>
    21. class BSTree
    22. {
    23. 	typedef BSTreeNode Node;
    24. public:
    25. 	//C++11支持default
    26. 	BSTree() = default;  //拷贝构造函数也是构造函数，只要写构造函数就不会生成默认构造，这里强制生成构造函数
    27.  
    28. 	Node* CopyTree(Node* root)
    29. 	{
    30. 		if (root == nullptr)
    31. 			return nullptr;
    32. 		Node* copyNode = new Node(root->_key);
    33. 		copyNode->_left = CopyTree(root->_left);
    34. 		copyNode->_right = CopyTree(root->_right);
    35. 		return copyNode;
    36. 	}
    37. 	BSTree(const BSTree& t)  //实现深拷贝
    38. 	{
    39. 		_root = CopyTree(t._root);
    40. 	}
    41. 	//赋值重载 例：t2=t1;
    42. 	//现代写法
    43. 	BSTree& operator=(BSTree t)
    44. 	{
    45. 		swap(_root, t._root);
    46. 		return *this;
    47. 	}
    48. 	void DestroyTree(Node* root)
    49. 	{
    50. 		if (root == nullptr)
    51. 			return;
    52. 		DestroyTree(root->_left);
    53. 		DestroyTree(root->_right);
    54. 		delete root;
    55. 	}
    56. 	~BSTree()  //因为析构函数没有参数，要写成递归就得借用成员函数，嵌套一层
    57. 	{
    58. 		DestroyTree(_root);
    59. 		_root = nullptr;
    60. 	}
    61. 	//非递归insert
    62. 	bool Insert(const K& key)   //一般不允许冗余，会进行去重
    63. 	{
    64. 		if (_root == nullptr)
    65. 		{
    66. 			_root = new Node(key);
    67. 			return true;
    68. 		}
    69. 		Node* parent = nullptr;
    70. 		Node* cur = _root;
    71. 		while (cur)
    72. 		{
    73. 			//不允许冗余
    74. 			if (cur->_key < key)
    75. 			{
    76. 				parent = cur;
    77. 				cur = cur->_right;
    78. 			}
    79. 			else if (cur->_key > key)
    80. 			{
    81. 				parent = cur;
    82. 				cur = cur->_left;
    83. 			}
    84. 			else
    85. 			{
    86. 				return false;
    87. 			}
    88. 			/*//允许冗余
    89. 			if (cur->_key < key)
    90. 			{
    91. 				parent = cur;
    92. 				cur = cur->_right;
    93. 			}
    94. 			else
    95. 			{
    96. 				parent = cur;
    97. 				cur = cur->_left;
    98. 			}*/
    99. 		}
    100. 		cur = new Node(key);
    101. 		if (parent->_key < key)
    102. 		{
    103. 			parent->_right = cur;
    104. 		}
    105. 		else
    106. 		{
    107. 			parent->_left = cur;
    108. 		}
    109. 		return true;
    110. 	}
    111. 	//非递归find
    112. 	bool Find(const K& key)
    113. 	{
    114. 		Node* cur = _root;
    115. 		while (cur)
    116. 		{
    117. 			if (cur->_key < key)
    118. 			{
    119. 				cur = cur->_right;
    120. 			}
    121. 			else if (cur->_key > key)
    122. 			{
    123. 				cur = cur->_left;
    124. 			}
    125. 			else
    126. 			{
    127. 				return true;
    128. 			}
    129. 		}
    130. 		return false;
    131. 	}
    132. 	//非递归erase
    133. 	//删除情况很多，需要分情况讨论
    134. 	//1.当删除的是父结点时，采用替换法：
    135. 	//找父结点的左子树的（所有值的）最大值结点或右子树的（所有值的）最小值结点替换被删除的父结点
    136. 	//2.当删除的是叶结点，直接删除，再链接
    137. 	bool Erase(const K& key)
    138. 	{
    139. 		Node* parent = nullptr;
    140. 		Node* cur = _root;
    141. 		while (cur)
    142. 		{
    143. 			if (cur->_key < key)
    144. 			{
    145. 				parent = cur;
    146. 				cur = cur->_right;
    147. 			}
    148. 			else if (cur->_key > key)
    149. 			{
    150. 				parent = cur;
    151. 				cur = cur->_left;
    152. 			}
    153. 			else
    154. 			{
    155. 				//一个孩子--左为空or右为空
    156.  
    157. 				if (cur->_left == nullptr)
    158. 				{
    159. 					//if(parent==nullptr)
    160. 					if (cur == _root)
    161. 					{
    162. 						_root = cur->_right;
    163. 					}
    164. 					else
    165. 					{
    166. 						if (cur == parent->_left)
    167. 						{
    168. 							parent->_left = cur->_right;
    169. 						}
    170. 						else
    171. 						{
    172. 							parent->_right = cur->_right;
    173. 						}
    174. 					}
    175. 					delete cur;
    176. 				}
    177. 				else if (cur->_right == nullptr)
    178. 				{
    179. 					//if(parent==nullptr)
    180. 					if (cur == _root)
    181. 					{
    182. 						_root = cur->_left;
    183. 					}
    184. 					else
    185. 					{
    186. 						if (cur == parent->_left)
    187. 						{
    188. 							parent->_left = cur->_left;
    189. 						}
    190. 						else
    191. 						{
    192. 							parent->_right = cur->_left;
    193. 						}
    194. 					}
    195. 					delete cur;
    196.  
    197. 				}
    198. 				else  //两个孩子都不为空 //删除有两个孩子的结点：替换法
    199. 				{
    200. 					//1.使用右子树的最小值结点替代
    201. 					Node* minParent = cur;
    202. 					Node* minRight = cur->_right;
    203. 					while (minRight->_left)
    204. 					{
    205. 						minParent = minRight;
    206. 						minRight = minRight->_left;
    207. 					}
    208. 					swap(minRight->_key, cur->_key); //或cur->_key = minRight->_key;
    209. 					if (minParent->_left == minRight)
    210. 					{
    211. 						minParent->_left = minRight->_right;
    212. 					}
    213. 					else
    214. 					{
    215. 						minParent->_right = minRight->_right;
    216. 					}
    217. 					delete minRight;
    218.  
    219. 					2.使用左子树的最大值结点替代
    220. 					//Node* maxParent = cur;
    221. 					//Node* maxLeft = cur->_left;
    222. 					//while (maxLeft->_right)
    223. 					//{
    224. 					//	maxParent = maxLeft;
    225. 					//	maxLeft = maxLeft->_right;
    226. 					//}
    227. 					//swap(maxLeft->_key, cur->_key); //或cur->_key = maxLeft->_key;
    228. 					//if (maxParent->_right == maxLeft)
    229. 					//{
    230. 					//	maxParent->_right = maxLeft->_left;
    231. 					//}
    232. 					//else
    233. 					//{
    234. 					//	maxParent->_left = maxLeft->_left;
    235. 					//}
    236. 					//delete maxLeft;
    237. 				}
    238. 				return true;
    239. 			}
    240.  
    241. 		}
    242. 		return false;
    243. 	}
    244. 	/
    245. 	//递归
    246. 	//无法直接使用私有成员进行递归，因此嵌套一层成员函数，实现递归
    247. 	//递归find
    248. 	bool FindR(const K& key)
    249. 	{
    250. 		return _FindR(_root, key);
    251. 	}
    252. 	//递归insert
    253. 	bool InsertR(const K& key)
    254. 	{
    255. 		return _InsertR(_root, key);
    256. 	}
    257. 	//递归erase
    258. 	bool EraseR(const K& key)
    259. 	{
    260. 		return _EraseR(_root, key);
    261. 	}
    262. private:
    263. 	//递归insert
    264. 	bool _InsertR(Node*& root, const K& key)
    265. 	{
    266. 		//Node*& root这个处理，使得当root为空指针时，但root同时也是父结点的left或right的别名，使得结点得以链接
    267. 		if (root == nullptr)
    268. 		{
    269. 			root = new Node(key);
    270. 			return true;
    271. 		}
    272. 		if (root->_key < key)
    273. 			return _InsertR(root->_right, key);
    274. 		else if (root->_key > key)
    275. 			return _InsertR(root->_left, key);
    276. 		else
    277. 			return false;
    278. 	}
    279. 	//递归FindR
    280. 	bool _FindR(Node* root, const K& key)
    281. 	{
    282. 		if (root == nullptr)
    283. 			return false;
    284. 		if (root->_key < key)
    285. 		{
    286. 			return _FindR(root->_right, key);
    287. 		}
    288. 		else if (root->_key > key)
    289. 		{
    290. 			return _FindR(root->_left, key);
    291. 		}
    292. 		else
    293. 		{
    294. 			return true;
    295. 		}
    296. 	}
    297. 	//递归erase
    298. 	bool _EraseR(Node*& root, const K& key)
    299. 	{
    300. 		if (root == nullptr)
    301. 			return false;
    302. 		if (root->_key < key)
    303. 		{
    304. 			return _EraseR(root->_right, key);
    305. 		}
    306. 		else if (root->_key > key)
    307. 		{
    308. 			return _EraseR(root->_left, key);
    309. 		}
    310. 		else
    311. 		{
    312. 			Node* del = root; //先保存一下
    313. 			if (root->_left == nullptr)
    314. 			{
    315. 				root = root->_right;
    316. 			}
    317. 			else if (root->_right == nullptr)
    318. 			{
    319. 				root = root->_left;
    320. 			}
    321. 			else
    322. 			{
    323. 				//1.使用右子树的最小值结点替代
    324. 				Node* minRight = root->_right;
    325. 				while (minRight->_left)
    326. 				{
    327. 					minRight = minRight->_left;
    328. 				}
    329. 				swap(root->_key, minRight->_key);
    330. 				return _EraseR(root->_right, key);
    331.  
    332. 				2.使用左子树的最大值结点替代
    333. 				//Node* maxLeft = root->_left;
    334. 				//while (maxLeft->_right)
    335. 				//{
    336. 				//	maxLeft = maxLeft->_right;
    337. 				//}
    338. 				//swap(root->_key, maxLeft->_key);
    339. 				//return _EraseR(root->_left, key);
    340. 			}
    341. 			delete del;
    342. 			return true;
    343. 		}
    344. 	}
    345.  
    346. public:
    347. 	//递归版遍历
    348. 	void InOrder()          //1.中序遍历
    349. 	{
    350. 		_InOrder(_root);
    351. 		cout << endl;
    352. 	}
    353. 	void PrevOrder()        //2.前序遍历
    354. 	{
    355. 		_PrevOrder(_root);
    356. 		cout << endl;
    357. 	}
    358. 	void PostOrder()       //3.后序遍历
    359. 	{
    360. 		_PostOrder(_root);
    361. 		cout << endl;
    362. 	}
    363. private:
    364. 	//在C语言中，root可以被直接获取，
    365. 	//在C++中，因为_root 是私有，被封装起来了所以可有以下两种方式获得
    366. 	//1.可以写一个成员函数GetRoot()获取
    367. 	//2.也可以使用遍历，不被继承就设为私有成员函数
    368.  
    369. 	void _InOrder(Node* root)     //1.中序遍历
    370. 	{
    371. 		if (root == nullptr)
    372. 			return;
    373. 		_InOrder(root->_left);
    374. 		cout << root->_key << " ";
    375. 		_InOrder(root->_right);
    376. 	}
    377. 	void _PrevOrder(Node* root)   //2.前序遍历
    378. 	{
    379. 		if (root == nullptr)
    380. 			return;
    381. 		cout << root->_key << " ";
    382. 		_PrevOrder(root->_left);
    383. 		_PrevOrder(root->_right);
    384. 	}
    385. 	void _PostOrder(Node* root)   //3.后序遍历
    386. 	{
    387. 		if (root == nullptr)
    388. 			return;
    389. 		_PostOrder(root->_left);
    390. 		_PostOrder(root->_right);
    391. 		cout << root->_key << " ";
    392. 	}
    393. private:
    394. 	Node* _root = nullptr;  //调用自定义类型Node*
    395. };

    （2）test.cpp:

    1. #include"BSTreeKey.h"
    2.  
    3. void TestBSTree1()
    4. {
    5. 	BSTree<int> t;
    6. 	//int a[] = {8,3,1,10,6,4,7,14,13 };
    7. 	//int a[] = {8,3,1,10,6,4,7,14,13,10,6 };   //冗余测试
    8.  
    9. 	int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    10. 	for (auto e : a)
    11. 	{
    12. 		t.Insert(e);
    13. 	}
    14. 	t.InOrder();
    15. 	t.Insert(16);
    16. 	t.Insert(9);
    17. 	t.InOrder();
    18. }
    19. void TestBSTree2()
    20. {
    21. 	BSTree<int> t;
    22. 	int a[] = { 8,3,1,10,6,4,7,14,13 };
    23. 	//int a[] = {8,3,1,10,6,4,7,14,13,10,6 };   //冗余测试
    24. 	//int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    25. 	for (auto e : a)
    26. 	{
    27. 		t.Insert(e);
    28. 	}
    29. 	t.InOrder();
    30. 	t.PrevOrder();
    31. 	t.PostOrder();
    32. 	//t.Erase(8);
    33. 	//t.Erase(10);
    34. 	//t.Erase(3);
    35. 	//t.Erase(7);
    36. 	//t.Erase(6);
    37. 	//t.Erase(14);
    38. 	//t.Erase(13);
    39. 	//t.InOrder();
    40.  
    41. 	/*for (auto e : a)
    42. 	{
    43. 		t.Erase(e);
    44. 	}
    45. 	t.InOrder();*/
    46. }
    47. void TestBSTree3()
    48. {
    49. 	BSTree<int> t;
    50. 	int a[] = { 8,3,1,10,6,4,7,14,13 };
    51. 	//int a[] = {8,3,1,10,6,4,7,14,13,10,6 };   //冗余测试
    52. 	//int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    53. 	//非递归insert
    54. 	/*for (auto e : a)
    55. 	{
    56. 		t.Insert(e);
    57. 	}*/
    58. 	//递归insertR
    59. 	/*for (auto e : a)
    60. 	{
    61. 		t.InsertR(e);
    62. 	}
    63. 	t.InOrder();*/
    64.  
    65. 	//BSTree copy=t;  //浅拷贝
    66. 	//copy.InOrder();
    67. 	t.Find(10);
    68. 	t.FindR(10);
    69.  
    70. }
    71. void TestBSTree4()
    72. {
    73. 	BSTree<int> t;
    74. 	int a[] = { 8,3,1,10,6,4,7,14,13 };
    75. 	//int a[] = {8,3,1,10,6,4,7,14,13,10,6 };   //冗余测试
    76. 	//int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    77. 	//非递归insert
    78. 	for (auto e : a)
    79. 	{
    80. 		t.Insert(e);
    81. 	}
    82. 	//递归insertR
    83. 	/*for (auto e : a)
    84. 	{
    85. 		t.InsertR(e);
    86. 	}*/
    87. 	t.InOrder();
    88. 	t.EraseR(13);
    89. 	t.EraseR(10);
    90. 	t.EraseR(8);
    91. 	t.EraseR(3);
    92.  
    93. 	t.InOrder();
    94.  
    95. 	for (auto e : a)
    96. 	{
    97. 		t.EraseR(e);
    98. 	}
    99. 	t.InOrder();
    100.  
    101. }
    102. int main()
    103. {
    104. 	//TestBSTree1();
    105. 	//TestBSTree2();
    106. 	//TestBSTree3();
    107. 	TestBSTree4();
    108.  
    109. 	return 0;
    110. }

    可画功能函数递归展开图进行分析

    3.2二叉搜索树（KV模型） 

    3.2.1 二叉树KV模型结构定义：

     

    3.2.2功能函数

    （1）非递归版Insert、Find、Erase 

    （2）递归版InsertR、FindR、EraseR： 3.2.3遍历（递归版）：

    中序遍历、前序遍历、后序遍历：

     

     3.2.4完整源码：

    （1）BSTreeKeyValue.h:

    1. #pragma once
    2. //二叉搜索树  BinarySearchTree-KeyValue模型
    3.  
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. template<class K,class V>      
    9. struct BSTreeNode
    10. {
    11. 	BSTreeNode* _left;
    12. 	BSTreeNode* _right;
    13.  
    14. 	 K _key;      //一般不允许修改key，防止树型结构变化
    15. 	 V _value;
    16. 	BSTreeNode(const K& key,const V& value)
    17. 		:_left(nullptr)
    18. 		, _right(nullptr)
    19. 		, _key(key)
    20. 		,_value(value)
    21. 	{}
    22. };
    23.  
    24. template<class K, class V>
    25.  
    26. class BSTree
    27. {
    28. 	typedef BSTreeNode Node;
    29. public:
    30. 	//C++11支持default
    31. 	BSTree() = default;  //拷贝构造函数也是构造函数，只要写构造函数就不会生成默认构造，这里强制生成构造函数
    32.  
    33. 	Node* CopyTree(Node* root)
    34. 	{
    35. 		if (root == nullptr)
    36. 			return nullptr;
    37. 		Node* copyNode = new Node(root->_key,root->_value);
    38. 		copyNode->_left = CopyTree(root->_left);
    39. 		copyNode->_right = CopyTree(root->_right);
    40. 		return copyNode;
    41. 	}
    42. 	BSTree(const BSTree& t)  //实现深拷贝
    43. 	{
    44. 		_root = CopyTree(t._root);
    45. 	}
    46. 	//赋值重载 例：t2=t1;
    47. 	//现代写法
    48. 	BSTree& operator=(BSTree t)
    49. 	{
    50. 		swap(_root, t._root);
    51. 		return *this;
    52. 	}
    53. 	void DestroyTree(Node* root)
    54. 	{
    55. 		if (root == nullptr)
    56. 			return;
    57. 		DestroyTree(root->_left);
    58. 		DestroyTree(root->_right);
    59. 		delete root;
    60. 	}
    61. 	~BSTree()  //因为析构函数没有参数，要写成递归就得借用成员函数，嵌套一层
    62. 	{
    63. 		DestroyTree(_root);
    64. 		_root = nullptr;
    65. 	}
    66. 	//非递归insert
    67. 	bool Insert(const K& key,const V& value)   //虽然传了key和value，但只用key比较
    68. 	{
    69. 		if (_root == nullptr)
    70. 		{
    71. 			_root = new Node(key,value);
    72. 			return true;
    73. 		}
    74. 		Node* parent = nullptr;
    75. 		Node* cur = _root;
    76. 		while (cur)
    77. 		{
    78. 			//不允许冗余
    79. 			if (cur->_key < key)
    80. 			{
    81. 				parent = cur;
    82. 				cur = cur->_right;
    83. 			}
    84. 			else if (cur->_key > key)
    85. 			{
    86. 				parent = cur;
    87. 				cur = cur->_left;
    88. 			}
    89. 			else
    90. 			{
    91. 				return false;
    92. 			}
    93. 			/*//允许冗余
    94. 			if (cur->_key < key)
    95. 			{
    96. 				parent = cur;
    97. 				cur = cur->_right;
    98. 			}
    99. 			else
    100. 			{
    101. 				parent = cur;
    102. 				cur = cur->_left;
    103. 			}*/
    104. 		}
    105. 		cur = new Node(key,value);
    106. 		if (parent->_key < key)
    107. 		{
    108. 			parent->_right = cur;
    109. 		}
    110. 		else
    111. 		{
    112. 			parent->_left = cur;
    113. 		}
    114. 		return true;
    115. 	}
    116. 	//非递归find
    117. 	Node* Find(const K& key)
    118. 	{
    119. 		Node* cur = _root;
    120. 		while (cur)
    121. 		{
    122. 			if (cur->_key < key)
    123. 			{
    124. 				cur = cur->_right;
    125. 			}
    126. 			else if (cur->_key > key)
    127. 			{
    128. 				cur = cur->_left;
    129. 			}
    130. 			else
    131. 			{
    132. 				return cur;
    133. 			}
    134. 		}
    135. 		return nullptr;
    136. 	}
    137. 	//非递归erase
    138. 	//删除情况很多，需要分情况讨论
    139. 	//1.当删除的是父结点时，采用替换法：
    140. 	//找父结点的左子树的（所有值的）最大值结点或右子树的（所有值的）最小值结点替换被删除的父结点
    141. 	//2.当删除的是叶结点，直接删除，再链接
    142. 	bool Erase(const K& key)
    143. 	{
    144. 		Node* parent = nullptr;
    145. 		Node* cur = _root;
    146. 		while (cur)
    147. 		{
    148. 			if (cur->_key < key)
    149. 			{
    150. 				parent = cur;
    151. 				cur = cur->_right;
    152. 			}
    153. 			else if (cur->_key > key)
    154. 			{
    155. 				parent = cur;
    156. 				cur = cur->_left;
    157. 			}
    158. 			else
    159. 			{
    160. 				//一个孩子--左为空or右为空
    161.  
    162. 				if (cur->_left == nullptr)
    163. 				{
    164. 					//if(parent==nullptr)
    165. 					if (cur == _root)
    166. 					{
    167. 						_root = cur->_right;
    168. 					}
    169. 					else
    170. 					{
    171. 						if (cur == parent->_left)
    172. 						{
    173. 							parent->_left = cur->_right;
    174. 						}
    175. 						else
    176. 						{
    177. 							parent->_right = cur->_right;
    178. 						}
    179. 					}
    180. 					delete cur;
    181. 				}
    182. 				else if (cur->_right == nullptr)
    183. 				{
    184. 					//if(parent==nullptr)
    185. 					if (cur == _root)
    186. 					{
    187. 						_root = cur->_left;
    188. 					}
    189. 					else
    190. 					{
    191. 						if (cur == parent->_left)
    192. 						{
    193. 							parent->_left = cur->_left;
    194. 						}
    195. 						else
    196. 						{
    197. 							parent->_right = cur->_left;
    198. 						}
    199. 					}
    200. 					delete cur;
    201.  
    202. 				}
    203. 				else  //两个孩子都不为空 //删除有两个孩子的结点：替换法
    204. 				{
    205. 					//1.使用右子树的最小值结点替代
    206. 					Node* minParent = cur;
    207. 					Node* minRight = cur->_right;
    208. 					while (minRight->_left)
    209. 					{
    210. 						minParent = minRight;
    211. 						minRight = minRight->_left;
    212. 					}
    213. 					swap(minRight->_key, cur->_key); //或cur->_key = minRight->_key;
    214. 					if (minParent->_left == minRight)
    215. 					{
    216. 						minParent->_left = minRight->_right;
    217. 					}
    218. 					else
    219. 					{
    220. 						minParent->_right = minRight->_right;
    221. 					}
    222. 					delete minRight;
    223.  
    224. 					2.使用左子树的最大值结点替代
    225. 					//Node* maxParent = cur;
    226. 					//Node* maxLeft = cur->_left;
    227. 					//while (maxLeft->_right)
    228. 					//{
    229. 					//	maxParent = maxLeft;
    230. 					//	maxLeft = maxLeft->_right;
    231. 					//}
    232. 					//swap(maxLeft->_key, cur->_key); //或cur->_key = maxLeft->_key;
    233. 					//if (maxParent->_right == maxLeft)
    234. 					//{
    235. 					//	maxParent->_right = maxLeft->_left;
    236. 					//}
    237. 					//else
    238. 					//{
    239. 					//	maxParent->_left = maxLeft->_left;
    240. 					//}
    241. 					//delete maxLeft;
    242. 				}
    243. 				return true;
    244. 			}
    245.  
    246. 		}
    247. 		return false;
    248. 	}
    249. 	/
    250. 	//递归版
    251. 	//无法直接使用私有成员进行递归，因此嵌套一层成员函数，实现递归
    252. 	//递归find
    253. 	Node* FindR(const K& key)
    254. 	{
    255. 		return _FindR(_root, key);
    256. 	}
    257. 	//递归insert
    258. 	bool InsertR(const K& key,const V& value)
    259. 	{
    260. 		return _InsertR(_root, key,value);
    261. 	}
    262. 	//递归erase
    263. 	bool EraseR(const K& key)
    264. 	{
    265. 		return _EraseR(_root, key);
    266. 	}
    267. private:
    268. 	//递归insert
    269. 	bool _InsertR(Node*& root, const K& key,const V& value)
    270. 	{
    271. 		//Node*& root这个处理，使得当root为空指针时，但root同时也是父结点的left或right的别名，使得结点得以链接
    272. 		if (root == nullptr)
    273. 		{
    274. 			root = new Node(key,value);
    275. 			return true;
    276. 		}
    277. 		if (root->_key < key)
    278. 			return _InsertR(root->_right, key,value);
    279. 		else if (root->_key > key)
    280. 			return _InsertR(root->_left, key,value);
    281. 		else
    282. 			return false;
    283. 	}
    284. 	Node* _FindR(Node* root, const K& key)  //不允许修改key,但可以修改value，因此可以使用Node*返回
    285. 	{
    286. 		if (root == nullptr)
    287. 			return nullptr;
    288. 		if (root->_key < key)
    289. 		{
    290. 			return _FindR(root->_right, key);
    291. 		}
    292. 		else if (root->_key > key)
    293. 		{
    294. 			return _FindR(root->_left, key);
    295. 		}
    296. 		else
    297. 		{
    298. 			return root;
    299. 		}
    300. 	}
    301. 	//递归erase
    302. 	bool _EraseR(Node*& root, const K& key)
    303. 	{
    304. 		if (root == nullptr)
    305. 			return false;
    306. 		if (root->_key < key)
    307. 		{
    308. 			return _EraseR(root->_right, key);
    309. 		}
    310. 		else if (root->_key > key)
    311. 		{
    312. 			return _EraseR(root->_left, key);
    313. 		}
    314. 		else
    315. 		{
    316. 			Node* del = root; //先保存一下
    317. 			if (root->_left == nullptr)
    318. 			{
    319. 				root = root->_right;
    320. 			}
    321. 			else if (root->_right == nullptr)
    322. 			{
    323. 				root = root->_left;
    324. 			}
    325. 			else
    326. 			{
    327. 				//1.使用右子树的最小值结点替代
    328. 				Node* minRight = root->_right;
    329. 				while (minRight->_left)
    330. 				{
    331. 					minRight = minRight->_left;
    332. 				}
    333. 				swap(root->_key, minRight->_key);
    334. 				return _EraseR(root->_right, key);
    335.  
    336. 				2.使用左子树的最大值结点替代
    337. 				//Node* maxLeft = root->_left;
    338. 				//while (maxLeft->_right)
    339. 				//{
    340. 				//	maxLeft = maxLeft->_right;
    341. 				//}
    342. 				//swap(root->_key, maxLeft->_key);
    343. 				//return _EraseR(root->_left, key);
    344. 			}
    345. 			delete del;
    346. 			return true;
    347. 		}
    348. 	}
    349.  
    350. public:
    351. 	//递归版遍历
    352. 	void InOrder()          //1.中序遍历
    353. 	{
    354. 		_InOrder(_root);
    355. 		cout << endl;
    356. 	}
    357. 	void PrevOrder()        //2.前序遍历
    358. 	{
    359. 		_PrevOrder(_root);
    360. 		cout << endl;
    361. 	}
    362. 	void PostOrder()       //3.后序遍历
    363. 	{
    364. 		_PostOrder(_root);
    365. 		cout << endl;
    366. 	}
    367. private:
    368. 	//在C语言中，root可以被直接获取，
    369. 	//在C++中，因为_root 是私有，被封装起来了所以可有以下两种方式获得
    370. 	//1.可以写一个成员函数GetRoot()获取
    371. 	//2.也可以使用遍历，不被继承就设为私有成员函数
    372.  
    373. 	void _InOrder(Node* root)     //1.中序遍历
    374. 	{
    375. 		if (root == nullptr)
    376. 			return;
    377. 		_InOrder(root->_left);
    378. 		cout << root->_key << " 出现次数:"<_value<
    379. 		_InOrder(root->_right);
    380. 	}
    381. 	void _PrevOrder(Node* root)   //2.前序遍历
    382. 	{
    383. 		if (root == nullptr)
    384. 			return;
    385. 		//cout << root->_key << " ";
    386. 		cout << root->_key << " 出现次数:" << root->_value << endl;
    387.  
    388. 		_PrevOrder(root->_left);
    389. 		_PrevOrder(root->_right);
    390. 	}
    391. 	void _PostOrder(Node* root)   //3.后序遍历
    392. 	{
    393. 		if (root == nullptr)
    394. 			return;
    395. 		_PostOrder(root->_left);
    396. 		_PostOrder(root->_right);
    397. 		//cout << root->_key << " ";
    398. 		cout << root->_key << " 出现次数:" << root->_value << endl;
    399.  
    400. 	}
    401. private:
    402. 	Node* _root = nullptr;  //调用自定义类型Node*
    403. };

    （2）test.cpp:

    1. #include"BSTreeKeyValue.h"
    2.  
    3. void TestBSTreeKV1()
    4. {
    5. 	BSTree ECdict;  //英文找中文
    6. 	//使用递归InsertR
    7. 	/*ECdict.InsertR("hello", "你好");
    8. 	ECdict.InsertR("world", "世界");*/
    9. 	//使用非递归Insert
    10. 	ECdict.Insert("hello", "你好");
    11. 	ECdict.Insert("world", "世界");
    12.  
    13. 	string str;
    14. 	cout << "请输入要查询的英文单词：" << endl;
    15. 	while (cin >> str)  //原理同while(scanf()!=EOF)   //operator>>a
    16. 	{
    17. 		使用递归InsertR
    18. 		//BSTreeNode*ret= ECdict.FindR(str);  //或使用auto
    19. 		auto ret= ECdict.FindR(str);
    20. 		
    21.  
    22. 		//使用非递归Insert
    23. 		BSTreeNode* ret = ECdict.Find(str);  //或使用auto
    24. 		//auto ret= ECdict.Find(str);
    25.  
    26.  
    27. 		if (ret != nullptr)
    28. 		{
    29. 			cout << "对应的中文：" << ret->_value << endl;
    30. 			cout << "请输入要查询的英文单词：" << endl;
    31. 		}
    32. 		else
    33. 		{
    34. 			cout << "无此单词，请重新输入！" << endl;
    35. 			cout << "请输入要查询的英文单词：" << endl;
    36. 		}
    37. 	}
    38. }
    39. void TestBSTreeKV2()
    40. {
    41. 	1.使用非递归的insert、find
    42. 	 统计水果出现的次数
    43. 	//string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
    44.  //  "苹果", "香蕉", "苹果", "香蕉" };
    45. 	//BSTree countTree;
    46. 	//for (const auto& str : arr)
    47. 	//{
    48. 	//	// 先查找水果在不在搜索树中
    49. 	//	// 1、不在，说明水果第一次出现，则插入<水果, 1>
    50. 	//	// 2、在，则查找到的节点中水果对应的次数++
    51. 	//	//BSTreeNode* ret = countTree.Find(str);
    52. 	//	auto ret = countTree.Find(str);
    53. 	//	if (ret == NULL)
    54. 	//	{
    55. 	//		countTree.Insert(str, 1);
    56. 	//	}
    57. 	//	else
    58. 	//	{
    59. 	//		ret->_value++;
    60. 	//	}
    61. 	//}
    62. 	//countTree.InOrder();
    63. 	///*countTree.PrevOrder();
    64. 	//countTree.PostOrder();*/
    65.  
    66. 	//2.使用递归的insert、find
    67. 	// 统计水果出现的次数
    68. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
    69.    "苹果", "香蕉", "苹果", "香蕉" };
    70. 	BSTreeint> countTree;
    71. 	for (const auto& str : arr)
    72. 	{
    73. 		// 先查找水果在不在搜索树中
    74. 		// 1、不在，说明水果第一次出现，则插入<水果, 1>
    75. 		// 2、在，则查找到的节点中水果对应的次数++
    76. 		//BSTreeNode* ret = countTree.FindR(str);
    77. 		auto ret = countTree.FindR(str);
    78. 		if (ret == NULL)
    79. 		{
    80. 			countTree.InsertR(str, 1);
    81. 		}
    82. 		else
    83. 		{
    84. 			ret->_value++;
    85. 		}
    86. 	}
    87. 	countTree.InOrder();
    88. 	/*countTree.PrevOrder();
    89. 	countTree.PostOrder();*/
    90. }
    91. int main()
    92. {
    93. 	//TestBSTreeKV1();
    94. 	TestBSTreeKV2();
    95. 	return 0;
    96. }

    3.2.5 K、V模型应用举例：

    （1）

    （2）

     

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

     

  • 相关阅读:
    FreeRTOS学习笔记（二）
    豪赌？远见？浙江东方的量子冒险
    c++ SQLite 特别好用的库使用实例-更新（3）
    HTTP 的三次握手
    【Linux】 OpenSSH_7.4p1 升级到 OpenSSH_9.3p1（亲测无问题，建议收藏）
    视频产品介绍：AS-VCVR-N多协议视频接入网关
    Python Number degrees()实例讲解
    JSTL使用
    MySQL5.7版本与8.0版本在Ubuntu（WSL环境）系统安装
    基于ssm大学生社团管理系统
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126264869