当前位置:   article > 正文

数据结构-二叉搜索树_二叉搜索树怎么构造

二叉搜索树怎么构造

目录

二叉搜索树的概念及结构

概念

结构

二叉搜索树的基本操作

默认成员函数

默认构造函数与拷贝构造函数

赋值重载

析构函数

二叉搜索树的插入

非递归

递归

二叉搜索树的遍历

中序遍历---升序(左根右)

中序遍历---降序(右根左)

二叉搜索树的删除

非递归

递归

二叉搜索树的查找

非递归

递归

代码


二叉搜索树的概念及结构

概念

   二叉搜索树也称二叉排序树或者二叉查找树,它是在普通二叉树上加入一些特性所形成的:

  • 1,若左子树非空,则左子树上所有结点的值均小于根结点的值。
  • 2,若右子树非空,则右子树上所有结点的值均大于根结点的值。
  • 3,其左右子树也分别是一棵二叉搜索树。

   由二叉搜索树的概念可知,左子树结点值 < 根结点值 < 右子树结点值;所有当二叉搜索树进行中序遍历也就是左根右遍历时,可以得到升序的结果;如果是右根左遍历,就可以得到降序的结果。

结构

   二叉搜索树的物理结构更适合采用链式结构,_left存储比根结点值小的结点地址,_right存储比根结点值大的结点地址。

二叉搜索树的基本操作

   对于二叉搜索树的基本操作,我们选择把它的基本操作与其根结点地址封装到一个类中。

默认成员函数

   二叉搜索树的默认成员函数都需要自己来实现,因为构造与析构涉及到开辟空间与释放空间的操作,而拷贝构造与赋值操作涉及到深拷贝的问题。

默认构造函数与拷贝构造函数

   默认构造函数只需要实现一个无参的构造函数就可以,其作用就是将_root置空。

  1. // 构造
  2. BSTree()
  3. :_root(nullptr)
  4. {}

   而拷贝构造函数需要进行深拷贝,就是将被拷贝的二叉搜索树每个结点值拷贝到新开辟结点中,并将新开辟的结点连接成与被拷贝的二叉搜索树结构一样。该拷贝构造过程需要使用到前序遍历的思想,因为先要有双亲结点,才能有左右孩子结点。

  1. // 拷贝构造
  2. BSTree(const BSTree& b)
  3. :_root(_CopyBSTree(b._root))
  4. {
  5. }

赋值重载

   赋值重载需要利用到拷贝构造,也就是让被拷贝的二叉搜索树拷贝构造一棵新的二叉搜索树,再让这课新树与需要赋值的树进行交换,即完成赋值。

  1. // 赋值重载
  2. BSTree<K>& operator=(BSTree<K> b)
  3. {
  4. swap(_root, b._root);
  5. return *this;
  6. }

析构函数

   析构函数的实现就是通过后序遍历,将二叉搜索树中每一个结点依次释放即可。

  1. // 析构
  2. ~BSTree()
  3. {
  4. _DestroyBSTree(_root);
  5. _root = nullptr;
  6. }

二叉搜索树的插入

   若原二叉搜索树为空树,则直接将新结点插入到根;否则,根据根结点的值进行判断插入,若插入的值小于根,则插入到左子树中,若插入的值大于根,则插入到右子树中。

   需要注意的是,若插入的值在原二叉搜索树中已经存在了,则插入失败;而且插入的这个新结点一定是叶子结点。

非递归

递归

  1. // 插入---递归
  2. bool InsertR(const K& key)
  3. {
  4. return _InsertR(_root, key);
  5. }

二叉搜索树的遍历

   二叉搜索树的中序遍历是最有意义的。

中序遍历---升序(左根右)

  1. void _InOrder(Node* root)
  2. {
  3. if (root == nullptr)
  4. {
  5. return;
  6. }
  7. _InOrder(root->_left);
  8. cout << root->_key << " ";
  9. _InOrder(root->_right);
  10. }
  11. // 中序遍历---升序
  12. void InOrder()
  13. {
  14. _InOrder(_root);
  15. cout << endl;
  16. }

中序遍历---降序(右根左)

  1. void _InOrderReverse(Node* root)
  2. {
  3. if (root == nullptr)
  4. {
  5. return;
  6. }
  7. _InOrderReverse(root->_right);
  8. cout << root->_key << " ";
  9. _InOrderReverse(root->_left);
  10. }
  11. // 中序遍历---降序
  12. void InOrderReverse()
  13. {
  14. _InOrderReverse(_root);
  15. cout << endl;
  16. }

二叉搜索树的删除

   删除分为三种情况:

1,若删除的是11,14,17,20这样的叶子结点,可以直接删除,并将其双亲结点指向自己的指针置空。

2,若删除的是19,20这样有一个孩子的结点,则可以将自己的孩子给其双亲托管,再删除自己。

3,若删除的是18,13.16这样有两个孩子的结点,可以使用替换删除法:去要删除结点的左右子树中找到可以顶替自己的结点,也就是在其左子树中找最大的结点或者在其右子树中找最小结点。找到之后保存该结点(该结点的特征与1或者2一样)的值,并删除该结点,最后将保存的值给要删除的结点。

非递归

递归

  1. // 删除---递归
  2. bool EraseR(const K& key)
  3. {
  4. return _EraseR(_root, key);
  5. }

二叉搜索树的查找

   二叉搜索树的查找就是从根结点开始,沿着某个分支逐层向下比较的过程。先将要查找的值与根结点值比较,如果相等则查找成功;如果不相等,若查找的值小于根结点值,则在根结点的左子树上查找,否则在根结点的右子树上查找;没有找到则返回nullptr。

非递归

递归

  1. // 查找---递归
  2. Node* FindR(const K& key)
  3. {
  4. return _FindR(_root, key);
  5. }

   二叉搜索树的插入删除查找的时间复杂度为O(n),因为二叉搜索树不能保证自身的结构不是一棵单支树,所以二叉搜索树需要进行优化成AVL树和红黑树。

代码

  1. #pragma once
  2. #include <iostream>
  3. #include <cstdbool>
  4. using namespace std;
  5. template <class K>
  6. struct BSTreeNode
  7. {
  8. struct BSTreeNode<K>* _left;
  9. struct BSTreeNode<K>* _right;
  10. K _key;
  11. BSTreeNode(const K& key=K())
  12. :_left(nullptr)
  13. ,_right(nullptr)
  14. ,_key(key)
  15. {
  16. }
  17. };
  18. template <class K>
  19. class BSTree
  20. {
  21. typedef struct BSTreeNode<K> Node;
  22. private:
  23. Node* _root;
  24. void _InOrder(Node* root)
  25. {
  26. if (root == nullptr)
  27. {
  28. return;
  29. }
  30. _InOrder(root->_left);
  31. cout << root->_key << " ";
  32. _InOrder(root->_right);
  33. }
  34. void _InOrderReverse(Node* root)
  35. {
  36. if (root == nullptr)
  37. {
  38. return;
  39. }
  40. _InOrderReverse(root->_right);
  41. cout << root->_key << " ";
  42. _InOrderReverse(root->_left);
  43. }
  44. bool _InsertR(Node* &root,const K& key)
  45. {
  46. if (root == nullptr)
  47. {
  48. root = new Node(key);
  49. return true;
  50. }
  51. if (root->_key < key)
  52. {
  53. return _InsertR(root->_right, key);
  54. }
  55. else if(root->_key>key)
  56. {
  57. return _InsertR(root->_left, key);
  58. }
  59. else
  60. {
  61. return false;
  62. }
  63. }
  64. Node* _FindR(Node* root, const K& key)
  65. {
  66. if (root == nullptr) // 查找失败
  67. {
  68. return nullptr;
  69. }
  70. if (root->_key < key) // 大于根结点值,往根结点的右子树上查找
  71. {
  72. return _FindR(root->_right, key);
  73. }
  74. else if(root->_key>key) // 小于根结点值,往根结点的左子树上查找
  75. {
  76. return _FindR(root->_left, key);
  77. }
  78. else // 查找成功
  79. {
  80. return root; // 查找成功
  81. }
  82. }
  83. bool _EraseR(Node*& root, const K& key)
  84. {
  85. if (root == nullptr)
  86. {
  87. return false;
  88. }
  89. if (root->_key < key)
  90. {
  91. return _EraseR(root->_right, key);
  92. }
  93. else if (root->_key > key)
  94. {
  95. return _EraseR(root->_left, key);
  96. }
  97. else // 找到了要删除的结点
  98. {
  99. if (root->_left == nullptr)
  100. {
  101. Node* del = root;
  102. root = root->_right;
  103. delete del;
  104. return true;
  105. }
  106. else if(root->_right==nullptr)
  107. {
  108. Node* del = root;
  109. root = root->_left;
  110. delete del;
  111. return true;
  112. }
  113. else
  114. {
  115. Node* min = root->_right;
  116. while (min->_left)
  117. {
  118. min = min->_left;
  119. }
  120. K tmp = min->_key;
  121. _EraseR(root, tmp);
  122. root->_key = tmp;
  123. return true;
  124. }
  125. }
  126. }
  127. Node* _CopyBSTree(Node* root)
  128. {
  129. if (root == nullptr)
  130. {
  131. return nullptr;
  132. }
  133. Node* newNode = new Node(root->_key);
  134. newNode->_left = _CopyBSTree(root->_left);
  135. newNode->_right = _CopyBSTree(root->_right);
  136. return newNode;
  137. }
  138. void _DestroyBSTree(Node* root)
  139. {
  140. if (root == nullptr)
  141. {
  142. return;
  143. }
  144. _DestroyBSTree(root->_left);
  145. _DestroyBSTree(root->_right);
  146. delete root;
  147. }
  148. public:
  149. // 构造
  150. BSTree()
  151. :_root(nullptr)
  152. {}
  153. // 拷贝构造
  154. BSTree(const BSTree& b)
  155. :_root(_CopyBSTree(b._root))
  156. {
  157. }
  158. // 赋值重载
  159. BSTree<K>& operator=(BSTree<K> b)
  160. {
  161. swap(_root, b._root);
  162. return *this;
  163. }
  164. // 析构
  165. ~BSTree()
  166. {
  167. _DestroyBSTree(_root);
  168. _root = nullptr;
  169. }
  170. // 插入
  171. bool Insert(const K& key) //二叉搜索树的插入与单链表的尾插相似,分两种情况
  172. {
  173. if (_root == nullptr) // 当二叉搜索树为空树时,直接将插入的结点当成根结点
  174. {
  175. _root = new Node(key);
  176. return true;
  177. }
  178. Node* prev = nullptr;
  179. Node* curr = _root;
  180. while (curr) // 当二叉搜索树不为空树时,需要寻找满足二叉搜索树特性的位置,并找到满足位置的双亲结点的位置
  181. {
  182. if (curr->_key < key) // 当key大于双亲结点的_key往右走
  183. {
  184. prev = curr;
  185. curr = curr->_right;
  186. }
  187. else if(curr->_key>key) // 当key小于双亲结点的_key往左走
  188. {
  189. prev = curr;
  190. curr = curr->_left;
  191. }
  192. else // 如果相等插入失败
  193. {
  194. return false;
  195. }
  196. }
  197. if (prev->_key < key) // prev为插入位置的双亲结点位置,保证插入的结点成功链接到二叉搜索树中
  198. {
  199. prev->_right = new Node(key);
  200. }
  201. else
  202. {
  203. prev->_left = new Node(key);
  204. }
  205. return true;
  206. }
  207. // 中序遍历---升序
  208. void InOrder()
  209. {
  210. _InOrder(_root);
  211. cout << endl;
  212. }
  213. // 中序遍历---降序
  214. void InOrderReverse()
  215. {
  216. _InOrderReverse(_root);
  217. cout << endl;
  218. }
  219. // 查找
  220. Node* Find(const K& key) // 二叉搜索树的查找与单链表的查找相似
  221. {
  222. Node* curr = _root;
  223. while (curr)
  224. {
  225. if (curr->_key < key)
  226. {
  227. curr = curr->_right;
  228. }
  229. else if (curr->_key > key)
  230. {
  231. curr = curr->_left;
  232. }
  233. else
  234. {
  235. return curr;
  236. }
  237. }
  238. return nullptr; // return curr; 也行
  239. }
  240. // 删除
  241. bool Erase(const K&key)
  242. {
  243. Node* prev = nullptr;
  244. Node* curr = _root;
  245. while (curr) // 寻找值为key的结点,prev为该结点的双亲结点
  246. {
  247. if (curr->_key < key) // 如果key大于当前结点的_key,则往右走
  248. {
  249. prev = curr;
  250. curr = curr->_right;
  251. }
  252. else if(curr->_key>key) // 如果key小于当前结点的_key,则往左走
  253. {
  254. prev = curr;
  255. curr = curr->_left;
  256. }
  257. else // 找到_key为key的结点---该结点分为三类:1,没有左右孩子结点 2,有一个孩子结点 3,左右孩子结点都
  258. {
  259. if (curr->_left == nullptr) // 如果该结点没有左孩子结点,则需要将该结点的右结点给其双亲结点
  260. {
  261. if (curr == _root) // 如果删除的是根结点,则将_root改为其右子树
  262. {
  263. _root = curr->_right;
  264. }
  265. else
  266. {
  267. if (prev->_left == curr) // 判断删除的结点是双亲的左孩子还是右孩子
  268. {
  269. prev->_left = curr->_right;
  270. }
  271. else
  272. {
  273. prev->_right = curr->_right;
  274. }
  275. }
  276. delete curr;
  277. return true;
  278. }
  279. else if (curr->_right == nullptr) // 如果该结点没有右孩子结点,则需要将该结点的左结点给其双亲结点
  280. {
  281. if (curr == _root) // 如果删除的是根结点,则将_root改为其左子树
  282. {
  283. _root = curr->_left;
  284. }
  285. else
  286. {
  287. if (prev->_left == curr)// 判断删除的结点是双亲的左孩子还是右孩子
  288. {
  289. prev->_left = curr->_left;
  290. }
  291. else
  292. {
  293. prev->_right = curr->_left;
  294. }
  295. }
  296. delete curr;
  297. return true;
  298. }
  299. else // 如果删除的结点左右孩子都有,则进行替换删除
  300. {
  301. /*Node* minPrev = curr;
  302. Node* min = curr->_right; // 寻找删除结点的右子树中最小结点
  303. while (min->_left)
  304. {
  305. minPrev = min;
  306. min = min->_left;
  307. }
  308. if (minPrev == curr) // 避免最小结点是删除结点的右孩子结点
  309. {
  310. minPrev->_right = min->_right;
  311. }
  312. else
  313. {
  314. minPrev->_left = min->_right;
  315. }
  316. curr->_key = min->_key;
  317. delete min;*/
  318. Node* min = curr->_right; // 选出右子树最小的结点
  319. while (min->_left)
  320. {
  321. min = min->_left;
  322. }
  323. K tmp = min->_key; // 保存右子树最小结点的值
  324. Erase(tmp); // 将tmp值的结点删除
  325. _root->_key = tmp; // 再将tmp的值赋给有两个孩子的结点,想当将这个结点删除
  326. return true;
  327. }
  328. }
  329. }
  330. return false; // 没有找到删除的结点,则说明删除失败,返回false
  331. }
  332. // 插入---递归
  333. bool InsertR(const K& key)
  334. {
  335. return _InsertR(_root, key);
  336. }
  337. // 查找---递归
  338. Node* FindR(const K& key)
  339. {
  340. return _FindR(_root, key);
  341. }
  342. // 删除---递归
  343. bool EraseR(const K& key)
  344. {
  345. return _EraseR(_root, key);
  346. }
  347. };
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/948650
推荐阅读
相关标签
  

闽ICP备14008679号