C++（进阶) 第3章 二叉搜索树

C++（进阶) 第3章 二叉搜索树

---

  

---

前言

之前在数据布局篇简朴的介绍了二叉搜索树，本篇博客会具体的介绍

---

一、什么是二叉搜索树？

⼆叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
• 若它的左⼦树不为空，则左⼦树上全部结点的值都⼩于等于根结点的值
• 若它的右⼦树不为空，则右⼦树上全部结点的值都⼤于等于根结点的值
• 它的左右⼦树也分别为⼆叉搜索树

下面就是一颗比力经典的二叉搜索树

搜索二叉树也叫排序二叉树，由于它走中序遍历的时候刚好就是有序的

---

二、搜索二叉树的实现

0.搜索二叉树的时间复杂度

搜索二叉树的做好环境下时间复杂度就是log N，但是会出现极端环境

以是时间复杂度就是N
但是后面会有AVL树，红黑树，可以优化差不多 log N

---

1.根本框架

1. #include<bits/stdc++.h>
2. using namespace std;
3. template<class K>
5. struct BSTreeNode
6. {
7.         K _key;
8.         BSTreeNode<K>* _left;
9.         BSTreeNode<K>* _right;
10.         BSTreeNode(const K& key)
11.                 :_key(key)
12.                 ,_left(nullptr)
13.                 ,_right(nullptr)
14.         {
16.         }
17. };
18. template<class K>
19. class BSTree
20. {
21.         typedef BSTreeNode<K> Node;
22. public:
23. private:
24.         Node* _root = nullptr;
25. };

复制代码

---

2.Find

普通的二叉树其实没有什么意义，如果只是普通的二叉树它存东西的效率其实还不如链表，以是在原来的二叉树基础上添加了一些规则，左孩子比根小，右孩子比根大
如果就用下面的例子，现在我要在这颗树里面搜索看看有没有16这个数字

如果我们查找的值比根大那么就可以直接往右走，比根小只必要往左走就可以了那么最多只必要找这棵树的高度次就可以了
如果找到null了那么就阐明找不到

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

复制代码

---

3.Insert

注意：这里有一个规定，树里面的数据是不允许重复的,也，如果树里面已经有了10，那么这里就不允许再次插入，以是这里insert返回值用bool

1. bool Insert(const K& key)
2. {
3.         if (_root == nullptr)
4.         {
5.                 _root = new Node(key);
6.                 return true;
7.         }
8.         Node* cur = _root;
9.         Node* parent = nullptr;
10.         while (cur)
11.         {
12.                 if (cur->_key < key)
13.                 {
14.                         parent = cur;
15.                         cur = cur->_right;
16.                        
17.                 }
18.                 else if (cur->_key > key)
19.                 {
20.                         parent = cur;
21.                         cur = cur->_left;
22.                        
23.                 }
24.                 else
25.                 {
26.                         return false;
27.                 }
28.         }
30.         cur = new Node(key);
31.         if (parent->_key < cur->_key)
32.         {
33.                 parent->_right = cur;
34.         }
35.         else
36.         {
37.                 parent->_left= cur;
39.         }
40.         return true;
43. }

复制代码

---

4.InOder

这里我用的是子函数的情势由于如果不这样的话，外面调用就要传入参数（_root）但是这里我_root是保护调用不了，

1.         void InOder()
2.         {
3.                 _InOder(_root);
4.         }
5. private:
6.         void _InOder(Node* root)
7.         {
8.                 if (root == nullptr)
9.                 {
10.                         return;
11.                 }
13.                 _InOder(root->_left);
14.                 cout << root->_key << ' ';
15.                 _InOder(root->_right);
17.         }

复制代码

---

写完中序遍历就可以看下程序有没有写错了

这里可以看到输出的是有序的，就阐明这里是没有写错的
到这里的完备代码就长这样

1. #pragma once#include<bits/stdc++.h>using namespace std;template<class K>struct BSTreeNode{        K _key;        BSTreeNode<K>* _left;        BSTreeNode<K>* _right;        BSTreeNode(const K& key)                :_key(key)                ,_left(nullptr)                ,_right(nullptr)        {        }};template<class K>class BSTree{        typedef BSTreeNode<K> Node;public:        bool Find(const K& key)        {                Node* cur = _root;                while (cur)                {                        if (cur->_key < key)                        {                                cur = cur->_right;                        }                        else if(cur->_key > key)                        {                                cur = cur->_left;                        }                        else                        {                                return true;                        }                }                return false;        }        bool Insert(const K& key)        {                if (_root == nullptr)                {                        _root = new Node(key);                        return true;                }                Node* cur = _root;                Node* parent = nullptr;                while (cur)                {                        if (cur->_key < key)                        {                                parent = cur;                                cur = cur->_right;                                                        }                        else if (cur->_key > key)                        {                                parent = cur;                                cur = cur->_left;                                                        }                        else                        {                                return false;                        }                }                cur = new Node(key);                if (parent->_key < cur->_key)                {                        parent->_right = cur;                }                else                {                        parent->_left= cur;                }                return true;        }        void InOder(Node* root)        {                if (root == nullptr)                {                        return;                }                InOder(root->_left);                cout << root->_key << ' ';                InOder(root->_right);        }        void InOder()
2.         {
3.                 _InOder(_root);
4.         }
5. private:
6.         void _InOder(Node* root)
7.         {
8.                 if (root == nullptr)
9.                 {
10.                         return;
11.                 }
13.                 _InOder(root->_left);
14.                 cout << root->_key << ' ';
15.                 _InOder(root->_right);
17.         }
18. private:        Node* _root = nullptr;};

复制代码

1. #define _CRT_SECURE_NO_WARNINGS
2. #include"bstree.h"
4. int main()
5. {
6.     int arr[] = { 8,3,1,10,6,4,7,14,13 };
7.     BSTree<int> t;
8.     for (auto e : arr)
9.     {
10.         t.Insert(e);
11.     }
12.     t.InOder();
14.     return 0;
15. }

复制代码

---

5.Erase

这里删除的话就比力复杂了，必要先找到要删的谁人节点，然后删除，但是删除的谁人节点大概会还有孩子并且删除了以后搜索二叉树不能乱，大致可以分成以下三种环境

• 没有孩子
  
• 只要一个孩子
  
• 有俩个孩子
  

如果这里我要删除3，那么我必要找到一个人替换3的位置，这个时候左子树最右边的节点，或者右子树最左边的节点都可以，以是上面的1，2种环境可以归类成一种环境，由于最左边或者最左边的一定是只有一个孩子或者没有孩子的环境
如果上面我要删掉3，那么我去找右子树的最左边的值也就是4，那么3替换成4，然后下面的4就可以直接删掉了

1. bool Erase(const K& key)
2. {
3.         Node* cur = _root;
4.         Node* parent = nullptr;
5.         while (cur)
6.         {
7.                 if (cur->_key < key)
8.                 {
9.                         parent = cur;
10.                         cur = cur->_right;
11.                 }
12.                 else if (cur->_key > key)
13.                 {
14.                         parent = cur;
16.                         cur = cur->_left;
17.                 }
18.                 else
19.                 {
20.                         if (cur->_left == nullptr)
21.                         {
22.                                 if (parent == nullptr)
23.                                 {
24.                                         _root = cur->_right;
25.                                 }
26.                                 else
27.                                 {
28.                                         if (parent->_left == cur)
29.                                         {
30.                                                 parent->_left = cur->_right;
31.                                         }
32.                                         else
33.                                         {
34.                                                 parent->_right = cur->_right;
35.                                         }
36.                                 }
37.                                
38.                                 delete cur;
39.                                 return true;
40.                         }
41.                         else if(cur->_right == nullptr)
42.                         {
43.                                 if (parent == nullptr)
44.                                 {
45.                                         _root = cur->_left;
46.                                 }
47.                                 else
48.                                 {
49.                                         if (parent->_left == cur)
50.                                         {
51.                                                 parent->_left = cur->_left;
52.                                         }
53.                                         else
54.                                         {
55.                                                 parent->_right = cur->_left;
56.                                         }
57.                                 }
58.                                
59.                                 delete cur;
60.                                 return true;
61.                         }
62.                         else
63.                         {
64.                                 Node* RightMin = cur->_right;
65.                                 Node* RightMinP = cur;
66.                                 while (RightMin ->_left)
67.                                 {
68.                                         RightMinP = RightMin;
69.                                         RightMin = RightMin->_left;
70.                                 }
72.                                 cur->_key = RightMin->_key;
73.                                 if (RightMinP->_left == RightMin )
74.                                 {
75.                                         RightMinP->_left = RightMin->_right;
76.                                 }
77.                                 else
78.                                 {
79.                                         RightMinP->_right = RightMin->_right;
80.                                 }
81.                                
82.                                 delete RightMin;
83.                                 return true;
84.                         }
85.                 }
86.         }
87.         return false;
88. }

复制代码

---

三 、完备代码

1. #pragma once
2. #include<bits/stdc++.h>
3. using namespace std;
5. template<class K>
6. struct BSTreeNode
7. {
8.         K _key;
9.         BSTreeNode<K>* _left;
10.         BSTreeNode<K>* _right;
11.         BSTreeNode(const K& key)
12.                 :_key(key)
13.                 ,_left(nullptr)
14.                 ,_right(nullptr)
15.         {
17.         }
19. };
23. template<class K>
24. class BSTree
25. {
26.         typedef BSTreeNode<K> Node;
28. public:
29.         bool Find(const K& key)
30.         {
31.                 Node* cur = _root;
32.                 while (cur)
33.                 {
34.                         if (cur->_key < key)
35.                         {
36.                                 cur = cur->_right;
37.                         }
38.                         else if (cur->_key > key)
39.                         {
40.                                 cur = cur->_left;
41.                         }
42.                         else
43.                         {
44.                                 return true;
45.                         }
46.                 }
47.                 return false;
48.         }
49.         bool Insert(const K& key)
50.         {
51.                 if (_root == nullptr)
52.                 {
53.                         _root = new Node(key);
54.                         return true;
55.                 }
56.                 Node* cur = _root;
57.                 Node* parent = nullptr;
58.                 while (cur)
59.                 {
60.                         if (cur->_key < key)
61.                         {
62.                                 parent = cur;
63.                                 cur = cur->_right;
64.                         }
65.                         else if (cur->_key > key)
66.                         {
67.                                 parent = cur;
68.                                 cur = cur->_left;
69.                         }
70.                         else
71.                         {
72.                                 return false;
73.                         }
74.                 }
75.                 cur = new Node(key);
76.                 if (parent->_key < cur->_key)
77.                 {
78.                         parent->_right = cur;
79.                 }
80.                 else
81.                 {
82.                         parent->_left = cur;
83.                 }
84.                 return true;
86.         }
87.         void InOrder()
88.         {
89.                 _InOrder(_root);
90.                 cout << endl;
91.         }
93.         bool Erase(const K& key)
94.         {
95.                 Node* cur = _root;
96.                 Node* parent = nullptr;
97.                 while (cur)
98.                 {
99.                         if (cur->_key < key)
100.                         {
101.                                 parent = cur;
102.                                 cur = cur->_right;
103.                         }
104.                         else if (cur->_key > key)
105.                         {
106.                                 parent = cur;
108.                                 cur = cur->_left;
109.                         }
110.                         else
111.                         {
112.                                 if (cur->_left == nullptr)
113.                                 {
114.                                         if (parent == nullptr)
115.                                         {
116.                                                 _root = cur->_right;
117.                                         }
118.                                         else
119.                                         {
120.                                                 if (parent->_left == cur)
121.                                                 {
122.                                                         parent->_left = cur->_right;
123.                                                 }
124.                                                 else
125.                                                 {
126.                                                         parent->_right = cur->_right;
127.                                                 }
128.                                         }
129.                                        
130.                                         delete cur;
131.                                         return true;
132.                                 }
133.                                 else if(cur->_right == nullptr)
134.                                 {
135.                                         if (parent == nullptr)
136.                                         {
137.                                                 _root = cur->_left;
138.                                         }
139.                                         else
140.                                         {
141.                                                 if (parent->_left == cur)
142.                                                 {
143.                                                         parent->_left = cur->_left;
144.                                                 }
145.                                                 else
146.                                                 {
147.                                                         parent->_right = cur->_left;
148.                                                 }
149.                                         }
150.                                        
151.                                         delete cur;
152.                                         return true;
153.                                 }
154.                                 else
155.                                 {
156.                                         Node* RightMin = cur->_right;
157.                                         Node* RightMinP = cur;
158.                                         while (RightMin ->_left)
159.                                         {
160.                                                 RightMinP = RightMin;
161.                                                 RightMin = RightMin->_left;
162.                                         }
164.                                         cur->_key = RightMin->_key;
165.                                         if (RightMinP->_left == RightMin )
166.                                         {
167.                                                 RightMinP->_left = RightMin->_right;
168.                                         }
169.                                         else
170.                                         {
171.                                                 RightMinP->_right = RightMin->_right;
172.                                         }
173.                                        
174.                                         delete RightMin;
175.                                         return true;
176.                                 }
177.                         }
178.                 }
179.                 return false;
180.         }
181. private:
182.         void _InOrder(Node* root)
183.         {
184.                 if (root == nullptr)
185.                 {
186.                         return;
187.                 }
189.                 _InOrder(root->_left);
190.                 cout << root->_key << ' ';
191.                 _InOrder(root->_right);       
192.         }
194. private:
195.        
196.         Node* _root = nullptr;
197. };

复制代码

---

1. #define _CRT_SECURE_NO_WARNINGS
2. #include"BStree.h"
3. using namespace std;
4. int main()
5. {
6.     int arr[] = { 8,3,1,10,6,4,7,14,13 };
7.     BSTree<int> t;
8.     for (auto e : arr)
9.     {
10.         t.Insert(e);
11.     }
12.     t.Insert(16);
13.     t.Insert(4);
14.     t.InOrder();
16.     for (auto e : arr)
17.     {
18.         t.Erase(e);
19.         t.InOrder();
20.     }
21.     return 0;
22. }

复制代码

总结

删除有点复杂照旧要花时间去明白

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。