• 二叉搜索树的实现（迭代方式）

    二叉搜索树（Binary Search Tree，BST）是一种基于二叉树的数据结构，具有以下特点：

    1. 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
    2. 左子树和右子树也都是二叉搜索树。

    这个特性使得二叉搜索树能够高效地支持插入、删除和查找操作。

    插入操作：
    要在二叉搜索树中插入一个新节点，需要按照以下步骤进行：

    1. 如果树为空，则将新节点作为根节点。
    2. 如果树不为空，则从根节点开始比较新节点的值与当前节点的值。
    3. 如果新节点的值小于当前节点的值，继续在当前节点的左子树中插入新节点。
    4. 如果新节点的值大于当前节点的值，继续在当前节点的右子树中插入新节点。
    5. 重复步骤3和4，直到找到一个空位置插入新节点。

    删除操作：
    要在二叉搜索树中删除一个节点，需要按照以下步骤进行：

    1. 首先，找到要删除的节点。如果节点不存在，则删除操作失败。
    2. 如果要删除的节点没有子节点，直接删除即可。
    3. 如果要删除的节点只有一个子节点，将其子节点替代要删除的节点。
    4. 如果要删除的节点有两个子节点，需要找到其右子树中的最小节点（或左子树中的最大节点），将其值替换到要删除的节点上，然后删除这个最小（或最大）节点。

    针对第4点，左子树的最右节点和右子树的最左节点，只有这两个节点能起到承上启下的作用，比所有的左子树节点都大，比所有的右子树节点都小；去替换目标节点后，这颗二叉树才能保持为搜索二叉树。

    查找操作：
    要在二叉搜索树中查找一个特定的值，需要按照以下步骤进行：

    1. 从根节点开始，将要查找的值与当前节点的值进行比较。
    2. 如果要查找的值等于当前节点的值，则找到了目标节点，返回该节点。
    3. 如果要查找的值小于当前节点的值，继续在当前节点的左子树中查找。
    4. 如果要查找的值大于当前节点的值，继续在当前节点的右子树中查找。
    5. 重复步骤3和4，直到找到目标节点或者遍历到叶子节点为止。

    二叉搜索树的时间复杂度取决于树的平衡性。在最坏情况下，树可能变成链表，导致插入、删除和查找操作的时间复杂度为 O(n)。但是，如果树保持平衡，例如平衡二叉搜索树（AVL树、红黑树等），则这些操作的时间复杂度可以保持在 O(log n)。

    以下是BST的代码实现：

    定义BST的节点结构BSTreeNode，包含左子树指针_left、右子树指针_right和键值_key。

    1. #include
    2. using namespace std;
    3.  
    4. template<class K>
    5. struct BSTreeNode
    6. {
    7. 	BSTreeNode* _left;
    8. 	BSTreeNode* _right;
    9. 	K _key;
    10.  
    11. 	BSTreeNode(const K& key)
    12. 		:_left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _key(key)
    15. 	{ }
    16. };

    定义BSTree类，其中的Find函数用于查找指定的键值。从根节点开始，根据当前节点的键值与目标键值的大小关系，沿着左子树或右子树逐步查找，直到找到目标键值或遍历完整个树。

    1. template<class K>
    2. class BSTree
    3. {
    4. 	typedef BSTreeNode Node;
    5. public:
    6. 	bool Find(const K& key)
    7. 	{
    8. 		Node* cur = _root;
    9. 		while (cur)
    10. 		{
    11. 			if (cur->_key < key)
    12. 			{
    13. 				cur = cur->_right;
    14. 			}
    15. 			else if (cur->_key > key)
    16. 			{
    17. 				cur = cur->_left;
    18. 			}
    19. 			else
    20. 				return true;
    21. 		}
    22. 		return false;
    23. 	}
    1. 	bool Erase(const K& key)
    2. 	{
    3. 		if (_root == nullptr)
    4. 			return false;
    5.  
    6. 		Node* cur = _root;
    7. 		Node* parent = nullptr;
    8. 		while (cur)
    9. 		{
    10. 			//不能在这更新parent,否则删除节点时parent和cur指向相同
    11. 			if (key < cur->_key)
    12. 			{
    13. 				parent = cur;
    14. 				cur = cur->_left;
    15. 			}
    16. 			else if (key > cur->_key)
    17. 			{
    18. 				parent = cur;
    19. 				cur = cur->_right;
    20. 			}
    21. 			else//删除操作
    22. 			{
    23. 				//只有一个孩子，托孤法				
    24. 				if (cur->_right == nullptr)//只有一个左孩子（+无孩子）
    25. 				{
    26. 					if (parent == nullptr)
    27. 					{
    28. 						_root = cur->_left;
    29. 						delete cur;
    30. 						return true;
    31. 					}
    32.  
    33. 					if (cur == parent->_left)
    34. 						parent->_left = cur->_left;
    35. 					else
    36. 						parent->_right = cur->_left;
    37. 					delete cur;
    38. 				}
    39. 				else if (cur->_left == nullptr)//只有一个右孩子
    40. 				{
    41. 					if (parent == nullptr)
    42. 					{
    43. 						_root = cur->_right;
    44. 						delete cur;
    45. 						return true;
    46. 					}
    47.  
    48. 					if (cur == parent->_left)
    49. 						parent->_left = cur->_right;
    50. 					else
    51. 						parent->_right = cur->_right;
    52. 					delete cur;
    53. 				}
    54. 				else //左右都有孩子
    55. 				{
    56. 					//有两个孩子，替换删除法；左子树的最大（最右）节点或右子数的最小（最左）节点
    57. 					//找到右子树的最左节点
    58. 					Node* subLeft = cur->_right;
    59. 					Node* subParent = cur;
    60. 					while (subLeft->_left)
    61. 					{
    62. 						subParent = subLeft;
    63. 						subLeft = subLeft->_left;
    64. 					}
    65. 					swap(subLeft->_key, cur->_key);
    66. 					//经过交换后，现在只需删除subLeft，已经转化为只有一个孩子的情况，使用托孤法
    67. 					if (subParent->_left == subLeft)
    68. 						subParent->_left = subLeft->_right;
    69. 					else
    70. 						subParent->_right = subLeft->_right;
    71.  
    72. 					delete subLeft;
    73. 				}
    74. 				return true;
    75. 			}
    76. 		}
    77. 		return false;
    78. 	}

    Erase函数用于删除指定的键值对应的节点。删除操作分为四种情况：

    1. 节点只有一个左孩子（包括无孩子），使用"托孤法"将其父节点指向其左孩子。
    2. 节点只有一个右孩子，同样使用"托孤法"将其父节点指向其右孩子。
    3. 节点既有左孩子又有右孩子，采用"替换删除法"，找到右子树的最左节点（或左子树的最右节点），将其键值与当前节点键值交换，然后删除这个最左节点。
    4. 无孩子可以随便合并到只有一个孩子的情况，代码是兼容的。

    1. 	bool insert(const K& key)
    2. 	{
    3. 		if (_root == nullptr)
    4. 		{
    5. 			_root = new Node(key);
    6. 			return true;
    7. 		}
    8. 		else
    9. 		{
    10. 			Node* parent = nullptr;
    11. 			Node* cur = _root;
    12. 			while (cur)
    13. 			{	
    14. 				//parent = cur; 虽然写这里也可以，但是写在里面结构更清晰
    15. 				if (cur->_key > key)
    16. 				{
    17. 					parent = cur;
    18. 					cur = cur->_left;
    19. 				}
    20. 				else if (cur->_key < key)
    21. 				{
    22. 					parent = cur;
    23. 					cur = cur->_right;
    24. 				}
    25. 				else
    26. 					return false;
    27. 			}
    28.  
    29. 			cur = new Node(key);
    30. 			parent->_key > cur->_key ? parent->_left = cur : parent->_right = cur;
    31. 		}
    32. 	}

    insert函数用于插入一个新节点。若树为空，直接创建根节点；否则，从根节点开始，根据当前节点的键值与待插入键值的大小关系，沿着左子树或右子树逐步查找插入位置，直到找到一个空位置，然后创建新节点并插入。

    1. 	void midOrder()
    2. 	{
    3. 		_midOrder(_root);
    4. 	}
    5. private:
    6. 	Node * _root = nullptr;
    7.  
    8. 	void _midOrder(Node* node)
    9. 	{
    10. 		if (node == nullptr)
    11. 			return;
    12.  
    13. 		_midOrder(node->_left);
    14. 		cout << node->_key << " ";
    15. 		_midOrder(node->_right);
    16. 	}
    17. };

    midOrder函数用于中序遍历树。由于根节点指针_root是私有的，无法在类外直接使用，因此提供了一个公有的无参遍历函数，在类内部调用私有的递归遍历函数_midOrder。

    1. int main()
    2. {
    3. 	int a[] = { 8,3,1,6,4,7,14,13 };
    4. 	BSTree<int> bst;
    5. 	for (int x : a)
    6. 	{
    7. 		bst.insert(x);
    8. 	}
    9. 	
    10. 	//测试：遍历删除
    11. 	for (int x : a)
    12. 	{
    13. 		bst.midOrder();
    14. 		cout << endl;
    15. 		bst.Erase(x);
    16. 		bst.midOrder();
    17. 		cout << endl;
    18. 		cout << endl;
    19. 	}
    20.  
    21. 	cout << "全部删除成功" << endl;
    22. 	system("pause");
    23. 	return 0;
    24. }

    在主函数中，首先创建了一个BSTree对象bst，然后依次插入数组a中的元素。接下来进行遍历删除的测试，每次删除一个元素后，都会输出当前树的中序遍历结果。最后输出"全部删除成功"，并暂停程序的执行。

    这段代码实现了BST的基本功能，包括查找、插入和删除操作，并且通过遍历删除的测试验证了代码的正确性。

    这是插入后建立的二叉树的逻辑关系：

    完整代码如下:

    1. #include
    2. using namespace std;
    3.  
    4. template<class K>
    5. struct BSTreeNode
    6. {
    7. 	BSTreeNode* _left;
    8. 	BSTreeNode* _right;
    9. 	K _key;
    10.  
    11. 	BSTreeNode(const K& key)
    12. 		:_left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _key(key)
    15. 	{ }
    16. };
    17.  
    18. template<class K>
    19. class BSTree
    20. {
    21. 	typedef BSTreeNode Node;
    22. public:
    23. 	bool Find(const K& key)
    24. 	{
    25. 		Node* cur = _root;
    26. 		while (cur)
    27. 		{
    28. 			if (cur->_key < key)
    29. 			{
    30. 				cur = cur->_right;
    31. 			}
    32. 			else if (cur->_key > key)
    33. 			{
    34. 				cur = cur->_left;
    35. 			}
    36. 			else
    37. 				return true;
    38. 		}
    39. 		return false;
    40. 	}
    41.  
    42. 	//删除节点，四种情况，可以合并为三种执行
    43. 	bool Erase(const K& key)
    44. 	{
    45. 		if (_root == nullptr)
    46. 			return false;
    47.  
    48. 		Node* cur = _root;
    49. 		Node* parent = nullptr;
    50. 		while (cur)
    51. 		{
    52. 			//不能在这更新parent,否则删除节点时parent和cur指向相同
    53. 			if (key < cur->_key)
    54. 			{
    55. 				parent = cur;
    56. 				cur = cur->_left;
    57. 			}
    58. 			else if (key > cur->_key)
    59. 			{
    60. 				parent = cur;
    61. 				cur = cur->_right;
    62. 			}
    63. 			else//删除操作
    64. 			{
    65. 				//只有一个孩子，托孤法				
    66. 				if (cur->_right == nullptr)//只有一个左孩子（+无孩子）
    67. 				{
    68. 					if (parent == nullptr)
    69. 					{
    70. 						_root = cur->_left;
    71. 						delete cur;
    72. 						return true;
    73. 					}
    74.  
    75. 					if (cur == parent->_left)
    76. 						parent->_left = cur->_left;
    77. 					else
    78. 						parent->_right = cur->_left;
    79. 					delete cur;
    80. 				}
    81. 				else if (cur->_left == nullptr)//只有一个右孩子
    82. 				{
    83. 					if (parent == nullptr)
    84. 					{
    85. 						_root = cur->_right;
    86. 						delete cur;
    87. 						return true;
    88. 					}
    89.  
    90. 					if (cur == parent->_left)
    91. 						parent->_left = cur->_right;
    92. 					else
    93. 						parent->_right = cur->_right;
    94. 					delete cur;
    95. 				}
    96. 				else //左右都有孩子
    97. 				{
    98. 					//有两个孩子，替换删除法；左子树的最大（最右）节点或右子数的最小（最左）节点
    99. 					//找到右子树的最左节点
    100. 					Node* subLeft = cur->_right;
    101. 					Node* subParent = cur;
    102. 					while (subLeft->_left)
    103. 					{
    104. 						subParent = subLeft;
    105. 						subLeft = subLeft->_left;
    106. 					}
    107. 					swap(subLeft->_key, cur->_key);
    108. 					//经过交换后，现在只需删除subLeft，已经转化为只有一个孩子的情况，使用托孤法
    109. 					if (subParent->_left == subLeft)
    110. 						subParent->_left = subLeft->_right;
    111. 					else
    112. 						subParent->_right = subLeft->_right;
    113.  
    114. 					delete subLeft;
    115. 				}
    116. 				return true;
    117. 			}
    118. 		}
    119. 		return false;
    120. 	}
    121.  
    122. 	//插入节点，要保证插入的值不同，一旦发现相同的，返回false
    123. 	bool insert(const K& key)
    124. 	{
    125. 		if (_root == nullptr)
    126. 		{
    127. 			_root = new Node(key);
    128. 			return true;
    129. 		}
    130. 		else
    131. 		{
    132. 			Node* parent = nullptr;
    133. 			Node* cur = _root;
    134. 			while (cur)
    135. 			{	
    136. 				//parent = cur; 虽然写这里也可以，但是写在里面结构更清晰
    137. 				if (cur->_key > key)
    138. 				{
    139. 					parent = cur;
    140. 					cur = cur->_left;
    141. 				}
    142. 				else if (cur->_key < key)
    143. 				{
    144. 					parent = cur;
    145. 					cur = cur->_right;
    146. 				}
    147. 				else
    148. 					return false;
    149. 			}
    150.  
    151. 			cur = new Node(key);
    152. 			parent->_key > cur->_key ? parent->_left = cur : parent->_right = cur;
    153. 		}
    154. 	}
    155.  
    156. 	//遍历树需要传根节点指针，但是树的指针是私有的
    157. 	//解决方法：套一层壳，给用户提供无参的遍历函数，在类内部调用传参遍历函数
    158. 	void midOrder()
    159. 	{
    160. 		_midOrder(_root);
    161. 	}
    162. private:
    163. 	Node * _root = nullptr;
    164.  
    165. 	void _midOrder(Node* node)
    166. 	{
    167. 		if (node == nullptr)
    168. 			return;
    169.  
    170. 		_midOrder(node->_left);
    171. 		cout << node->_key << " ";
    172. 		_midOrder(node->_right);
    173. 	}
    174. };
    175.  
    176.  
    177. int main()
    178. {
    179. 	int a[] = { 8,3,1,6,4,7,14,13 };
    180. 	BSTree<int> bst;
    181. 	for (int x : a)
    182. 	{
    183. 		bst.insert(x);
    184. 	}
    185. 	
    186. 	//测试：遍历删除
    187. 	for (int x : a)
    188. 	{
    189. 		bst.midOrder();
    190. 		cout << endl;
    191. 		bst.Erase(x);
    192. 		bst.midOrder();
    193. 		cout << endl;
    194. 		cout << endl;
    195. 	}
    196.  
    197. 	cout << "全部删除成功" << endl;
    198. 	system("pause");
    199. 	return 0;
    200. }

    以上是BST的实现是以迭代方式（循环），下一篇博客会展示以递归方式实现BST的增、删、查。

  • 相关阅读:
    Keytool配置 Tomcat的HTTPS双向认证
    CSS小计
    健壮性测试是什么？
    mysql事务和事务隔离级别
    Muduo网络库之Channel、EPollPoller与EventLoop类【深度解析】
    国内一些镜像源
    RCU Library
    【AutoSAR CAN】02 - 硬件过滤器配置
    3D医学影像PACS系统源代码
    加密与解密笔记-4.1
  • 原文地址：https://blog.csdn.net/weixin_73567058/article/details/134052295