• 数据结构：二叉搜索树

    目录

    1、二叉搜索树概念

    2、 二叉搜索树的插入

    3、二叉搜索树的查找

    4、二叉搜索树的删除

    5、二叉搜索树的中序遍历

    实现

    1、二叉搜索树概念

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

     定义一个二叉搜索树类

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode<K>* _left;
    5. 	BSTreeNode<K>* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 	{}
    13. };
    14.  
    15. template<class K>
    16. class BSTree
    17. {
    18. 	typedef BSTreeNode<K> Node;
    19. private:
    20. 	Node* _root = nullptr;
    21. public:
    22. 	bool Insert(const K& key);            //插入
    23. 	bool Find(const K& key);              //查找
    24. 	bool Erase(const K& key);             //删除
    25. 	void InOrder();                       //中序遍历
    26. 	void _InOrder(Node* root);
    27.  
    28.  
    29. };

    2、 二叉搜索树的插入

    • 树为空，则直接新增节点，赋值给root指针
    • 树不空，按二叉搜索树性质查找插入位置，插入新节点

    1. template<class K>
    2. bool BSTree<K>::Insert(const K& key)
    3. {
    4. 	if (_root == nullptr)
    5. 	{
    6. 		_root = new Node(key);
    7. 		return true;
    8. 	}
    9.  
    10. 	Node* parent = nullptr;
    11. 	Node* cur = _root;
    12. 	while (cur != nullptr)
    13. 	{
    14. 		parent = cur;
    15.  
    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;       //cur->_key == key
    27. 		}
    28. 	}
    29.  
    30. 	cur = new Node(key);
    31. 	if (parent->_key < key)
    32. 	{
    33. 		parent->_right = cur;
    34. 	}
    35. 	else
    36. 	{
    37. 		parent->_left = cur;
    38. 	}
    39.  
    40. 	return true;
    41. }

    3、二叉搜索树的查找

    • 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
    • 最多查找高度次，走到到空，还没找到，这个值不存在。 
    1. template<class K>
    2. bool BSTree<K>::Find(const K& key)
    3. {
    4. 	Node* cur = _root;
    5. 	while (cur != nullptr)
    6. 	{
    7. 		if (key < cur->_key)      //key小于cur->_key,cur向左走
    8. 		{
    9. 			cur = cur->_left;
    10. 		}
    11. 		else if (key > cur->_key)   //key大于于cur->_key,cur向右走
    12. 		{
    13. 			cur = cur->_right;
    14. 		}
    15. 		else                       //key等于于cur->_key，返回true
    16. 		{
    17. 			return true;
    18. 		}
    19. 	}
    20. 	return false;                 //不存在返回false
    21.  
    22. }

    4、二叉搜索树的删除

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

     替换法删除：我们可以使用被删的节点的左子树的最大节点或者右子树的最小节点，来替代被删的节点的值

    1. template<class K>
    2. bool BSTree::Erase(const K& key)
    3. {
    4. 	Node* parent = nullptr;
    5. 	Node* cur = _root;
    6. 	while (cur != nullptr)
    7. 	{
    8. 		if (cur->_key < key)
    9. 		{
    10. 			parent = cur;
    11. 			cur = cur->_right;
    12. 		}
    13. 		else if (cur->_key > key)
    14. 		{
    15. 			parent = cur;
    16. 			cur = cur->_left;
    17. 		}
    18. 		else                             //找到要删除的数
    19. 		{
    20. 			// 准备删除
    21.             //分为三种情况
    22.             //1、左为空
    23.             //2、右为空
    24.             //3、左右都不为空  
    25. 			if (cur->_left == nullptr)   //左为空
    26. 			{
    27. 				if (cur == _root)      //1、要删除的点为根节点
    28. 				{
    29. 					_root = cur->_right;
    30. 				}
    31. 				else
    32. 				{
    33. 					if (cur == parent->_left)
    34. 					{
    35. 						parent->_left = cur->_right;
    36. 					}
    37. 					else
    38. 					{
    39. 						parent->_right = cur->_right;
    40. 					}
    41. 				}
    42. 			}
    43. 			else if (cur->_right == nullptr)   //右为空
    44. 			{
    45. 				if (cur == _root)             //1、要删除的点为根节点
    46. 				{
    47. 					_root = cur->_left;
    48. 				}
    49. 				else
    50. 				{
    51. 					if (cur == parent->_left)
    52. 					{
    53. 						parent->_left = cur->_left;
    54. 					}
    55. 					else
    56. 					{
    57. 						parent->_right = cur->_left;
    58. 					}
    59. 				}
    60. 			}
    61. 			else                     //左右都不为空
    62. 			{
    63.                   //我们可以使用被删的节点的左子树的最大节点或者右子树的最小节点，
    64.                   //来替代被删的节点的值
    65. 				Node* parent = cur;
    66. 				Node* subLeft = cur->_right;
    67. 				while (subLeft->_left)
    68. 				{
    69. 					parent = subLeft;
    70. 					subLeft = subLeft->_left;    // 右子树的最小节点(最左节点)
    71. 				}
    72.  
    73. 				swap(cur->_key, subLeft->_key);  //右子树的最小节点与被删节点的值交换
    74.  
    75. 				if (subLeft == parent->_left)
    76.                 {
    77. 					parent->_left = subLeft->_right;
    78.                 }
    79. 				else
    80.                 {
    81. 					parent->_right = subLeft->_right;
    82.                 }
    83. 			}
    84.  
    85. 			return true;
    86. 		}
    87. 	}
    88.  
    89. 	return false;         //没有找到要删除的数
    90. }

    5、二叉搜索树的中序遍历

    根据二叉搜索树的特性，我们可以推出二叉搜索树的中序遍历是一个有序的数据

    我们可以采用递归的方法去遍历

    1. template<class K>
    2. void BSTree<K>::InOrder()
    3. {
    4. 	_InOrder(_root);
    5. 	cout << endl;
    6. }
    7. template<class K>
    8. void BSTree<K>::_InOrder(Node* root)
    9. {
    10. 	if (root == nullptr)
    11. 		return;
    12.  
    13. 	_InOrder(root->_left);
    14. 	cout << root->_key << " ";
    15. 	_InOrder(root->_right);
    16. }

    实现

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode<K>* _left;
    5. 	BSTreeNode<K>* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 	{}
    13. };
    14.  
    15. template<class K>
    16. class BSTree
    17. {
    18. 	typedef BSTreeNode<K> Node;
    19. private:
    20. 	Node* _root = nullptr;
    21. public:
    22. 	bool Insert(const K& key);            //插入
    23. 	bool Find(const K& key);              //查找
    24. 	bool Erase(const K& key);             //删除
    25. 	void InOrder();                       //中序遍历
    26. 	void _InOrder(Node* root);
    27.  
    28.  
    29. };
    30.  
    31. template<class K>
    32. bool BSTree<K>::Insert(const K& key)
    33. {
    34. 	if (_root == nullptr)
    35. 	{
    36. 		_root = new Node(key);
    37. 		return true;
    38. 	}
    39.  
    40. 	Node* parent = nullptr;
    41. 	Node* cur = _root;
    42. 	while (cur != nullptr)
    43. 	{
    44. 		parent = cur;
    45.  
    46. 		if (cur->_key < key)
    47. 		{
    48. 			cur = cur->_right;
    49. 		}
    50. 		else if (cur->_key > key)
    51. 		{
    52. 			cur = cur->_left;
    53. 		}
    54. 		else
    55. 		{
    56. 			return false;       //cur->_key == key
    57. 		}
    58. 	}
    59.  
    60. 	cur = new Node(key);
    61. 	if (parent->_key < key)
    62. 	{
    63. 		parent->_right = cur;
    64. 	}
    65. 	else
    66. 	{
    67. 		parent->_left = cur;
    68. 	}
    69.  
    70. 	return true;
    71. }
    72.  
    73. template<class K>
    74. bool BSTree<K>::Find(const K& key)
    75. {
    76. 	Node* cur = _root;
    77. 	while (cur != nullptr)
    78. 	{
    79. 		if (key < cur->_key)      //key小于cur->_key,cur向左走
    80. 		{
    81. 			cur = cur->_left;
    82. 		}
    83. 		else if (key > cur->_key)   //key大于于cur->_key,cur向右走
    84. 		{
    85. 			cur = cur->_right;
    86. 		}
    87. 		else                       //key等于于cur->_key，返回true
    88. 		{
    89. 			return true;
    90. 		}
    91. 	}
    92. 	return false;                 //不存在返回false
    93.  
    94. }
    95.  
    96. template<class K>
    97. bool BSTree<K>::Erase(const K& key)
    98. {
    99. 	Node* parent = nullptr;
    100. 	Node* cur = _root;
    101. 	while (cur != nullptr)
    102. 	{
    103. 		if (cur->_key < key)
    104. 		{
    105. 			parent = cur;
    106. 			cur = cur->_right;
    107. 		}
    108. 		else if (cur->_key > key)
    109. 		{
    110. 			parent = cur;
    111. 			cur = cur->_left;
    112. 		}
    113. 		else
    114. 		{
    115. 			// 准备删除  
    116. 			if (cur->_left == nullptr)   //左为空
    117. 			{
    118. 				if (cur == _root)
    119. 				{
    120. 					_root = cur->_right;
    121. 				}
    122. 				else
    123. 				{
    124. 					if (cur == parent->_left)
    125. 					{
    126. 						parent->_left = cur->_right;
    127. 					}
    128. 					else
    129. 					{
    130. 						parent->_right = cur->_right;
    131. 					}
    132. 				}
    133. 			}
    134. 			else if (cur->_right == nullptr)   //右为空
    135. 			{
    136. 				if (cur == _root)
    137. 				{
    138. 					_root = cur->_left;
    139. 				}
    140. 				else
    141. 				{
    142. 					if (cur == parent->_left)
    143. 					{
    144. 						parent->_left = cur->_left;
    145. 					}
    146. 					else
    147. 					{
    148. 						parent->_right = cur->_left;
    149. 					}
    150. 				}
    151. 			}
    152. 			else
    153. 			{//左右都不为空
    154.  
    155. 				// 右树的最小节点(最左节点)
    156. 				Node* parent = cur;
    157. 				Node* subLeft = cur->_right;
    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. 					parent->_left = subLeft->_right;
    168. 				else
    169. 					parent->_right = subLeft->_right;
    170. 			}
    171.  
    172. 			return true;
    173. 		}
    174. 	}
    175.  
    176. 	return false;
    177. }
    178. template<class K>
    179. void BSTree<K>::InOrder()
    180. {
    181. 	_InOrder(_root);
    182. 	cout << endl;
    183. }
    184. template<class K>
    185. void BSTree<K>::_InOrder(Node* root)
    186. {
    187. 	if (root == nullptr)
    188. 		return;
    189.  
    190. 	_InOrder(root->_left);
    191. 	cout << root->_key << " ";
    192. 	_InOrder(root->_right);
    193. }

  • 相关阅读:
    Idea中运行sparkSQL
    45.120.101.X 如何找出网站建设中弱点和漏洞
    AMBA总线相关知识记录
    Windows OpenGL ES 图像灰度图
    跟李沐学AI之现代卷积神经网络
    MySQL入门第六天——函数与条件查询
    C#中List、Dictionary、HashSet用法以及区别
    java图片处理
    Mysql 自带分页异常
    为期一周的数据分析与Excel，继续加油，多练习
  • 原文地址：https://blog.csdn.net/weixin_74268082/article/details/134022226