• 【数据结构】二叉搜索树

    目录

    一、二叉搜索树

    ⭐1.1 二叉搜索树的概念

    ⭐1.2 二叉搜索树具有的性质：

    ⭐ 二、二叉搜索树的相关操作

    ⭐2.1二叉搜索树的节点的类型

    ⭐2.2二叉搜索树的查找（非递归）

    ⭐ 2.3二叉搜索树的查找（递归）

    ⭐2.4二叉搜索树的插入（非递归）

    ⭐2.5二叉搜索树的插入（递归）

    ⭐2.6二叉搜索树的删除（非递归）

    ⭐2.7二叉搜索树的删除（递归）

    ⭐2.8二叉搜索树的遍历

    ⭐2.9二叉树的拷贝构造及构造，赋值重载

    ⭐三、二叉搜索树的全部代码

    一、二叉搜索树

    ⭐1.1 二叉搜索树的概念

    二叉搜索树又称二叉排序树，是一种特殊有序的二叉树。

    ⭐1.2 二叉搜索树具有的性质：

    • 左子树不为空时，左子树所有节点的值都小于根节点的值
    • 右子树不为空时，右子树所有节点的值都大于根节点的值
    • 当然它的左右子树也满足该性质

    d5cc776e54e64213a80051f8edf149a1.png

    ⭐ 二、二叉搜索树的相关操作

    ①二叉搜索树的查找

    ②二叉搜索树的插入

    ③二叉搜索树的删除

    ⭐2.1二叉搜索树的节点的类型

    1. template <class K>//类模板
    2. struct BSTNode
    3. {
    4. 	BSTNode* left;
    5. 	BSTNode* right;
    6. 	K _key;
    7. 	BSTNode(K key)
    8. 		:left(nullptr)
    9. 		, right(nullptr)
    10. 		, _key(key)
    11. 	{}
    12. };

    ⭐2.2二叉搜索树的查找（非递归）

    从根开始查找，如果要查找的值比根节点大就往右子树走，如果比根节点小就往左子树走，依次循环，直到找到或走到空，则结束。找到则返回true，找不到返回false。

     

    1. bool find(const K& key)
    2. 	{
    3. 		BSTNode* cur = _root;
    4. 		while (cur)
    5. 		{
    6. 			if (cur->_key == key)
    7. 				return true;
    8. 			else if (cur->_key < key)
    9. 				cur = cur->right;
    10. 			else
    11. 				cur = cur->left;
    12. 		}
    13. 		return false;
    14. 	}

    ⭐ 2.3二叉搜索树的查找（递归）

    思路和非递归是一样的，如果查找的节点为空表示该树中没有该节点，返回false，如果找到了就返回true

    1. bool _findR(BSTNode* root, const K& key)
    2. 	{
    3. 		if (!root)return false;
    4. 		if (root->_key == key)
    5. 			return true;
    6. 		else if (root->_key > key)
    7. 			return _findR(root->left, key);//往左子树走
    8. 		else
    9. 			return _findR(root->right, key);//往右子树走
    10. 	}

    ⭐2.4二叉搜索树的插入（非递归）

    判断树是否为空，如果树为空的话，那么直接新增一个节点，并把该节点的地址赋给_root指针（指向根节点的指针）。如果树不为空，那么就按照二叉搜索树的查找方法，找到插入的位置，然后将新节点插入。注意：如果相等那么将返回false，不能插入

     

    1. bool insert(const K& key)
    2. 	{
    3. 		if (_root == nullptr)
    4. 		{
    5. 			_root= new BSTNode(key);
    6. 			return true;
    7. 		}
    8.  
    9. 		BSTNode* cur = _root, *parent=nullptr;
    10. 		while (cur)
    11. 		{
    12. 			if (_root->_key < key)
    13. 			{
    14. 				parent = cur;
    15. 				cur = cur->right;
    16. 			}
    17. 			else if (_root->_key > key)
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->left;
    21. 			}
    22. 			else
    23. 				return false;
    24. 		}
    25.  
    26. 		BSTNode* newnode = new BSTNode(key);
    27. 		if (parent->_key < key)
    28. 		{  //插入的节点大于该插入位置的父节点，往右边插入
    29. 			parent->right = newnode;
    30. 		}
    31. 		else
    32.         { //插入的节点小于该插入位置的父节点，往左边插入
    33. 			parent->left = newnode;
    34.         } 
    35. 		return true;
    36. 	}

    ⭐2.5二叉搜索树的插入（递归）

    这里传的是引用，形参的改变可以影响实参，所以直接给root赋值了

    1. bool _InsertR(BSTNode*& root, const K& key)
    2. 	{   //如果根节点为空，直接把值赋给root
    3. 		if (!root)
    4. 			BSTNode* root = new BSTNode(key);
    5. 		if (root->_key > key)
    6. 		{
    7. 			return _InsertR(root->left, key);
    8. 		}
    9. 		else if (root->_key < key)
    10. 		{
    11. 			return _InsertR(root->right, key);
    12. 		}
    13. 		else
    14. 			return false;
    15.  
    16. 	}

    ⭐2.6二叉搜索树的删除（非递归）

    首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
    况：

    1.  要删除的结点无孩子结点
    2.  要删除的结点只有左孩子结点
    3.  要删除的结点只有右孩子结点
    4.  要删除的结点有左、右孩子结点

    看起来有待删除节点有4种情况，实际情况1可以与情况2或者3合并起来，因此真正的删除过程
    如下：

    • 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
    • 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
    • 情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除
    1. bool Erase(const K& key)
    2. 	{
    3. 		BSTNode* cur = _root, * parent =nullptr;
    4. 		while (cur)
    5. 		{
    6. 			if (cur->_key < key)
    7. 			{
    8. 				parent = cur;
    9. 				cur = cur->right;
    10. 			}
    11. 			else if (cur->_key > key)
    12. 			{
    13. 				parent = cur;
    14. 				cur = cur->left;
    15. 			}
    16. 			else
    17. 			{   //没有左孩子节点
    18. 				if (cur->left == nullptr)
    19. 				{
    20. 					if (parent == nullptr)
    21. 					{
    22. 						_root = _root->right;
    23. 					}
    24. 					else if (parent->left == cur)
    25. 					{
    26. 						parent->left = cur->right;
    27. 					}
    28. 					else
    29. 					{
    30. 						parent->right = cur->right;
    31. 					}
    32. 					delete cur;
    33. 				}
    34.                   //没有右孩子节点
    35. 				else if (cur->right == nullptr)
    36. 				{
    37. 					if (parent == nullptr)
    38. 					{
    39. 						_root = _root->right;
    40. 					}
    41. 					else if (parent->left == cur)
    42. 					{
    43. 						parent->left = cur->left;
    44. 					}
    45. 					else
    46. 					{
    47. 						parent->right = cur->left;
    48. 					}
    49. 					delete cur;
    50. 				}
    51.                  //左右孩子都有的节点
    52. 				else
    53. 				{
    54. 					BSTNode*minparent = cur;
    55. 					BSTNode* minright = cur->right;
    56. 					while (minright->left)
    57. 					{
    58. 						minparent = minright;
    59. 						minright = minright->left;
    60. 					}
    61. 					swap(minright->_key, cur->_key);
    62. 					if (minparent->left = minright)
    63. 					{
    64. 						minparent->left = minright->right;
    65. 					}
    66. 					else
    67. 					{
    68. 						minparent->right = minright->right;
    69. 					}
    70. 					delete minright;
    71. 				}
    72. 			}
    73. 			return true;
    74. 		}
    75. 		return false;
    76.  
    77. 	}

    ⭐2.7二叉搜索树的删除（递归）

    1. bool _EraseR(BSTNode*& root, const K& key)//传引用
    2. 	{
    3. 		if (!root)return false;
    4. 		if (root->_key == key)
    5. 		{
    6. 			BSTNode* del = root;
    7. 			// 删除
    8. 			if (root->left == nullptr)
    9. 			{
    10. 				root = root->right;
    11. 			}
    12. 			else if (root->right == nullptr)
    13. 			{
    14. 				root = root->left;
    15. 			}
    16. 			else
    17. 			{
    18. 				BSTNode* minRight = root->right;
    19. 				while (minRight->left)
    20. 				{
    21. 					minRight = minRight->left;
    22. 				}
    23.  
    24. 				swap(root->_key, minRight->_key);
    25.                 //交换完以后继续递归删除
    26. 				return _EraseR(root->right, key);
    27. 			}
    28.  
    29. 			delete del;
    30. 			return true;
    31. 		}
    32. 		else if (root->_key > key)
    33. 			return _EraseR(root->left, key);
    34. 		else
    35. 			return _EraseR(root->right, key);
    36. 	}

    ⭐2.8二叉搜索树的遍历

    当创建好二叉搜索树后，我们需要知道自己的相关操作对不对，所以需要遍历二叉搜索树来验证，

    那什么遍历方式好呢？这里选的是中序遍历，因为二叉搜索树左边都是小于根节点的，右边都是大于根节点的，所以使用中序遍历可以得到一个呈升序的序列

    1. void _Inorder(BSTNode* root)
    2. 	{
    3. 		if (!root)return;
    4. 		_Inorder(root->left);
    5. 		cout << root->_key << ' ';
    6. 		_Inorder(root->right);
    7. 	}

    ⭐2.9二叉树的拷贝构造及构造，赋值重载

    1. //C++11支持的编译器强制生成默认构造函数
    2. 	//BST() = default;
    3. 	BST()//构造
    4. 	{}
    5. 	
    6. 	BSTNode* CopyTree( BSTNode* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 			return nullptr;
    10.  
    11. 		BSTNode* copyNode = new BSTNode(root->_key);
    12. 		copyNode->_left = CopyTree(root->_left);
    13. 		copyNode->_right = CopyTree(root->_right);
    14.  
    15. 		return copyNode;
    16. 	}
    17. 	BST(const BST& bst)//拷贝构造
    18. 	{
    19. 		_root = CopyTree(bst);
    20. 	}
    21. 	
    22. 	BST& operator=(const BST bst)//赋值重载
    23. 	{
    24. 		swap(_root, bst._root);
    25. 		return *this;
    26. 	}

    ⭐三、二叉搜索树的全部代码

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5. template <class K>
    6. struct BSTNode
    7. {
    8. 	BSTNode* left;
    9. 	BSTNode* right;
    10. 	K _key;
    11. 	BSTNode(K key)
    12. 		:left(nullptr)
    13. 		, right(nullptr)
    14. 		, _key(key)
    15. 	{}
    16. };
    17.  
    18. template <class K>
    19. class BST
    20. {
    21. public:
    22. 	//C++11支持的编译器强制生成默认构造函数
    23. 	//BST() = default;
    24. 	BST()
    25. 	{}
    26. 	
    27. 	BSTNode* CopyTree( BSTNode* root)
    28. 	{
    29. 		if (root == nullptr)
    30. 			return nullptr;
    31.  
    32. 		BSTNode* copyNode = new BSTNode(root->_key);
    33. 		copyNode->_left = CopyTree(root->_left);
    34. 		copyNode->_right = CopyTree(root->_right);
    35.  
    36. 		return copyNode;
    37. 	}
    38. 	BST(const BST& bst)
    39. 	{
    40. 		_root = CopyTree(bst);
    41. 	}
    42. 	
    43. 	BST& operator=(const BST bst)
    44. 	{
    45. 		swap(_root, bst._root);
    46. 		return *this;
    47. 	}
    48.  
    49. 	bool find(const K& key)
    50. 	{
    51. 		BSTNode* cur = _root;
    52. 		while (cur)
    53. 		{
    54. 			if (cur->_key == key)
    55. 				return true;
    56. 			else if (cur->_key < key)
    57. 				cur = cur->right;
    58. 			else
    59. 				cur = cur->left;
    60. 		}
    61. 		return false;
    62. 	}
    63.  
    64.  
    65. 	bool insert(const K& key)
    66. 	{
    67. 		if (_root == nullptr)
    68. 		{
    69. 			_root= new BSTNode(key);
    70. 			return true;
    71. 		}
    72. 		BSTNode* cur = _root, *parent=nullptr;
    73. 		while (cur)
    74. 		{
    75. 			if (_root->_key < key)
    76. 			{
    77. 				parent = cur;
    78. 				cur = cur->right;
    79. 			}
    80. 			else if (_root->_key > key)
    81. 			{
    82. 				parent = cur;
    83. 				cur = cur->left;
    84. 			}
    85. 			else
    86. 				return false;
    87. 		}
    88. 		BSTNode* newnode = new BSTNode(key);
    89. 		if (parent->_key < key)
    90. 		{
    91. 			parent->right = newnode;
    92. 		}
    93. 		else
    94. 			parent->left = newnode;
    95. 		return true;
    96. 	}
    97.  
    98.  
    99. 	bool Erase(const K& key)
    100. 	{
    101. 		BSTNode* cur = _root, * parent =nullptr;
    102. 		while (cur)
    103. 		{
    104. 			if (cur->_key < key)
    105. 			{
    106. 				parent = cur;
    107. 				cur = cur->right;
    108. 			}
    109. 			else if (cur->_key > key)
    110. 			{
    111. 				parent = cur;
    112. 				cur = cur->left;
    113. 			}
    114. 			else
    115. 			{
    116. 				if (cur->left == nullptr)
    117. 				{
    118. 					if (parent == nullptr)
    119. 					{
    120. 						_root = _root->right;
    121. 					}
    122. 					else if (parent->left == cur)
    123. 					{
    124. 						parent->left = cur->right;
    125. 					}
    126. 					else
    127. 					{
    128. 						parent->right = cur->right;
    129. 					}
    130. 					delete cur;
    131. 				}
    132. 				else if (cur->right == nullptr)
    133. 				{
    134. 					if (parent == nullptr)
    135. 					{
    136. 						_root = _root->right;
    137. 					}
    138. 					else if (parent->left == cur)
    139. 					{
    140. 						parent->left = cur->left;
    141. 					}
    142. 					else
    143. 					{
    144. 						parent->right = cur->left;
    145. 					}
    146. 					delete cur;
    147. 				}
    148. 				else
    149. 				{
    150. 					BSTNode*minparent = cur;
    151. 					BSTNode* minright = cur->right;
    152. 					while (minright->left)
    153. 					{
    154. 						minparent = minright;
    155. 						minright = minright->left;
    156. 					}
    157. 					swap(minright->_key, cur->_key);
    158. 					if (minparent->left = minright)
    159. 					{
    160. 						minparent->left = minright->right;
    161. 					}
    162. 					else
    163. 					{
    164. 						minparent->right = minright->right;
    165. 					}
    166. 					delete minright;
    167. 				}
    168. 			}
    169. 			return true;
    170. 		}
    171. 		return false;
    172.  
    173. 	}
    174.  
    175. 	void Inorder()
    176. 	{
    177. 		_Inorder(_root);
    178. 		cout << endl;
    179. 	}
    180. 	bool findR(const K& key)
    181. 	{
    182. 		return _findR(_root, key);
    183. 	
    184. 	}
    185.  
    186. 	bool InsertR(const K& key)
    187. 	{
    188. 		return _InsertR(_root, key);	
    189. 	}
    190. 	bool EraseR(const K& key)
    191. 	{
    192. 		return _EraseR(_root, key);
    193. 	}
    194.  
    195. private:
    196. 	void _Inorder(BSTNode* root)
    197. 	{
    198. 		if (!root)return;
    199. 		_Inorder(root->left);
    200. 		cout << root->_key << ' ';
    201. 		_Inorder(root->right);
    202. 	}
    203. 	bool _findR(BSTNode* root, const K& key)
    204. 	{
    205. 		if (!root)return false;
    206. 		if (root->_key == key)
    207. 			return true;
    208. 		else if (root->_key > key)
    209. 			return _findR(root->left, key);
    210. 		else
    211. 			return _findR(root->right, key);
    212. 	}
    213.  
    214. 	bool _InsertR(BSTNode*& root, const K& key)
    215. 	{
    216. 		if (!root)
    217. 			BSTNode* root = new BSTNode(key);
    218. 		if (root->_key > key)
    219. 		{
    220. 			return _InsertR(root->left, key);
    221. 		}
    222. 		else if (root->_key < key)
    223. 		{
    224. 			return _InsertR(root->right, key);
    225. 		}
    226. 		else
    227. 			return false;
    228.  
    229. 	}
    230.  
    231. 	bool _EraseR(BSTNode*& root, const K& key)
    232. 	{
    233. 		if (!root)return false;
    234. 		if (root->_key == key)
    235. 		{
    236. 			BSTNode* del = root;
    237. 			// 删除
    238. 			if (root->left == nullptr)
    239. 			{
    240. 				root = root->right;
    241. 			}
    242. 			else if (root->right == nullptr)
    243. 			{
    244. 				root = root->left;
    245. 			}
    246. 			else
    247. 			{
    248. 				BSTNode* minRight = root->right;
    249. 				while (minRight->left)
    250. 				{
    251. 					minRight = minRight->left;
    252. 				}
    253.  
    254. 				swap(root->_key, minRight->_key);
    255.  
    256. 				return _EraseR(root->right, key);
    257. 			}
    258.  
    259. 			delete del;
    260. 			return true;
    261. 		}
    262. 		else if (root->_key > key)
    263. 			return _EraseR(root->left, key);
    264. 		else
    265. 			return _EraseR(root->right, key);
    266. 	}
    267.  
    268. 	BSTNode* _root = nullptr;
    269. };

    二叉搜索树的知识就分享到这里了，有什么错误还望指出。

  • 相关阅读:
    水果店圈子：水果店水果都去哪进货，水果店进货怎么找货源
    Docker_基础知识
    c++ 学习 之 继承中静态成员函数和静态成员变量
    基于51单片机交通灯仿真_紧急开关+黄灯倒计时+可调时间（proteus+代码+报告+讲解视频）
    DFS 无向图欧拉路径
    基于stm32单片机的输入捕获测量脉宽Proteus仿真
    【MySQL】 Java的JDBC编程
    【历史上的今天】7 月 30 日：现代电视先驱诞生；以太坊启动；80 年代最畅销的电脑品牌
    CV+Deep Learning——网络架构Pytorch复现系列——classification(三：MobileNet，ShuffleNet)
    【Hello Linux】多路转接之 epoll
  • 原文地址：https://blog.csdn.net/m0_72532428/article/details/130694757