• 搜索二叉树实现（非递归版本）

    目录

    一，搜索二叉树是个啥？

    二，搜索二叉树的实现

    1.前期工作

    2.方法实现

    1.插入

    2，查找

    3.删除

    三，实现二叉搜索树的全部代码

    一，搜索二叉树是个啥？

    话不多所，先给各位来一个搜索二叉树：

    从这棵树中可以看到这棵树有如下性质：

    1.根节点的左节点的值小于根节点的值，根节点的右节点的值大于根节点的值。

    2.这棵树的中序遍历的结果是一个升序的数组。

    3.这棵树的左子树和右子树都是一颗搜索二叉树。

    以上三点便是一棵搜索二叉树的性质！！！

    二，搜索二叉树的实现

    1.前期工作

         要实现一棵搜索二叉树，首先便要实现它的各个节点。实现如下：

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

    这个节点的成员就是它的左指针_left，右指针_right，还有这个节点里包含的一个值_key。

          接下来便要开始实现一下这棵树。实现如下：

    1. template<class K>
    2. class BSTree
    3. {
    4.   public:
    5.  
    6.   private:
    7.     BSNode* _root;
    8. }

    这棵树的成员便只有一个，那便是_root这个根节点。

    2.方法实现

    1.插入

    在前期工作准备好以后便要来实现我们的方法了，现在来实现我们的插入方法。实现思路如下：

    1.因为我们的_root是是私有的，所以我们不能实现一个需要传参的Insert方法。所以它必须是无参的。

    2.要实现一个无参的方法，那我们就得套一层_Insert()方法在Insert()方法里面。

    3.实现_Insert()方法步骤如下：

    1.如果_root是nullptr便new一个节点,让_root接收这个新节点。

    2.如果key比我当前的节点值要大，便向右走。

    3.如果比我当前的节点值要小，那就向左走。

    4.如果走到空（_root的替代值未为nullptr）那就在该位置生成一个新节点，并让该节点的parent的左或者右指针指向这个新节点。

    代码如下：

    实现无参：

    1. bool Insert( const K& key)
    2. 	{
    3. 		return _Insert(key);
    4. 	}

    _Insert()方法实现：

    1. 	bool _Insert(const K& key)
    2. 	{
    3. 		if (_root == nullptr)//若_root是一个nullptr那就给_root new 一个节点
    4. 		{
    5. 			_root = new BNode(key);
    6. 			return true;
    7. 		}
    8. 		else
    9. 		{
    10. 			BNode* cur = _root;
    11. 			BNode* parent = nullptr;
    12.  
    13. 			while (cur!=nullptr)//找位置
    14. 			{
    15. 				parent = cur;
    16. 				if (cur->_key < key)
    17. 				{
    18. 					cur = cur->_right;
    19. 				}
    20. 				else if (cur->_key > key)
    21. 				{
    22. 					cur = cur->_left;
    23. 				}
    24. 				else
    25. 				{
    26. 					return false;
    27. 				}
    28. 			}
    29.  
    30. 			cur = new BNode(key);//找到后便给这个位置new一个节点
    31.  
    32. 			if (key > parent->_key)//判断一下是左边还是右边然后链接
    33. 			{
    34. 				parent->_right = cur;
    35. 			}
    36. 			else
    37. 			{
    38. 				parent->_left = cur;
    39. 			}
    40. 			return true;
    41. 		}
    42. 	    
    43. 	}
    2，查找

       查找方法的实现也很简单，其实就是将_Insert()里面的查找代码给复制一份过来便可以了。同样的，我们的查找算法在类的外边也是不能调用_root的，所以也会有封装。Find()函数实现如下：

    1.     bool Find(const K& key)
    2. 	{
    3. 		return _Find(key);
    4. 	}

         我们的_Find()函数实现如下：

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

    删除方法的实现大概是最难写的一个代码了，首先我们得先找到这个要删除的节点找到以后分为三种情况讨论：

    以如下搜索二叉树为例：

    1.要删除节点的左节点为空。如以下情况：

    比如要删除10这个节点，我们该如何操作呢？

    我们的操作如下：

    1.找到我的父亲。

    2.判断我是父亲的那个节点。

    3.如果我是父亲的左节点便让父亲的左节点连接到我的右节点上。如果我是父亲右节点，便让父亲的右节点指向我的右节点。

    但是这里需要注意一个点：如果我是root，我便没有父亲。如以下情况：

    在这种情况下我们便可以直接让右节点担任root节点：

    1. if (cur == _root)
    2. {
    3.    _root = _root->_right;
    4. }

    左节点为空的情况下实现删除代码如下：
     

    1.                    if (cur->_left == nullptr)
    2. 					{
    3. 						if (cur == _root)
    4. 						{
    5. 							_root = _root->_right;
    6. 						}
    7. 						else
    8. 						{
    9. 							if (cur->_key > parent->_key)
    10. 							{
    11. 								parent->_right = cur->_right;
    12. 							}
    13. 							else
    14. 							{
    15. 								parent->_left = cur->_right;
    16. 							}
    17. 						}
    18. 						return true;
    19. 					}

    2.要删除的节点的右节点为空。
    其实这种情况下的的代码的值和前面的实现逻辑是一样的，

    所以不解释直接给出实现代码：

    1.                     else if (cur->_right == nullptr)
    2. 					{
    3. 						if (cur == _root)
    4. 						{
    5. 							_root = cur->_left;
    6. 						}
    7. 						else
    8. 						{
    9. 							if (cur->_key > parent->_key)
    10. 							{
    11. 								parent->_right = cur->_left;
    12. 							}
    13. 							else
    14. 							{
    15. 								parent->_left = cur->_left;
    16. 							}
    17. 						}
    18. 						return true;
    19. 					}

    3.当我要删除的节点的左右两个节点都在

    这个删除便是我们这个删除方法里面最难实现的一个代码，在这里我们要使用替换法来删除：

    1.如何使用替换法呢？

    步骤：1.定义parent和subLeft，subLeft定义为cur->right。

               记录我的父亲，这个父亲要初始化cur(当前节点)。

                2.找到当前节点的右子树的最左节点subLeft并更新parent位subLeft的父亲节点。

                3.交换cur节点和subLeft两个节点的值（使用swap).

                4.链接。

     了解完以上步骤以后写下如下代码：

    1.                     else
    2. 					{//有两个孩子，替换法。（找右子树的最左节点）
    3. 						BNode* Parent = cur;
    4. 						BNode* SubLeft = cur->_right;
    5.  
    6. 						while (SubLeft->_left)
    7. 						{
    8. 							Parent = SubLeft;
    9. 							SubLeft = SubLeft->_left;
    10. 						}
    11.                         
    12. 						swap(cur->_key, SubLeft->_key);
    13.  
    14. 						if (SubLeft == Parent->_left)
    15. 						{
    16. 							Parent->_left = SubLeft->_left;
    17. 						}
    18. 						else
    19. 						{
    20. 							Parent->_right = SubLeft->_left;
    21. 						}
    22. 						 
    23. 						return true;
    24. 					}

     在这里解释一下：

    1.为什么parent要初始为cur,如以下例子：

                   

    假如是以上的情况，那我的这段代码是不会进去的：

    1. while (SubLeft->_left)
    2. {
    3. 	Parent = SubLeft;
    4. 	SubLeft = SubLeft->_left;
    5. }

    那如果我的parent 如果赋值为nullptr的话，那便会解引用nullptr:

    1. if (SubLeft == Parent->_left)
    2. {
    3.   Parent->_left = SubLeft->_left;
    4. }
    5. else
    6. {
    7.   Parent->_right = SubLeft->_left;
    8. }

    所以我们必须要将parent初始化为cur。这个时候也能删除。

    2.链接该如何连接？

    我实现的连接代码是这样的：

    1. if (SubLeft == Parent->_left)
    2. {
    3.   Parent->_left = SubLeft->_left;
    4. }
    5. else
    6. {
    7.   Parent->_right = SubLeft->_left;
    8. }

    在这里我们首先得先判断一下我们的subLeft是我的parent节点的哪一位？

    可能是右节点：

    就像我们上面的删除8的情况一样，我要删除的是根节点，我的根节点的左节点是nullptr。

    也可能是左节点：

    我进入了循环：

    1. while (SubLeft->_left)
    2. {
    3.   Parent = SubLeft;
    4.   SubLeft = SubLeft->_left;
    5. }

    三，实现二叉搜索树的全部代码

    1. #include
    2. using namespace std;
    3. #include
    4.  
    5.  
    6. template<class K>
    7. struct BNode
    8. {
    9. 	BNode(const K& key)
    10. 		:_key(key)
    11. 		,_left(nullptr)
    12. 		,_right(nullptr)
    13. 	{}
    14.  
    15. 	K _key;
    16. 	BNode* _left;
    17. 	BNode* _right;
    18. };
    19.  
    20.  
    21. template<class K>
    22. class BSTree
    23. {
    24. public:
    25.  
    26. 	bool Insert( const K& key)
    27. 	{
    28. 		return _Insert(key);
    29. 	}
    30.  
    31. 	void Inorder()
    32. 	{
    33. 	 _Inorder(_root);
    34. 	 cout << endl;
    35. 	}
    36.  
    37. 	bool Find(const K& key)
    38. 	{
    39. 		return _Find(key);
    40. 	}
    41.  
    42. 	bool Erase(const K& key)
    43. 	{
    44. 		return _Erase(key);
    45. 	}
    46. 	 
    47. private:
    48. 		bool _Insert(const K& key)
    49. 	{
    50. 		if (_root == nullptr)
    51. 		{
    52. 			_root = new BNode(key);
    53. 			return true;
    54. 		}
    55. 		else
    56. 		{
    57. 			BNode* cur = _root;
    58. 			BNode* parent = nullptr;
    59.  
    60. 			while (cur!=nullptr)
    61. 			{
    62. 				parent = cur;
    63. 				if (cur->_key < key)
    64. 				{
    65. 					cur = cur->_right;
    66. 				}
    67. 				else if (cur->_key > key)
    68. 				{
    69. 					cur = cur->_left;
    70. 				}
    71. 				else
    72. 				{
    73. 					return false;
    74. 				}
    75. 			}
    76.  
    77. 			cur = new BNode(key);
    78. 			if (key > parent->_key)
    79. 			{
    80. 				parent->_right = cur;
    81. 			}
    82. 			else
    83. 			{
    84. 				parent->_left = cur;
    85. 			}
    86. 			return true;
    87. 		}
    88. 	    
    89. 	}
    90.  
    91. 		bool _Erase(const K& key)
    92. 		{
    93. 			assert(_root);
    94. 			BNode* cur = _root;
    95. 			BNode* parent = cur;
    96.  
    97.  
    98. 			while (cur)
    99. 			{
    100. 				if (key > cur->_key)
    101. 				{
    102. 					parent = cur;
    103. 					cur = cur->_right;
    104. 				}
    105.  
    106. 				else if (key < cur->_key)
    107. 				{
    108. 					parent = cur;
    109. 					cur = cur->_left;
    110. 				}
    111. 				else
    112. 				{
    113. 					if (cur->_left == nullptr)
    114. 					{
    115. 						if (cur == _root)
    116. 						{
    117. 							_root = _root->_right;
    118. 						}
    119. 						else
    120. 						{
    121. 							if (cur->_key > parent->_key)
    122. 							{
    123. 								parent->_right = cur->_right;
    124. 							}
    125. 							else
    126. 							{
    127. 								parent->_left = cur->_right;
    128. 							}
    129. 						}
    130. 						return true;
    131. 					}
    132.  
    133. 					else if (cur->_right == nullptr)
    134. 					{
    135. 						if (cur == _root)
    136. 						{
    137. 							_root = cur->_left;
    138. 						}
    139. 						else
    140. 						{
    141. 							if (cur->_key > parent->_key)
    142. 							{
    143. 								parent->_right = cur->_left;
    144. 							}
    145. 							else
    146. 							{
    147. 								parent->_left = cur->_left;
    148. 							}
    149. 						}
    150. 						return true;
    151. 					}
    152.  
    153. 					else
    154. 					{//有两个孩子，替换法。（找右子树的最左节点）
    155. 						BNode* Parent = cur;
    156. 						BNode* SubLeft = cur->_right;
    157.  
    158. 						while (SubLeft->_left)
    159. 						{
    160. 							Parent = SubLeft;
    161. 							SubLeft = SubLeft->_left;
    162. 						}
    163.                         
    164. 						swap(cur->_key, SubLeft->_key);
    165.  
    166. 						if (SubLeft == Parent->_left)
    167. 						{
    168. 							Parent->_left = SubLeft->_left;
    169. 						}
    170. 						else
    171. 						{
    172. 							Parent->_right = SubLeft->_left;
    173. 						}
    174. 						 
    175. 						return true;
    176. 					}
    177. 				}
    178. 			}
    179.  
    180. 			return false;
    181.  
    182.  
    183.  
    184. 		}
    185.  
    186. 		bool _Find(const K& key)
    187. 		{
    188. 			BNode* cur = _root;
    189. 			while (cur)
    190. 			{
    191. 				if (key > cur->_key)
    192. 				{
    193. 					cur = cur->_right;
    194. 				}
    195.  
    196. 				else if (key < cur->_key)
    197. 				{
    198. 					cur = cur->_left;
    199. 				}
    200. 				else
    201. 				{
    202. 					return true;
    203. 				}
    204. 			}
    205.  
    206. 			return false;
    207. 		}
    208.  
    209. 		void _Inorder(BNode* root)
    210. 		{
    211. 			if (root == nullptr)
    212. 			{
    213. 				return;
    214. 			}
    215.  
    216. 			_Inorder(root->_left);
    217. 			cout << root->_key << " ";
    218. 			_Inorder(root->_right);
    219. 		}
    220.  
    221.  
    222.  
    223. 		BNode*_root =nullptr ;
    224. };

    实际上还可以实现一个递归版本的二叉搜索树，有时间再写。

  • 相关阅读:
    Spring实例化源码解析之Bean的实例化(十二)
    LeetCode 第 311 场周赛
    超越OpenCV速度的MorphologyEx函数实现（特别是对于二值图，速度是CV的4倍左右）。
    【分隔结构】同从分离
    STL——vector与迭代器
    【服务器数据恢复】RAID5强制上线后又被格式化的数据恢复案例
    【ES6】-- 对象、数组、字符串常用API
    JMeter数据库性能测试指南：全面掌握基础操作
    [附源码]计算机毕业设计springboot农村人居环境治理监管系统
    基础知识汇总一
  • 原文地址：https://blog.csdn.net/qq_41934502/article/details/134027109