二叉树2（二叉查找树的插入、查找、删除、遍历）

109 阅读 0 评论 72 点赞

我是靠谱客的博主隐形手链，这篇文章主要介绍二叉树2（二叉查找树的插入、查找、删除、遍历），现在分享给大家，希望可以做个参考。

单纯想用类把它给封装起来
BinarySearchTree.h

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAX = 1000000000;
typedef struct BSTNode
{
int data;
//数据
int num;
//数量
BSTNode* left;
BSTNode* right;
}Node,*pointer;
//
const修饰的函数 函数体内不能对成员数据做任何改动
class BinarySearchTree
{
private:
pointer Root;
pointer Empty(pointer node);
pointer Search(pointer node, int key) const; //内部查找
pointer SearchMin(pointer node) const; //内部查找
pointer Insert(pointer node, int key);
//内部插入
pointer Delete(pointer node, int key); //内部删除
pointer DeleteMin(pointer node);
//删除最小值
void PreOrder(pointer node) const;
//先序
void InOrder(pointer node) const;
//中序
void PostOrder(pointer node) const; //后序
void PrintNode(pointer node) const; //输出节点信息
public:
BinarySearchTree();
~BinarySearchTree();
bool Search(int key) const;
//外部查找
int SearchMin() const;
//查找最小值
bool Insert(int key);
//外部插入
bool Delete(int key);
//删除
void PreOrder() const;
//先序
void InOrder() const;
//中序
void PostOrder() const; //后序
void LeverOrder() const; //层次 宽度优先
void DepthOrder() const; //深度优先 先序的非递归
};
BinarySearchTree::BinarySearchTree()
{
Root = NULL;
}
BinarySearchTree::~BinarySearchTree()
//析构函数在对象作用域结束后调用 如在函数fun内创建node，则A结束就调用
{
Empty(Root);
}
//清空
pointer BinarySearchTree::Empty(pointer node)
{
if (node)
{
Empty(node->left);
Empty(node->right);
free(node);
}
return NULL;
}
//查找 存在返回T 否则返回F
bool BinarySearchTree::Search(int key) const
{
if (Search(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Search(pointer node, int key) const
{
if (node == NULL)
return NULL;
if (key < node->data)
return Search(node->left, key);
else if (key > node->data)
return Search(node->right, key);
else
return node;
}
//查找最小值 若为空树 返回 MAX
int BinarySearchTree::SearchMin() const
{
pointer T = Root;
if (T != NULL)
while (T->left != NULL)
T = T->left;
if (T)
return T->data;
else
return MAX;
}
pointer BinarySearchTree::SearchMin(pointer node) const
{
if (node == NULL)
return NULL;
else if (node->left == NULL)
return node;
else
return SearchMin(node->left);
}
//插入 
bool BinarySearchTree::Insert(int key)
{
if (Insert(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Insert(pointer node, int key)
{
if (node == NULL)
{
node = (pointer)malloc(sizeof(Node));
if (node == NULL)
{
perror("Allocate dynamic memory");
//错误输出语句
return node;
}
node->data = key;
node->num = 1;
node->left = node->right = NULL;
if (Root == NULL)
//这一步必须有 传入的指针仅仅是一个拷贝，方法不会改变原指针的地址、值，但是可能会改变原指针所指向内存块的数据
Root = node;
}
else if (key < node->data)
node->left = Insert(node->left, key);
else if (key > node->data)
node->right = Insert(node->right, key);
else
node->num++;
return node;
}
//删除
bool BinarySearchTree::Delete(int key)
{
if (Delete(Root, key))
return true;
return false;
}
pointer BinarySearchTree::DeleteMin(pointer node)
{
pointer current = node;
pointer parent = node;
node = node->right;
if (node->left == NULL)
//如果右子树没有左子树 那么它直接替代
{
current->data = node->data;
current->right = node->right;
//就算右子树为空也可以直接NULL
}
else
{
while (node->left != NULL)
//找到右子树的最小子树
{
parent = node;
node = node->left;
}
current->data = node->data;
parent->left = node->right;
}
free(node);
return current;
}
pointer BinarySearchTree::Delete(pointer node, int key)
{
if (node == NULL)
return NULL;
else if (key < node->data)
node->left = Delete(node->left, key);
else if (key > node->data)
node->right = Delete(node->right, key);
else if (node->left && node->right)
//2个儿子都有
{
//直接在查找的时候就删除了
node = DeleteMin(node);
}
else
//一个或者0个儿子
{
pointer temp = node;
if (node->left == NULL)
node = node->right;
else if (node->right == NULL)
node = node->left;
if (temp->data == Root->data)
//如果是删除根 Root要重定向一下
Root = node;
free(temp);
}
return node;
}
//遍历
void BinarySearchTree::PrintNode(pointer node) const
{
printf("%d ", node->data);
//printf("data: %d num: %dn", node->data, node->num);
}
//先序
void BinarySearchTree::PreOrder() const
{
if (Root)
{
printf("PreOrder: ");
PreOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PreOrder(pointer node) const
{
if (node != NULL)
{
PrintNode(node);
PreOrder(node->left);
PreOrder(node->right);
}
}
//中序
void BinarySearchTree::InOrder() const
{
if (Root)
{
printf("InOrder: ");
InOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::InOrder(pointer node) const
{
if (node != NULL)
{
InOrder(node->left);
PrintNode(node);
InOrder(node->right);
}
}
//后序
void BinarySearchTree::PostOrder() const
{
if (Root)
{
printf("PostOrder: ");
PostOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PostOrder(pointer node) const
{
if (node != NULL)
{
PostOrder(node->left);
PostOrder(node->right);
PrintNode(node);
}
}
//层次遍历 用队列
void BinarySearchTree::LeverOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("LevelOrder: ");
pointer temp;
queue<pointer> q;
q.push(Root);
while (!q.empty())
{
temp = q.front();
q.pop();
PrintNode(temp);
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
printf("n");
}
//深度优先 用栈 先序的非递归实现
void BinarySearchTree::DepthOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("DepthOrder: ");
pointer temp;
stack<pointer> s;
s.push(Root);
while (!s.empty())
{
temp = s.top();
s.pop();
PrintNode(temp);
if (temp->right)
s.push(temp->right);
if (temp->left)
s.push(temp->left);
}
printf("n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAX = 1000000000;
typedef struct BSTNode
{
int data;
//数据
int num;
//数量
BSTNode* left;
BSTNode* right;
}Node,*pointer;
//
const修饰的函数 函数体内不能对成员数据做任何改动
class BinarySearchTree
{
private:
pointer Root;
pointer Empty(pointer node);
pointer Search(pointer node, int key) const; //内部查找
pointer SearchMin(pointer node) const; //内部查找
pointer Insert(pointer node, int key);
//内部插入
pointer Delete(pointer node, int key); //内部删除
pointer DeleteMin(pointer node);
//删除最小值
void PreOrder(pointer node) const;
//先序
void InOrder(pointer node) const;
//中序
void PostOrder(pointer node) const; //后序
void PrintNode(pointer node) const; //输出节点信息
public:
BinarySearchTree();
~BinarySearchTree();
bool Search(int key) const;
//外部查找
int SearchMin() const;
//查找最小值
bool Insert(int key);
//外部插入
bool Delete(int key);
//删除
void PreOrder() const;
//先序
void InOrder() const;
//中序
void PostOrder() const; //后序
void LeverOrder() const; //层次 宽度优先
void DepthOrder() const; //深度优先 先序的非递归
};
BinarySearchTree::BinarySearchTree()
{
Root = NULL;
}
BinarySearchTree::~BinarySearchTree()
//析构函数在对象作用域结束后调用 如在函数fun内创建node，则A结束就调用
{
Empty(Root);
}
//清空
pointer BinarySearchTree::Empty(pointer node)
{
if (node)
{
Empty(node->left);
Empty(node->right);
free(node);
}
return NULL;
}
//查找 存在返回T 否则返回F
bool BinarySearchTree::Search(int key) const
{
if (Search(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Search(pointer node, int key) const
{
if (node == NULL)
return NULL;
if (key < node->data)
return Search(node->left, key);
else if (key > node->data)
return Search(node->right, key);
else
return node;
}
//查找最小值 若为空树 返回 MAX
int BinarySearchTree::SearchMin() const
{
pointer T = Root;
if (T != NULL)
while (T->left != NULL)
T = T->left;
if (T)
return T->data;
else
return MAX;
}
pointer BinarySearchTree::SearchMin(pointer node) const
{
if (node == NULL)
return NULL;
else if (node->left == NULL)
return node;
else
return SearchMin(node->left);
}
//插入 
bool BinarySearchTree::Insert(int key)
{
if (Insert(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Insert(pointer node, int key)
{
if (node == NULL)
{
node = (pointer)malloc(sizeof(Node));
if (node == NULL)
{
perror("Allocate dynamic memory");
//错误输出语句
return node;
}
node->data = key;
node->num = 1;
node->left = node->right = NULL;
if (Root == NULL)
//这一步必须有 传入的指针仅仅是一个拷贝，方法不会改变原指针的地址、值，但是可能会改变原指针所指向内存块的数据
Root = node;
}
else if (key < node->data)
node->left = Insert(node->left, key);
else if (key > node->data)
node->right = Insert(node->right, key);
else
node->num++;
return node;
}
//删除
bool BinarySearchTree::Delete(int key)
{
if (Delete(Root, key))
return true;
return false;
}
pointer BinarySearchTree::DeleteMin(pointer node)
{
pointer current = node;
pointer parent = node;
node = node->right;
if (node->left == NULL)
//如果右子树没有左子树 那么它直接替代
{
current->data = node->data;
current->right = node->right;
//就算右子树为空也可以直接NULL
}
else
{
while (node->left != NULL)
//找到右子树的最小子树
{
parent = node;
node = node->left;
}
current->data = node->data;
parent->left = node->right;
}
free(node);
return current;
}
pointer BinarySearchTree::Delete(pointer node, int key)
{
if (node == NULL)
return NULL;
else if (key < node->data)
node->left = Delete(node->left, key);
else if (key > node->data)
node->right = Delete(node->right, key);
else if (node->left && node->right)
//2个儿子都有
{
//直接在查找的时候就删除了
node = DeleteMin(node);
}
else
//一个或者0个儿子
{
pointer temp = node;
if (node->left == NULL)
node = node->right;
else if (node->right == NULL)
node = node->left;
if (temp->data == Root->data)
//如果是删除根 Root要重定向一下
Root = node;
free(temp);
}
return node;
}
//遍历
void BinarySearchTree::PrintNode(pointer node) const
{
printf("%d ", node->data);
//printf("data: %d num: %dn", node->data, node->num);
}
//先序
void BinarySearchTree::PreOrder() const
{
if (Root)
{
printf("PreOrder: ");
PreOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PreOrder(pointer node) const
{
if (node != NULL)
{
PrintNode(node);
PreOrder(node->left);
PreOrder(node->right);
}
}
//中序
void BinarySearchTree::InOrder() const
{
if (Root)
{
printf("InOrder: ");
InOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::InOrder(pointer node) const
{
if (node != NULL)
{
InOrder(node->left);
PrintNode(node);
InOrder(node->right);
}
}
//后序
void BinarySearchTree::PostOrder() const
{
if (Root)
{
printf("PostOrder: ");
PostOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PostOrder(pointer node) const
{
if (node != NULL)
{
PostOrder(node->left);
PostOrder(node->right);
PrintNode(node);
}
}
//层次遍历 用队列
void BinarySearchTree::LeverOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("LevelOrder: ");
pointer temp;
queue<pointer> q;
q.push(Root);
while (!q.empty())
{
temp = q.front();
q.pop();
PrintNode(temp);
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
printf("n");
}
//深度优先 用栈 先序的非递归实现
void BinarySearchTree::DepthOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("DepthOrder: ");
pointer temp;
stack<pointer> s;
s.push(Root);
while (!s.empty())
{
temp = s.top();
s.pop();
PrintNode(temp);
if (temp->right)
s.push(temp->right);
if (temp->left)
s.push(temp->left);
}
printf("n");
}

这里写图片描述
使用：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include"BinarySearchTree.h"
using namespace std;
int main()
{
BinarySearchTree Tree;
Tree.Insert(12);
Tree.Insert(6);
Tree.Insert(2);
Tree.Insert(10);
Tree.Insert(11);
Tree.Insert(9);
Tree.Insert(7);
Tree.Insert(8);
Tree.Insert(14);
Tree.Delete(6);
Tree.Delete(2);
Tree.PreOrder();
Tree.InOrder();
Tree.PostOrder();
Tree.LeverOrder();
return 0;
}