数据结构学习<五> 树的性质及二叉搜索树实现

树是一种常见的抽象数据结构,一棵树的性质就是任意两个节点只有唯一的一条路径

二叉树

我们一般都分析的是二叉树,对于一个节点要不是内部节点要不是外部节点,外部节点又叫叶子,内部节点有左子树或者右子树或者都有。

##二叉树的性质

  • 一棵有N个内部节点的二叉树有N+1个外部节点
  • 一棵有N个内部节点的二叉树有2N个链接:N-1个链接到内部节点,N+1个链接到外部节点
  • 有N个内部节点的二叉树的高度至少是\(lgN\),至多是\(N-1\)
  • 深度为\(k\)的二叉树至多有\(2^k-1\)个节点

二叉搜索树

二叉搜索树

对于二叉搜索树的任意一个节点,比其小的一定在其左子树,比其大的一定在其右子树。
这样的性质决定了二叉搜索树的查找性能很好

二叉搜索树的点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
class BSNode
{
template<typename C> friend class BSTree;
public:
BSNode(T t)
:value(t), lchild(nullptr), rchild(nullptr){}
BSNode() = default;
private:
T value;
BSNode<T>* lchild;
BSNode<T>* rchild;
BSNode<T>* parent;
};
  • value:节点的值
  • lchild:指向节点的左子树
  • rchild: 指向节点的右子树
  • parent: 指向节点的父节点

二叉搜索树的定义

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
template<typename T>
class BSTree
{
public:
typedef typename BSNode<T> node;
typedef typename BSNode<T>* node_pointer;
typedef typename T value_type;
BSTree()
:root(nullptr){}
BSTree(value_type val)//val为根节点
{
root = new node(val);
}
~BSTree()
{
destory(root);
}
void preOrder();//前序遍历
void inOrder();//中序遍历
void postOrder();//后续遍历
void layerOrder();//层序遍历
node_pointer search_recursion(value_type key);//递归查找
node_pointer search_iterator(value_type key);//迭代查找
value_type search_min();//寻找最小值
value_type search_max();//寻找最大值
node_pointer successor(node_pointer x);//查找指定节点的后继节点
node_pointer predecessor(node_pointer x);//查找指定节点的前驱节点
void insert(value_type key);//插入值
void remove(value_type key);//删除节点
void destory();//销毁树
void print();//按前序,中序,后序,层序分别打印树
private:
node_pointer root;
node_pointer search(node_pointer p,value_type key);
void remove(node_pointer p, value_type key);
void preOrder(node_pointer p);
void inOrder(node_pointer p);
void postOrder(node_pointer p);
void layerOrder(node_pointer p);
value_type search_minimun(node_pointer p);
value_type search_maximum(node_pointer p);
void destory(node_pointer &p);
};

接下来看看二叉树函数实现

插入操作

插入的过程

  • 寻找元素合适的插入位置:新元素与当前结点进行比较,若值大于当前结点,则从右子树进行寻找;否则从左子树进行寻找。
  • 找到插入位置之后,以元素的值构建新节点,插入二叉排序树中
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
template<typename T>
void BSTree<T>::insert(value_type key)
{
node_pointer pparent = nullptr;
node_pointer pnode = root;
while (pnode != nullptr)//找到合适的插入位置
{
pparent = pnode;
if (key > pnode->value)
pnode = pnode->rchild;
else if (key < pnode->value)
pnode = pnode->lchild;
else
break;
}
pnode = new node(key);//构建新点
if (pparent == nullptr)如果是空树
root = pnode;
else//不空
{
if (key > pparent->value)//大于父节点
{
pparent->rchild = pnode;
}
else//小于父节点
{
pparent->lchild = pnode;
}
}
pnode->parent = pparent;
}

遍历

我们来看看前序遍历,即访问节点,访问节点的左子树,再访问节点的右子树的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//前序遍历
template<typename T>
void BSTree<T>::preOrder()
{
preOrder(root);
}
template<typename T>
void BSTree<T>::preOrder(node_pointer p)
{
if (p != nullptr)
{
std::cout << p ->value <<" ";
preOrder(p->lchild);
preOrder(p->rchild);
}
}

这里是使用递归实现。

至于中序和后序遍历,可以见后边代码

层序遍历
层序遍历为是节点从上到小,从左到右的依次遍历,这里使用队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//层序遍历
template<typename T>
void BSTree<T>::layerOrder()
{
layerOrder(root);
}
template<typename T>
void BSTree<T>::layerOrder(node_pointer pnode)
{
std::queue<node_pointer> Q;
Q.push(pnode);
while (!Q.empty())
{
pnode = Q.front();
std::cout << pnode->value <<" ";
Q.pop();
if (pnode->lchild != nullptr)
Q.push(pnode->lchild);
if (pnode->rchild != nullptr)
Q.push(pnode->rchild);
}
std::cout << std::endl;
}

前驱后继节点

对于一个二叉搜索树,中序遍历恰好得到一个非递减的序列,在中序遍历中一个节点的上一个节点即他的前驱节点,同理后边一个是他的后继节点。

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
//寻找节点的前驱节点
template<typename T>
BSNode<T>* BSTree<T>::predecessor(node_pointer pnode)
{
if (pnode->lchild != nullptr)//如果有左子树
{
//先设为左子树
pnode = pnode->lchild;
//如果其左子树还有右子树,那就是右子树
while (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
}
return pnode;
}
//如果节点没有左子树
node_pointer pparent = pnode->parent;
while (pparent != nullptr&&pparent->lchild == pnode)//节点没有左子树,且其本身为其父节点的左子树,循环结束条件为找到第一个拥有右子树的父节点
{
pnode = pparent;
pparent = pparent->parent;
}
return pparent;//如果没有进入循环就是节点没有左子树,且本身为右子树,其父节点为其前驱节点。
}
//寻找后继节点
template<typename T>
BSNode<T>* BSTree<T>::successor(node_pointer pnode)
{
//如果节点有右子树,则其后继节点为右子树的最左节点
if (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
while (pnode->lchild!=nullptr)//寻找右子树的最左节点
{
pnode = pnode->lchild;
}
return pnode;
}
//////////////////////////////////////////////////////
//
//
// |---->本身是左子树,后继节点为其父节点
// |
//如果没有右子树---|
// |
// |---->本身是右子树,后继节点为其“具有左子树的最近父节点”
//
////////////////////////////////////////////////////////////
node_pointer pparent = pnode->parent;
while (pparent != nullptr&&pparent->rchild == pnode)//如果pnode!=pparent->rchild,pnode是pparent的左子树,也就是找到了
{
pnode = pparent;
pparent = pnode->parent;
}
return pparent;
}

删除操作

删除某个节点有三种情况:
1.被删除节点同时有左子树与右子树
2.被删除节点只有左子树或只有右子树。
3.被删除节点没有子树。
对于第一种情况,我们的处理方式是将前驱节点的值保存在当前结点,继而删除前驱节点。
对于第二种情况,我们直接用子树替换被删节点。
对于第三种情况,我们可以直接删除节点。
图

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
template<typename T>
void BSTree<T>::remove(value_type key)
{
remove(root, key);
}
template<typename T>
void BSTree<T>::remove(node_pointer pnode, value_type key)
{
if (pnode != nullptr)
{
if (pnode->value == key)//找到删除的对象
{
node_pointer pdel = nullptr;
//pnode为只有左子树或者只有右子树,或者没有子树
if (pnode->lchild == nullptr || pnode->rchild == nullptr)
pdel = pnode;
else//pnode有左右子树,使用前驱顶替
{
pdel = predecessor(pnode);
}
//此时要删除的节点只有一个孩子或者没有孩子,保存孩子指针
node_pointer pchild = nullptr;
if (pdel->lchild != nullptr)
pchild = pdel->lchild;
else
{
pchild = pdel->rchild;
}
//让孩子指向被删节点的父节点
if (pchild != nullptr)
pchild->parent = pdel->parent;
//如果删的是头节点,就修改root的值
if (pdel->parent == nullptr)
root = pchild;
else if(pdel->parent->lchild==pdel)//如果不是头节点并且是左节点
{
pdel->parent->lchild = pchild;
}
else//不是头节点且是右节点
{
pdel->parent->rchild = pchild;
}
if (pnode->value != pdel->value)
pnode->value = pdel->value;
delete pdel;
}
//递归寻找删除点。
else if(key>pnode->value)
{
remove(pnode->rchild, key);
}
else
{
remove(pnode->lchild, key);
}
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include"BStree.h"
#include<iostream>
int main(void)
{
BSTree<int> t(32);
t.insert(45);
t.insert(89);
t.insert(16);
t.insert(55);
t.insert(7);
t.insert(9);
t.print();
t.remove(32);
t.print();
std::cout << t.search_max();
t.destory();
return 0;
}

结果如图:
图

所有源代码

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
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
//BSTree.h
#pragma once
#include<queue>
#include<iostream>
template<typename T>
class BSNode
{
template<typename C> friend class BSTree;
public:
BSNode(T t)
:value(t), lchild(nullptr), rchild(nullptr){}
BSNode() = default;
private:
T value;
BSNode<T>* lchild;
BSNode<T>* rchild;
BSNode<T>* parent;
};
template<typename T>
class BSTree
{
public:
typedef typename BSNode<T> node;
typedef typename BSNode<T>* node_pointer;
typedef typename T value_type;
BSTree()
:root(nullptr){}
BSTree(value_type val)
{
root = new node(val);
}
~BSTree()
{
destory(root);
}
void preOrder();//前序遍历
void inOrder();//中序遍历
void postOrder();//后续遍历
void layerOrder();//层序遍历
node_pointer search_recursion(value_type key);//递归查找
node_pointer search_iterator(value_type key);//迭代查找
value_type search_min();
value_type search_max();
node_pointer successor(node_pointer x);//查找指定节点的后继节点
node_pointer predecessor(node_pointer x);//查找指定节点的前驱节点
void insert(value_type key);
void remove(value_type key);//删除节点
void destory();
void print();
private:
node_pointer root;
node_pointer search(node_pointer p,value_type key);
void remove(node_pointer p, value_type key);
void preOrder(node_pointer p);
void inOrder(node_pointer p);
void postOrder(node_pointer p);
void layerOrder(node_pointer p);
value_type search_minimun(node_pointer p);
value_type search_maximum(node_pointer p);
void destory(node_pointer &p);
};
template<typename T>
void BSTree<T>::insert(value_type key)
{
node_pointer pparent = nullptr;
node_pointer pnode = root;
while (pnode != nullptr)//找到合适的插入位置
{
pparent = pnode;
if (key > pnode->value)
pnode = pnode->rchild;
else if (key < pnode->value)
pnode = pnode->lchild;
else
break;
}
pnode = new node(key);
if (pparent == nullptr)
root = pnode;
else
{
if (key > pparent->value)
{
pparent->rchild = pnode;
}
else
{
pparent->lchild = pnode;
}
}
pnode->parent = pparent;
}
//前序遍历
template<typename T>
void BSTree<T>::preOrder()
{
preOrder(root);
}
template<typename T>
void BSTree<T>::preOrder(node_pointer p)
{
if (p != nullptr)
{
std::cout << p ->value <<" ";
preOrder(p->lchild);
preOrder(p->rchild);
}
}
//中序遍历
template<typename T>
void BSTree<T>::inOrder()
{
inOrder(root);
}
template<typename T>
void BSTree<T>::inOrder(node_pointer p)
{
if (p != nullptr)
{
inOrder(p->lchild);
std::cout << p->value << " ";
inOrder(p->rchild);
}
}
//后序遍历
template<typename T>
void BSTree<T>::postOrder()
{
postOrder(root);
}
template<typename T>
void BSTree<T>::postOrder(node_pointer p)
{
if (p != nullptr)
{
postOrder(p->lchild);
postOrder(p->rchild);
std::cout << p->value << " ";
}
}
//层序遍历
template<typename T>
void BSTree<T>::layerOrder()
{
layerOrder(root);
}
template<typename T>
void BSTree<T>::layerOrder(node_pointer pnode)
{
std::queue<node_pointer> Q;
Q.push(pnode);
while (!Q.empty())
{
pnode = Q.front();
std::cout << pnode->value <<" ";
Q.pop();
if (pnode->lchild != nullptr)
Q.push(pnode->lchild);
if (pnode->rchild != nullptr)
Q.push(pnode->rchild);
}
std::cout << std::endl;
}
template<typename T>
void BSTree<T>::print()
{
std::cout << "前序遍历: ";
preOrder();
std::cout << std::endl;
std::cout << "中序遍历: ";
inOrder();
std::cout << std::endl;
std::cout << "后序遍历: ";
postOrder();
std::cout << std::endl;
std::cout << "层序遍历: ";
layerOrder();
std::cout << std::endl;
}
//寻找节点的前驱节点
template<typename T>
BSNode<T>* BSTree<T>::predecessor(node_pointer pnode)
{
if (pnode->lchild != nullptr)//如果有左子树
{
//先设为左子树
pnode = pnode->lchild;
//如果其左子树还有右子树,那就是右子树
while (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
}
return pnode;
}
//如果节点没有左子树
node_pointer pparent = pnode->parent;
while (pparent != nullptr&&pparent->lchild == pnode)//节点没有左子树,且其本身为其父节点的左子树,循环结束条件为找到第一个拥有右子树的父节点
{
pnode = pparent;
pparent = pparent->parent;
}
return pparent;//如果没有进入循环就是节点没有左子树,且本身为右子树,其父节点为其前驱节点。
}
template<typename T>
BSNode<T>* BSTree<T>::successor(node_pointer pnode)
{
//如果节点有右子树,则其后继节点为右子树的最左节点
if (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
while (pnode->lchild!=nullptr)//寻找右子树的最左节点
{
pnode = pnode->lchild;
}
return pnode;
}
//////////////////////////////////////////////////////
//
//
// |---->本身是左子树,后继节点为其父节点
// |
//如果没有右子树---|
// |
// |---->本身是右子树,后继节点为其“具有左子树的最近父节点”
//
////////////////////////////////////////////////////////////
node_pointer pparent = pnode->parent;
while (pparent != nullptr&&pparent->rchild == pnode)//如果pnode!=pparent->rchild,pnode是pparent的左子树,也就是找到了
{
pnode = pparent;
pparent = pnode->parent;
}
return pparent;
}
template<typename T>
void BSTree<T>::remove(value_type key)
{
remove(root, key);
}
template<typename T>
void BSTree<T>::remove(node_pointer pnode, value_type key)
{
if (pnode != nullptr)
{
if (pnode->value == key)//找到删除的对象
{
node_pointer pdel = nullptr;
//pnode为只有左子树或者只有右子树,或者没有子树
if (pnode->lchild == nullptr || pnode->rchild == nullptr)
pdel = pnode;
else//pnode有左右子树,使用前驱顶替
{
pdel = predecessor(pnode);
}
//此时要删除的节点只有一个孩子或者没有孩子,保存孩子指针
node_pointer pchild = nullptr;
if (pdel->lchild != nullptr)
pchild = pdel->lchild;
else
{
pchild = pdel->rchild;
}
//让孩子指向被删节点的父节点
if (pchild != nullptr)
pchild->parent = pdel->parent;
//如果删的是头节点,就修改root的值
if (pdel->parent == nullptr)
root = pchild;
else if(pdel->parent->lchild==pdel)//如果不是头节点并且是左节点
{
pdel->parent->lchild = pchild;
}
else//不是头节点且是右节点
{
pdel->parent->rchild = pchild;
}
if (pnode->value != pdel->value)
pnode->value = pdel->value;
delete pdel;
}
else if(key>pnode->value)
{
remove(pnode->rchild, key);
}
else
{
remove(pnode->lchild, key);
}
}
}
template<typename T>
typename BSTree<T>::node_pointer BSTree<T>::search(node_pointer pnode, value_type key)
{
if (pnode == nullptr)
return nullptr;
if (pnode->value == key)
return pnode;
if (key > pnode->value)
return search(pnode->rchild, key);
else
{
return search(pnode->lchild, key);
}
}
template<typename T>
typename BSTree<T>::node_pointer BSTree<T>::search_recursion(value_type key)
{
return search(root, key);
}
template<typename T>
typename BSTree<T>::node_pointer BSTree<T>::search_iterator(value_type key)
{
node_pointer pnode = root;
while (pnode != nullptr)
{
if (key == pnode->value)
return pnode;
if (key > pnode->value)
pnode = pnode->rchild;
else
{
pnode = pnode->lchild;
}
}
return nullptr;
}
template<typename T>
typename BSTree<T>::value_type BSTree<T>::search_minimun(node_pointer pnode)
{
while(pnode->lchild != nullptr)
pnode = pnode->lchild;
return pnode->value;
}
template<typename T>
typename BSTree<T>::value_type BSTree<T>::search_min()
{
if (root == nullptr)
return value_type(0);
return search_minimun(root);
}
template<typename T>
typename BSTree<T>::value_type BSTree<T>::search_maximum(node_pointer pnode)
{
while (pnode->rchild != nullptr)
pnode = pnode->rchild;
return pnode->value;
}
template<typename T>
typename BSTree<T>::value_type BSTree<T>::search_max()
{
if (root == nullptr)
return value_type(0);
return search_maximum(root);
}
template<typename T>
void BSTree<T>::destory()
{
destory(root);
}
template<typename T>
void BSTree<T>::destory(node_pointer& pnode)
{
if (pnode != nullptr)
{
if (pnode->lchild != nullptr)
destory(pnode->lchild);
if (pnode->rchild != nullptr)
destory(pnode->rchild);
delete(pnode);
pnode = nullptr;
}
}