• 二叉搜索树

    目录

    一、基本函数实现

    （一）结点定义

    （二）插入结点

    1. 非递归插入

    2. 递归插入

    （三）查找

    1. 非递归

    2. 递归

    （四）删除

    1. 删除情况分析

    2. 非递归

    3. 递归

    （五）中序遍历

    （六）拷贝树和销毁

    （七）构造、拷贝构造、析构和赋值重载

    二、完整代码

    1. BinarySearchTree.h

    2. 测试1

    3. 测试2

    4. 测试3

    5. 测试4 

    三、二叉搜索树的应用

    （一） K模型

    （二）KV模型

    1. 结点定义

    2. 完整代码

    一、基本函数实现

    （一）结点定义

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7. 	BSTreeNode(const K& key)
    8. 		:_left(nullptr)
    9. 		, _right(nullptr)
    10. 		, _key(key)
    11. 	{}
    12. };

    （二）插入结点

    1. 非递归插入

    1. bool Insert(const K& key)//插入
    2. {
    3. 	if (_root == nullptr)
    4. 	{
    5. 		_root = new Node(key);
    6. 		return true;
    7. 	}
    8.  
    9. 	Node* cur = _root;
    10. 	Node* parent = nullptr;//cur的父亲结点
    11. 	while (cur)
    12. 	{
    13. 		parent = cur;
    14.  
    15. 		if (key > cur->_key)//key的值比cur的值大，就去cur的右边
    16. 		{
    17. 			cur = cur->_right;
    18. 		}
    19. 		else if (key < cur->_key)//key的值比cur的值小，就去cur的左边
    20. 		{
    21. 			cur = cur->_left;
    22. 		}
    23. 		else
    24. 		{
    25. 			return false;
    26. 		}
    27. 	}
    28.  
    29. 	cur = new Node(key);
    30. 	//连接
    31. 	if (key > parent->_key)
    32. 	{
    33. 		parent->_right = cur;
    34. 	}
    35. 	else
    36. 	{
    37. 		parent->_left = cur;
    38. 	}
    39. 	return true;
    40. }

    2. 递归插入

    1. bool InsertR(const K& key)//递归插入
    2. {
    3. 	return _InsertR(this->_root, key);通过_InsertR函数拿到私有成员_root，然后进行递归
    4. }
    1. bool _InsertR(Node*& root, const K& key)
    2. {
    3. 	if (root == nullptr)
    4. 	{
    5. 		root = new Node(key);
    6. 		return true;
    7. 	}
    8.  
    9. 	if (key > root->_key)
    10. 	{
    11. 		return _InsertR(root->_right, key);//递归到右边
    12. 	}
    13. 	else if (key < root->_key)
    14. 	{
    15. 		return _InsertR(root->_left, key);//递归到左边
    16. 	}
    17. 	else//存在相等的值
    18. 	{
    19. 		return false;
    20. 	}
    21. }

    （三）查找

    1. 非递归

    1. bool Find(const K& key)//查找
    2. {
    3. 	Node* cur = _root;
    4. 	while (cur)
    5. 	{
    6. 		if (key > cur->_key)
    7. 		{
    8. 			cur = cur->_right;
    9. 		}
    10. 		else if (key < cur->_key)
    11. 		{
    12. 			cur = cur->_left;
    13. 		}
    14. 		else
    15. 		{
    16. 			return true;
    17. 		}
    18. 	}
    19. 	return false;
    20. }

    2. 递归

    1. bool FindR(const K& key)//递归查找
    2. {
    3. 	return _FindR(this->_root, key);
    4. }
    1. bool _FindR(Node* root, const K& key)
    2. {
    3. 	if (root == nullptr)
    4. 	{
    5. 		return false;
    6. 	}
    7.  
    8. 	if (key > root->_key)
    9. 	{
    10. 		return _FindR(root->_right, key);//递归到右边
    11. 	}
    12. 	else if (key < root->_key)
    13. 	{
    14. 		return _FindR(root->_left, key);//递归到左边
    15. 	}
    16. 	else//存在相等的值
    17. 	{
    18. 		return true;
    19. 	}
    20. }

    （四）删除

    1. 删除情况分析

     

    2. 非递归

    1. bool Erase(const K& key)//删除结点
    2. {
    3. 	Node* cur = _root;
    4. 	Node* parent = nullptr;//parent是删除结点cur的父结点
    5. 	while (cur)//先找到key值所在的结点
    6. 	{
    7. 		if (key > cur->_key)
    8. 		{
    9. 			parent = cur;
    10. 			cur = cur->_right;
    11. 		}
    12. 		else if (key < cur->_key)
    13. 		{
    14. 			parent = cur;
    15. 			cur = cur->_left;
    16. 		}
    17. 		else//找到了
    18. 		{
    19. 			//准备删除
    20. 			if (cur->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    21. 			{
    22. 				if (cur == _root)//删除的是根结点
    23. 				{
    24. 					_root = cur->_right;
    25. 				}
    26. 				else//删除的不是根结点
    27. 				{
    28. 					if (cur == parent->_left)//cur是父结点的左结点
    29. 					{
    30. 						parent->_left = cur->_right;
    31. 					}
    32. 					else//cur是父结点的右结点
    33. 					{
    34. 						parent->_right = cur->_right;
    35. 					}
    36. 				}
    37. 				delete cur;
    38. 				return true;
    39. 			}
    40. 			else if (cur->_right == nullptr)//删除的结点，只存在左子树)
    41. 			{
    42. 				if (cur == _root)//删除的是根结点
    43. 				{
    44. 					_root = cur->_left;
    45. 				}
    46. 				else
    47. 				{
    48. 					if (cur == parent->_left)//cur是父结点的左结点
    49. 					{
    50. 						parent->_left = cur->_left;
    51. 					}
    52. 					else//cur是父结点的右结点
    53. 					{
    54. 						parent->_right = cur->_left;
    55. 					}
    56. 				}
    57. 				delete cur;
    58. 				return true;
    59. 			}
    60. 			else//左右子树都不为空
    61. 			{
    62. 				//找右子树的最小结点
    63. 				Node* Minparent = cur;//右子树的最小结点的父结点
    64. 				Node* MinNode = cur->_right;//找cur右子树的最小结点
    65. 				while (MinNode->_left)
    66. 				{
    67. 					Minparent = MinNode;
    68. 					MinNode = MinNode->_left;
    69. 				}
    70. 				swap(MinNode->_key, cur->_key);//交换最小结点和删除结点的值
    71.  
    72. 				if (MinNode == Minparent->_left)//
    73. 				{
    74. 					Minparent->_left = MinNode->_right;
    75. 				}
    76. 				else//说明cur右子树的最小结点就是cur右子树的根结点
    77. 				{
    78. 					Minparent->_right = MinNode->_right;
    79. 				}
    80. 				delete MinNode;
    81. 				return true;
    82. 			}
    83. 		}
    84. 	}
    85. 	return false; //没有找到待删除结点，删除失败
    86. }

    3. 递归

    1. bool EraseR(const K& key)//递归删除
    2. {
    3. 	return _EraseR(this->_root, key);
    4. }
    1. bool _EraseR(Node*& root, const K& key)
    2. {
    3. 	if (_root == nullptr)
    4. 	{
    5. 		return false;
    6. 	}
    7.  
    8. 	if (key > root->_key)
    9. 	{
    10. 		return _EraseR(root->_right, key);//递归到右边
    11. 	}
    12. 	else if (key < root->_key)
    13. 	{
    14. 		return _EraseR(root->_left, key);
    15. 	}
    16. 	else //找到了等于key的结点
    17. 	{
    18. 		if (root->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    19. 		{
    20. 			Node* del = root;//先保存删除结点
    21. 			root = root->_right;//更新root
    22.  
    23. 			delete del;//释放结点
    24. 			return true;
    25. 		}
    26. 		else if (root->_right == nullptr)
    27. 		{
    28. 			Node* del = root;//先保存删除结点
    29. 			root = root->_left;//更新root
    30.  
    31. 			delete del;//释放结点
    32. 			return true;
    33. 		}
    34. 		else//左右子树都存在
    35. 		{
    36. 			//找删除结点右子树的最小结点
    37. 			Node* MinNode = root->_right;//开始指向右子树的根结点
    38.  
    39. 			while (MinNode->_left)
    40. 			{
    41. 				MinNode = MinNode->_left;
    42. 			}
    43.  
    44. 			swap(root->_key, MinNode->_key);//删除结点的值的值交换到了右子树上
    45.  
    46. 			// 转换成在子树去递归删除
    47. 			return _EraseR(root->_right, key);
    48. 		}
    49. 	}
    50. }

    （五）中序遍历

    1. void InOrder()//中序遍历
    2. {
    3. 	_InOrder(this->_root);//通过_InOrder函数拿到私有成员_root，然后进行递归
    4. }
    1. bool _InsertR(Node*& root, const K& key)//递归插入
    2. {
    3. 	if (root == nullptr)
    4. 	{
    5. 		root = new Node(key);
    6. 		return true;
    7. 	}
    8.  
    9. 	if (key > root->_key)
    10. 	{
    11. 		return _InsertR(root->_right, key);//递归到右边
    12. 	}
    13. 	else if (key < root->_key)
    14. 	{
    15. 		return _InsertR(root->_left, key);//递归到左边
    16. 	}
    17. 	else//存在相等的值
    18. 	{
    19. 		return false;
    20. 	}
    21. }

    （六）拷贝树和销毁

    1. Node* Copy(Node* root)//拷贝
    2. {
    3. 	if (root == nullptr)
    4. 	{
    5. 		return nullptr;
    6. 	}
    7.  
    8. 	Node* newRoot = new Node(root->_key);
    9. 	newRoot->_left = Copy(root->_left);
    10. 	newRoot->_right = Copy(root->_right);
    11.  
    12. 	return newRoot;
    13. }
    14. void _Destroy(Node*& root)//递归释放树中结点
    15. //需要修改原始树的根节点指针，因此参数是指针的引用
    16. {
    17. 	if (root == nullptr)
    18. 		return;
    19.  
    20. 	_Destroy(root->_left);//先释放左结点
    21. 	_Destroy(root->_right);//再释放右结点
    22. 	delete root;
    23. 	root = nullptr;
    24. }

    （七）构造、拷贝构造、析构和赋值重载

    1. BSTree() :_root(nullptr)//在构造函数中初始化私有成员_root 为 nullptr
    2. {}
    3. ~BSTree()//析构函数
    4. {
    5. 	Destory();
    6. }
    7. BSTree(const BSTree& t)//拷贝构造函数
    8. {
    9. 	this->_root = Copy(t._root);
    10. }
    11.  
    12. BSTree& operator=(BSTree t)//赋值重载
    13. {
    14. 	swap(this->_root, t._root);
    15. 	return *this;
    16. }

    二、完整代码

    1. BinarySearchTree.h

    1. #pragma once
    2. #include
    3. using namespace std;
    4. template<class K>
    5. struct BSTreeNode
    6. {
    7. 	BSTreeNode* _left;
    8. 	BSTreeNode* _right;
    9. 	K _key;
    10. 	BSTreeNode(const K& key)
    11. 		:_left(nullptr)
    12. 		, _right(nullptr)
    13. 		, _key(key)
    14. 	{}
    15. };
    16.  
    17. template<class K>
    18. class BSTree
    19. {
    20. 	typedef BSTreeNode Node;
    21. public:
    22. 	BSTree() :_root(nullptr)//在构造函数中初始化私有成员_root 为 nullptr
    23. 	{}
    24. 	~BSTree()//析构函数
    25. 	{
    26. 		Destory();
    27. 	}
    28. 	BSTree(const BSTree& t)//拷贝构造函数
    29. 	{
    30. 		this->_root = Copy(t._root);
    31. 	}
    32.  
    33. 	BSTree& operator=(BSTree t)//赋值重载
    34. 	{
    35. 		swap(this->_root, t._root);
    36. 		return *this;
    37. 	}
    38.  
    39. 	void SetRoot(BSTreeNode* root)//设置根结点
    40. 	{
    41. 		_root = root;
    42. 	}
    43. 	void Destory()//释放结点
    44. 	{
    45. 		_Destroy(this->_root);
    46. 	}
    47.  
    48. 	bool Insert(const K& key)//插入
    49. 	{
    50. 		if (_root == nullptr)
    51. 		{
    52. 			_root = new Node(key);
    53. 			return true;
    54. 		}
    55.  
    56. 		Node* cur = _root;
    57. 		Node* parent = nullptr;//cur的父亲结点
    58. 		while (cur)
    59. 		{
    60. 			parent = cur;
    61.  
    62. 			if (key > cur->_key)//key的值比cur的值大，就去cur的右边
    63. 			{
    64. 				cur = cur->_right;
    65. 			}
    66. 			else if (key < cur->_key)//key的值比cur的值小，就去cur的左边
    67. 			{
    68. 				cur = cur->_left;
    69. 			}
    70. 			else
    71. 			{
    72. 				return false;
    73. 			}
    74. 		}
    75.  
    76. 		cur = new Node(key);
    77. 		//连接
    78. 		if (key > parent->_key)
    79. 		{
    80. 			parent->_right = cur;
    81. 		}
    82. 		else
    83. 		{
    84. 			parent->_left = cur;
    85. 		}
    86. 		return true;
    87. 	}
    88. 	bool Find(const K& key)//查找
    89. 	{
    90. 		Node* cur = _root;
    91. 		while (cur)
    92. 		{
    93. 			if (key >cur->_key)
    94. 			{
    95. 				cur = cur->_right;
    96. 			}
    97. 			else if (key < cur->_key)
    98. 			{
    99. 				cur = cur->_left;
    100. 			}
    101. 			else
    102. 			{
    103. 				return true;
    104. 			}
    105. 		}
    106. 		return false;
    107. 	}
    108. 	bool Erase(const K& key)//删除结点
    109. 	{
    110. 		Node* cur = _root;
    111. 		Node* parent = nullptr;//parent是删除结点cur的父结点
    112. 		while (cur)//先找到key值所在的结点
    113. 		{
    114. 			if (key > cur->_key)
    115. 			{
    116. 				parent = cur;
    117. 				cur = cur->_right;
    118. 			}
    119. 			else if (key < cur->_key)
    120. 			{
    121. 				parent = cur;
    122. 				cur = cur->_left;
    123. 			}
    124. 			else//找到了
    125. 			{
    126. 				//准备删除
    127. 				if (cur->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    128. 				{
    129. 					if (cur == _root)//删除的是根结点
    130. 					{
    131. 						_root = cur->_right;
    132. 					}
    133. 					else//删除的不是根结点
    134. 					{
    135. 						if (cur == parent->_left)//cur是父结点的左结点
    136. 						{
    137. 							parent->_left = cur->_right;
    138. 						}
    139. 						else//cur是父结点的右结点
    140. 						{
    141. 							parent->_right = cur->_right;
    142. 						}
    143. 					}
    144. 					delete cur;
    145. 					return true;
    146. 				}
    147. 				else if (cur->_right == nullptr)//删除的结点，只存在左子树)
    148. 				{
    149. 					if (cur == _root)//删除的是根结点
    150. 					{
    151. 						_root = cur->_left;
    152. 					}
    153. 					else
    154. 					{
    155. 						if (cur == parent->_left)//cur是父结点的左结点
    156. 						{
    157. 							parent->_left = cur->_left;
    158. 						}
    159. 						else//cur是父结点的右结点
    160. 						{
    161. 							parent->_right = cur->_left;
    162. 						}
    163. 					}
    164. 					delete cur;
    165. 					return true;
    166. 				}
    167. 				else//左右子树都不为空
    168. 				{
    169. 					//找右子树的最小结点
    170. 					Node* Minparent = cur;//右子树的最小结点的父结点
    171. 					Node* MinNode = cur->_right;//找cur右子树的最小结点
    172. 					while (MinNode->_left)
    173. 					{
    174. 						Minparent = MinNode;
    175. 						MinNode = MinNode->_left;
    176. 					}
    177. 					swap(MinNode->_key, cur->_key);//交换最小结点和删除结点的值
    178. 					
    179. 					if (MinNode == Minparent->_left)//
    180. 					{
    181. 						Minparent->_left = MinNode->_right;
    182. 					}
    183. 					else//说明cur右子树的最小结点就是cur右子树的根结点
    184. 					{
    185. 						Minparent->_right = MinNode->_right;
    186. 					}
    187. 					delete MinNode;
    188. 					return true;
    189. 				}
    190. 			}
    191. 		}
    192. 		return false; //没有找到待删除结点，删除失败
    193. 	}
    194.  
    195. 	//递归
    196. 	bool InsertR(const K& key)//递归插入
    197. 	{
    198. 		return _InsertR(this->_root, key);
    199. 	}
    200. 	bool FindR(const K& key)//递归查找
    201. 	{
    202. 		return _FindR(this->_root, key);
    203. 	}
    204. 	bool EraseR(const K& key)//递归删除
    205. 	{
    206. 		return _EraseR(this->_root, key);
    207. 	}
    208. 	void InOrder()//中序遍历
    209. 	{
    210. 		_InOrder(this->_root);//通过_InOrder函数拿到私有成员_root，然后进行递归
    211. 	}
    212. private:
    213. 	Node* Copy(Node* root)//拷贝
    214. 	{
    215. 		if (root == nullptr)
    216. 		{
    217. 			return nullptr;
    218. 		}
    219.  
    220. 		Node* newRoot = new Node(root->_key);
    221. 		newRoot->_left = Copy(root->_left);
    222. 		newRoot->_right = Copy(root->_right);
    223.  
    224. 		return newRoot;
    225. 	}
    226. 	void _Destroy(Node*& root)//递归释放树中结点
    227. 								//需要修改原始树的根节点指针，因此参数是指针的引用
    228. 	{
    229. 		if (root == nullptr)
    230. 			return;
    231.  
    232. 		_Destroy(root->_left);//先释放左结点
    233. 		_Destroy(root->_right);//再释放右结点
    234. 		delete root;
    235. 		root = nullptr;
    236. 	}
    237. 	bool _InsertR(Node*& root, const K& key)//递归插入
    238. 	{
    239. 		if (root == nullptr)
    240. 		{
    241. 			root = new Node(key);
    242. 			return true;
    243. 		}
    244.  
    245. 		if (key > root->_key)
    246. 		{
    247. 			return _InsertR(root->_right, key);//递归到右边
    248. 		}
    249. 		else if (key < root->_key)
    250. 		{
    251. 			return _InsertR(root->_left, key);//递归到左边
    252. 		}
    253. 		else//存在相等的值
    254. 		{
    255. 			return false;
    256. 		}
    257. 	}
    258. 	bool _FindR(Node* root, const K& key)
    259. 	{
    260. 		if (root == nullptr)
    261. 		{
    262. 			return false;
    263. 		}
    264.  
    265. 		if (key > root->_key)
    266. 		{
    267. 			return _FindR(root->_right, key);//递归到右边
    268. 		}
    269. 		else if (key < root->_key)
    270. 		{
    271. 			return _FindR(root->_left, key);//递归到左边
    272. 		}
    273. 		else//存在相等的值
    274. 		{
    275. 			return true;
    276. 		}
    277. 	}
    278. 	bool _EraseR(Node*& root, const K& key)
    279. 	{
    280. 		if (_root == nullptr)
    281. 		{
    282. 			return false;
    283. 		}
    284.  
    285. 		if (key > root->_key)
    286. 		{
    287. 			return _EraseR(root->_right, key);//递归到右边
    288. 		}
    289. 		else if (key < root->_key)
    290. 		{
    291. 			return _EraseR(root->_left, key);
    292. 		}
    293. 		else //找到了等于key的结点
    294. 		{
    295. 			if (root->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    296. 			{
    297. 				Node* del = root;//先保存删除结点
    298. 				root = root->_right;//更新root
    299.  
    300. 				delete del;//释放结点
    301. 				return true;
    302. 			}
    303. 			else if (root->_right == nullptr)
    304. 			{
    305. 				Node* del = root;//先保存删除结点
    306. 				root = root->_left;//更新root
    307.  
    308. 				delete del;//释放结点
    309. 				return true;
    310. 			}
    311. 			else//左右子树都存在
    312. 			{
    313. 				//找删除结点右子树的最小结点
    314. 				Node* MinNode = root->_right;//开始指向右子树的根结点
    315.  
    316. 				while (MinNode->_left)
    317. 				{
    318. 					MinNode = MinNode->_left;
    319. 				}
    320.  
    321. 				swap(root->_key, MinNode->_key);//删除结点的值的值交换到了右子树上
    322.  
    323. 				// 转换成在子树去递归删除
    324. 				return _EraseR(root->_right, key);
    325. 			}
    326. 		}
    327. 	}
    328.  
    329. 	void _InOrder(Node* root)//中序遍历
    330. 	{
    331. 		if (root == nullptr)
    332. 		{
    333. 			return;
    334. 		}
    335. 		_InOrder(root->_left);
    336. 		cout << root->_key << " ";
    337. 		_InOrder(root->_right);
    338. 	}
    339. private:
    340. 	Node* _root;
    341. };

    2. 测试1

    1. #include"BinarySearchTree.h"
    2. int main()
    3. {
    4. 	int data[] = { 1, 5, 2, 9, 7, 3, 8, 17, 15, 4};
    5. 	//创建树
    6. 	BSTree<int> T;
    7. 	for (int i = 0; i < sizeof(data)/sizeof(data[0]); i++)
    8. 	{
    9. 		T.Insert(data[i]);
    10. 	}
    11.  
    12. 	T.InOrder();//中序遍历
    13.  
    14. 	cout << endl;
    15. 	if (T.Find(89) == true)
    16. 	{
    17. 		cout << "找到了" << endl;
    18. 	}
    19. 	else
    20. 	{
    21. 		cout << "没有找到" << endl;
    22. 	}
    23. 	return 0;
    24. }

    3. 测试2

    1. #include"BinarySearchTree.h"
    2. int main()
    3. {
    4. 	//手动链接结点，创建T2
    5. 	BSTree<int> T2;
    6. 	BSTreeNode<int>* Node1 = new BSTreeNode<int>(8);
    7. 	BSTreeNode<int>* Node2 = new BSTreeNode<int>(3);
    8. 	BSTreeNode<int>* Node3 = new BSTreeNode<int>(10);
    9. 	BSTreeNode<int>* Node4 = new BSTreeNode<int>(1);
    10. 	BSTreeNode<int>* Node5 = new BSTreeNode<int>(6);
    11. 	BSTreeNode<int>* Node6 = new BSTreeNode<int>(14);
    12. 	BSTreeNode<int>* Node7 = new BSTreeNode<int>(4);
    13. 	BSTreeNode<int>* Node8 = new BSTreeNode<int>(7);
    14. 	BSTreeNode<int>* Node9 = new BSTreeNode<int>(13);
    15. 	Node1->_left = Node2;
    16. 	Node1->_right = Node3;
    17. 	Node2->_left = Node4;
    18. 	Node2->_right = Node5;
    19. 	Node3->_right = Node6;
    20. 	Node5->_left = Node7;
    21. 	Node5->_right = Node8;
    22. 	Node6->_left = Node9;
    23. 	T2.SetRoot(Node1);
    24. 	cout << "删除10之前：";
    25. 	T2.InOrder();//中序遍历
    26.  
    27. 	T2.Erase(10);
    28. 	cout << endl;
    29. 	cout << "删除10之后：";
    30. 	T2.InOrder();
    31.  
    32. 	T2.Erase(3);
    33. 	cout << endl;
    34. 	cout << "删除3之后：" ;
    35. 	T2.InOrder();
    36.  
    37. 	return 0;
    38. }

    4. 测试3

    1. #include"BinarySearchTree.h"
    2. int main()
    3. {
    4. 	//手动链接结点，创建T2
    5. 	BSTree<int> T2;
    6. 	BSTreeNode<int>* Node1 = new BSTreeNode<int>(8);
    7. 	BSTreeNode<int>* Node2 = new BSTreeNode<int>(3);
    8. 	BSTreeNode<int>* Node3 = new BSTreeNode<int>(10);
    9. 	BSTreeNode<int>* Node4 = new BSTreeNode<int>(1);
    10. 	BSTreeNode<int>* Node5 = new BSTreeNode<int>(6);
    11. 	BSTreeNode<int>* Node6 = new BSTreeNode<int>(14);
    12. 	BSTreeNode<int>* Node7 = new BSTreeNode<int>(4);
    13. 	BSTreeNode<int>* Node8 = new BSTreeNode<int>(7);
    14. 	BSTreeNode<int>* Node9 = new BSTreeNode<int>(13);
    15. 	Node1->_left = Node2;
    16. 	Node1->_right = Node3;
    17. 	Node2->_left = Node4;
    18. 	Node2->_right = Node5;
    19. 	Node3->_right = Node6;
    20. 	Node5->_left = Node7;
    21. 	Node5->_right = Node8;
    22. 	Node6->_left = Node9;
    23. 	T2.SetRoot(Node1);
    24.  
    25. 	//递归
    26. 	//T2.InOrder();
    27. 	//T2.InsertR(9);
    28. 	//cout << endl;
    29. 	//cout << "插入9之后：";
    30. 	//T2.InOrder();
    31.  
    32.  
    33. 	//cout << "删除3之前：";
    34. 	//T2.InOrder();
    35. 	//T2.EraseR(3);
    36. 	//cout << endl;
    37. 	//cout << "删除3之后：";
    38. 	//T2.InOrder();
    39.  
    40.  
    41. 	//cout << "删除10之前：";
    42. 	//T2.InOrder();
    43. 	//T2.EraseR(10);
    44. 	//cout << endl;
    45. 	//cout << "删除10之后：";
    46. 	//T2.InOrder();
    47.  
    48. 	if (T2.FindR(4) == true)
    49. 	{
    50. 		cout << "找到了" << endl;
    51. 	}
    52. 	else
    53. 	{
    54. 		cout << "没有找到" << endl;
    55. 	}
    56. 	return 0;
    57. }
    58.

    5. 测试4 

    1. #include"BinarySearchTree.h"
    2. int main()
    3. {
    4. 	//手动链接结点，创建T
    5. 	BSTree<int> T;
    6. 	BSTreeNode<int>* Node1 = new BSTreeNode<int>(8);
    7. 	BSTreeNode<int>* Node2 = new BSTreeNode<int>(3);
    8. 	BSTreeNode<int>* Node3 = new BSTreeNode<int>(10);
    9. 	BSTreeNode<int>* Node4 = new BSTreeNode<int>(1);
    10. 	BSTreeNode<int>* Node5 = new BSTreeNode<int>(6);
    11. 	BSTreeNode<int>* Node6 = new BSTreeNode<int>(14);
    12. 	BSTreeNode<int>* Node7 = new BSTreeNode<int>(4);
    13. 	BSTreeNode<int>* Node8 = new BSTreeNode<int>(7);
    14. 	BSTreeNode<int>* Node9 = new BSTreeNode<int>(13);
    15. 	Node1->_left = Node2;
    16. 	Node1->_right = Node3;
    17. 	Node2->_left = Node4;
    18. 	Node2->_right = Node5;
    19. 	Node3->_right = Node6;
    20. 	Node5->_left = Node7;
    21. 	Node5->_right = Node8;
    22. 	Node6->_left = Node9;
    23. 	T.SetRoot(Node1);
    24.  
    25. 	BSTree<int> T2(T);//拷贝构造
    26. 	cout << "T2：" ;
    27. 	T2.InOrder();
    28. 	cout << endl;
    29.  
    30.  
    31. 	int data[] = { 1, 5, 2, 9, 7, 3, 8, 17, 15, 4};
    32. 	//创建树
    33. 	BSTree<int> T3;
    34. 	for (int i = 0; i < sizeof(data)/sizeof(data[0]); i++)
    35. 	{
    36. 		T3.Insert(data[i]);
    37. 	}
    38. 	cout << "T3：";
    39. 	T3.InOrder();
    40. 	cout << endl;
    41. 	cout << "T3被T2赋值以后：";
    42. 	T3 = T2;
    43. 	T3.InOrder();
    44. 	cout << endl;
    45.  
    46. 	cout << "析构以后T2：";
    47. 	T2.~BSTree();
    48.  
    49.  
    50. 	return 0;
    51. }

    三、二叉搜索树的应用

    （一） K模型

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

    （二）KV模型

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

    1. 结点定义

    1. template<class K, class V>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7. 	V _value;
    8. 	BSTreeNode(const K& key, const V& value)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 		,_value(value)
    13. 	{}
    14. };

    2. 完整代码

    1. #pragma once
    2. #include
    3. using namespace std;
    4. template<class K, class V>
    5. struct BSTreeNode
    6. {
    7. 	BSTreeNode* _left;
    8. 	BSTreeNode* _right;
    9. 	K _key;
    10. 	V _value;
    11. 	BSTreeNode(const K& key, const V& value)
    12. 		:_left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _key(key)
    15. 		,_value(value)
    16. 	{}
    17. };
    18.  
    19. template<class K, class V>
    20. class BSTree
    21. {
    22. 	typedef BSTreeNode Node;
    23. public:
    24. 	BSTree() :_root(nullptr)//在构造函数中初始化私有成员_root 为 nullptr
    25. 	{}
    26. 	~BSTree()//析构函数
    27. 	{
    28. 		Destory();
    29. 	}
    30. 	BSTree(const BSTree& t)//拷贝构造函数
    31. 	{
    32. 		this->_root = Copy(t._root);
    33. 	}
    34.  
    35. 	BSTree& operator=(BSTree t)//赋值重载
    36. 	{
    37. 		swap(this->_root, t._root);
    38. 		return *this;
    39. 	}
    40.  
    41. 	void SetRoot(BSTreeNode* root)//设置根结点
    42. 	{
    43. 		_root = root;
    44. 	}
    45. 	void Destory()//释放结点
    46. 	{
    47. 		_Destroy(this->_root);
    48. 	}
    49.  
    50. 	bool Insert(const K& key, const V& value)//插入
    51. 	{
    52. 		if (_root == nullptr)
    53. 		{
    54. 			_root = new Node(key, value);
    55. 			return true;
    56. 		}
    57.  
    58. 		Node* cur = _root;
    59. 		Node* parent = nullptr;//cur的父亲结点
    60. 		while (cur)
    61. 		{
    62. 			parent = cur;
    63.  
    64. 			if (key > cur->_key)//key的值比cur的值大，就去cur的右边
    65. 			{
    66. 				cur = cur->_right;
    67. 			}
    68. 			else if (key < cur->_key)//key的值比cur的值小，就去cur的左边
    69. 			{
    70. 				cur = cur->_left;
    71. 			}
    72. 			else
    73. 			{
    74. 				return false;
    75. 			}
    76. 		}
    77.  
    78. 		cur = new Node(key, value);
    79. 		//连接
    80. 		if (key > parent->_key)
    81. 		{
    82. 			parent->_right = cur;
    83. 		}
    84. 		else
    85. 		{
    86. 			parent->_left = cur;
    87. 		}
    88. 		return true;
    89. 	}
    90. 	Node* Find(const K& key)//查找
    91. 	{
    92. 		Node* cur = _root;
    93. 		while (cur)
    94. 		{
    95. 			if (key >cur->_key)
    96. 			{
    97. 				cur = cur->_right;
    98. 			}
    99. 			else if (key < cur->_key)
    100. 			{
    101. 				cur = cur->_left;
    102. 			}
    103. 			else
    104. 			{
    105. 				return cur;
    106. 			}
    107. 		}
    108. 		return nullptr;
    109. 	}
    110. 	bool Erase(const K& key)//删除结点
    111. 	{
    112. 		Node* cur = _root;
    113. 		Node* parent = nullptr;//parent是删除结点cur的父结点
    114. 		while (cur)//先找到key值所在的结点
    115. 		{
    116. 			if (key > cur->_key)
    117. 			{
    118. 				parent = cur;
    119. 				cur = cur->_right;
    120. 			}
    121. 			else if (key < cur->_key)
    122. 			{
    123. 				parent = cur;
    124. 				cur = cur->_left;
    125. 			}
    126. 			else//找到了
    127. 			{
    128. 				//准备删除
    129. 				if (cur->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    130. 				{
    131. 					if (cur == _root)//删除的是根结点
    132. 					{
    133. 						_root = cur->_right;
    134. 					}
    135. 					else//删除的不是根结点
    136. 					{
    137. 						if (cur == parent->_left)//cur是父结点的左结点
    138. 						{
    139. 							parent->_left = cur->_right;
    140. 						}
    141. 						else//cur是父结点的右结点
    142. 						{
    143. 							parent->_right = cur->_right;
    144. 						}
    145. 					}
    146. 					delete cur;
    147. 					return true;
    148. 				}
    149. 				else if (cur->_right == nullptr)//删除的结点，只存在左子树)
    150. 				{
    151. 					if (cur == _root)//删除的是根结点
    152. 					{
    153. 						_root = cur->_left;
    154. 					}
    155. 					else
    156. 					{
    157. 						if (cur == parent->_left)//cur是父结点的左结点
    158. 						{
    159. 							parent->_left = cur->_left;
    160. 						}
    161. 						else//cur是父结点的右结点
    162. 						{
    163. 							parent->_right = cur->_left;
    164. 						}
    165. 					}
    166. 					delete cur;
    167. 					return true;
    168. 				}
    169. 				else//左右子树都不为空
    170. 				{
    171. 					//找右子树的最小结点
    172. 					Node* Minparent = cur;//右子树的最小结点的父结点
    173. 					Node* MinNode = cur->_right;//找cur右子树的最小结点
    174. 					while (MinNode->_left)
    175. 					{
    176. 						Minparent = MinNode;
    177. 						MinNode = MinNode->_left;
    178. 					}
    179. 					swap(MinNode->_key, cur->_key);//交换最小结点和删除结点的值
    180. 					
    181. 					if (MinNode == Minparent->_left)//
    182. 					{
    183. 						Minparent->_left = MinNode->_right;
    184. 					}
    185. 					else//说明cur右子树的最小结点就是cur右子树的根结点
    186. 					{
    187. 						Minparent->_right = MinNode->_right;
    188. 					}
    189. 					delete MinNode;
    190. 					return true;
    191. 				}
    192. 			}
    193. 		}
    194. 		return false; //没有找到待删除结点，删除失败
    195. 	}
    196.  
    197. 	//递归
    198. 	bool InsertR(const K& key)//递归插入
    199. 	{
    200. 		return _InsertR(this->_root, key);
    201. 	}
    202. 	Node* FindR(const K& key)//递归查找
    203. 	{
    204. 		return _FindR(this->_root, key);
    205. 	}
    206. 	bool EraseR(const K& key)//递归删除
    207. 	{
    208. 		return _EraseR(this->_root, key);
    209. 	}
    210. 	void InOrder()//中序遍历
    211. 	{
    212. 		_InOrder(this->_root);//通过_InOrder函数拿到私有成员_root，然后进行递归
    213. 	}
    214. private:
    215. 	Node* Copy(Node* root)//拷贝
    216. 	{
    217. 		if (root == nullptr)
    218. 		{
    219. 			return nullptr;
    220. 		}
    221.  
    222. 		Node* newRoot = new Node(root->_key);
    223. 		newRoot->_left = Copy(root->_left);
    224. 		newRoot->_right = Copy(root->_right);
    225.  
    226. 		return newRoot;
    227. 	}
    228. 	void _Destroy(Node*& root)//递归释放树中结点
    229. 								//需要修改原始树的根节点指针，因此参数是指针的引用
    230. 	{
    231. 		if (root == nullptr)
    232. 			return;
    233.  
    234. 		_Destroy(root->_left);//先释放左结点
    235. 		_Destroy(root->_right);//再释放右结点
    236. 		delete root;
    237. 		root = nullptr;
    238. 	}
    239. 	bool _InsertR(Node*& root, const K& key)//递归插入
    240. 	{
    241. 		if (root == nullptr)
    242. 		{
    243. 			root = new Node(key);
    244. 			return true;
    245. 		}
    246.  
    247. 		if (key > root->_key)
    248. 		{
    249. 			return _InsertR(root->_right, key);//递归到右边
    250. 		}
    251. 		else if (key < root->_key)
    252. 		{
    253. 			return _InsertR(root->_left, key);//递归到左边
    254. 		}
    255. 		else//存在相等的值
    256. 		{
    257. 			return false;
    258. 		}
    259. 	}
    260. 	Node* _FindR(Node* root, const K& key)
    261. 	{
    262. 		if (root == nullptr)
    263. 		{
    264. 			return nullptr;
    265. 		}
    266.  
    267. 		if (key > root->_key)
    268. 		{
    269. 			return _FindR(root->_right, key);//递归到右边
    270. 		}
    271. 		else if (key < root->_key)
    272. 		{
    273. 			return _FindR(root->_left, key);//递归到左边
    274. 		}
    275. 		else//存在相等的值
    276. 		{
    277. 			return root;
    278. 		}
    279. 	}
    280. 	bool _EraseR(Node*& root, const K& key)
    281. 	{
    282. 		if (_root == nullptr)
    283. 		{
    284. 			return false;
    285. 		}
    286.  
    287. 		if (key > root->_key)
    288. 		{
    289. 			return _EraseR(root->_right, key);//递归到右边
    290. 		}
    291. 		else if (key < root->_key)
    292. 		{
    293. 			return _EraseR(root->_left, key);
    294. 		}
    295. 		else //找到了等于key的结点
    296. 		{
    297. 			if (root->_left == nullptr)//删除的结点，只存在右子树（或者左右子树都不存在）
    298. 			{
    299. 				Node* del = root;//先保存删除结点
    300. 				root = root->_right;//更新root
    301.  
    302. 				delete del;//释放结点
    303. 				return true;
    304. 			}
    305. 			else if (root->_right == nullptr)
    306. 			{
    307. 				Node* del = root;//先保存删除结点
    308. 				root = root->_left;//更新root
    309.  
    310. 				delete del;//释放结点
    311. 				return true;
    312. 			}
    313. 			else//左右子树都存在
    314. 			{
    315. 				//找删除结点右子树的最小结点
    316. 				Node* MinNode = root->_right;//开始指向右子树的根结点
    317.  
    318. 				while (MinNode->_left)
    319. 				{
    320. 					MinNode = MinNode->_left;
    321. 				}
    322.  
    323. 				swap(root->_key, MinNode->_key);//删除结点的值的值交换到了右子树上
    324.  
    325. 				// 转换成在子树去递归删除
    326. 				return _EraseR(root->_right, key);
    327. 			}
    328. 		}
    329. 	}
    330.  
    331. 	void _InOrder(Node* root)//中序遍历
    332. 	{
    333. 		if (root == nullptr)
    334. 		{
    335. 			return;
    336. 		}
    337. 		_InOrder(root->_left);
    338. 		cout << root->_key << " ";
    339. 		_InOrder(root->_right);
    340. 	}
    341. private:
    342. 	Node* _root;
    343. };
    1. #include"BinarySearchTree.h"
    2. #include
    3. int main()
    4. {
    5. 	BSTree dict;
    6. 	dict.Insert("sort", "排序");
    7. 	dict.Insert("left", "左边");
    8. 	dict.Insert("right", "右边");
    9. 	dict.Insert("insert", "插入");
    10. 	dict.Insert("key", "key值");
    11.  
    12. 	string str;
    13. 	while (cin >> str)
    14. 	{
    15. 		BSTreeNode* ret = dict.FindR(str);
    16. 		if (ret)
    17. 		{
    18. 			cout << ret->_value << endl;
    19. 		}
    20. 		else
    21. 		{
    22. 			cout << "不在字典中" << endl;
    23. 		}
    24. 	}
    25.  
    26. 	return 0;
    27. }

  • 相关阅读:
    PromQL 查询监控数据
    Weakmap详解
    图片或视频充当网页背景+过渡动画
    高端两轮电动车是否担得起“高端”头衔？
    windows下安装配置CGAL
    JavaWeb知识梳理(后端部分)
    MySQL百万数据深度分页优化思路分析
    叠片式过滤器原理概述
    图04---最小生成树与实现
    PHP 创建 MySQL 表
  • 原文地址：https://blog.csdn.net/m0_63783532/article/details/134024307