0%

数据结构-树和二叉树(五)二叉排序树

二叉排序树🚉

==二叉排序树==,又称==二叉查找树==( BST, Binary Search Tree)
一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:

  1. 左子树上所有结点的关键字均小于根结点的关键字;

  2. 右子树上所有结点的关键字均大于根结点的关键字。

  3. 左子树和右子树又各是一棵二叉排序树。

  4. 左子树结点值 < 根结点值 < 右子树结点值

  5. 进行中序遍历,可以得到一个递增的有序序列

1 代码实现

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
//
// Created by Wang on 2021/8/23.
//
#include <iostream>
#include <string>
using namespace std;
typedef struct BSTNode{
int value;
struct BSTNode *lChild, *rChild;
}BSTNode, *BSTree;

/**
* 非递归插入
* @param T
* @param e
* @return
*/
void InsertBST(BSTree &T,int e) {
auto *newNode = (BSTNode *)malloc(sizeof(BSTNode));
if (T == nullptr) {
newNode->value = e;
newNode->lChild = nullptr;
newNode->rChild = nullptr;
T = newNode;
return;
}
BSTNode *p = T, *parent = nullptr;

while (p != nullptr) {
if (p->value == e) {
cout << e << "值已存在" << endl;
return;
}
parent = p;
if (parent->value > e) {
p = p->lChild;
}else {
p = p->rChild;
}
}
newNode->value = e;
newNode->rChild = nullptr;
newNode->lChild = nullptr;
if (parent->value > e) {
parent->lChild = newNode;
}else {
parent->rChild = newNode;
}
return;
}

/**
* 递归插入
* @param T
* @param e
* @return
*/
void RecursionInsertBST(BSTree &T, int e) {
auto *newNode = (BSTNode *)malloc(sizeof(BSTNode));
if (T == nullptr) {
newNode->value = e;
newNode->lChild = nullptr;
newNode->rChild = nullptr;
T = newNode;
return;
}
else if (T->value == e) {
cout << e << "值已存在" << endl;
return;
} else if (e > T->value) {
return RecursionInsertBST(T->rChild, e);
}else {
return RecursionInsertBST(T->lChild, e);
}
}

/**
* 构造二叉排序树
* @param T
* @param str
* @param n
* @return
*/
bool CreatBST(BSTree &T, int str[], int n) {
T = nullptr;
int i = 0;
while (i < n) {
InsertBST(T, str[i]);
// RecursionInsertBST(T, str[i]);
i++;
}
}

/**
* 非递归查找
* @param T
* @param e
* @return
*/
BSTNode *SearchBST(BSTree T, int e) {
while (T != nullptr && e != T->value) {
if (e < T->value) {
T = T->lChild;
}else
T = T->rChild;
}
return T;
}

/**
* 递归查找
* @param T
* @param e
* @return
*/
BSTNode *RecursionSearchBST(BSTree T, int e) {
if (T == nullptr) {
return nullptr;
}
if (e == T->value) {
return T;
}else if (e < T->value) {
return RecursionSearchBST(T->lChild, e);
}else {
return RecursionSearchBST(T->rChild, e);
}
}

/**
* 查找子树最小值结点即,父节点的直接后继结点
* @param T
* @return
*/
BSTNode *SearchMin(BSTree T) {
while (T->lChild != nullptr) {
T = T->lChild;
}
return T;
}
/**
* 删除
* @param T
* @param e
* @return
*/
bool DeleteBST(BSTree &T, int e) {
if (T == nullptr) {
return false;
}
BSTNode *p = T;
BSTNode *parent = nullptr;
int tag = 0; //左子树0,右子树1
while (p != nullptr && e != p->value) { //寻找要删除的结点
parent = p; //得其父节点
if (e < T->value) {
p = p->lChild;
tag = 0;
}
else {
p = p->rChild;
tag = 1;
}
}
if (p->rChild == nullptr && p->lChild == nullptr) { //左右子树为空,
if (tag == 0) {
parent->lChild = nullptr;
} else {
parent->rChild = nullptr;
}
free(p);
}else if (p->rChild == nullptr && p->lChild != nullptr) { //右子树为空
if (tag == 0) {
parent->lChild = p->lChild;
} else {
parent->rChild = p->lChild;
}
free(p);
}else if (p->rChild != nullptr && p->lChild == nullptr) { //左子树为空
if (tag == 0) {
parent->lChild = p->rChild;
} else {
parent->rChild = p->rChild;
}
free(p);
}else { // 左右子树均不为空
if (tag == 0) {
BSTNode *t = SearchMin(p->lChild); //寻找p结点右子树的最小结点
int tValue = t->value;
DeleteBST(T, t->value); //删除最小结点
p->value = tValue; //将此结点替换到删除结点

} else {
BSTNode *t = SearchMin(p->rChild);
int tValue = t->value;
DeleteBST(T, t->value); //删除最小结点
p->value = tValue;
}
}
}

/**
* 中序遍历
* @param root
*/
void InOrderTraversal(BSTree root) {
if (root == nullptr) {
return;
}
InOrderTraversal(root->lChild);
cout << root->value << "->";
InOrderTraversal(root->rChild);
}

int main() {
BSTree T;
T = (BSTree)malloc(sizeof(BSTNode));
int arr[] = {54, 20, 66, 40, 28, 58, 79};
int len = sizeof(arr) / sizeof(arr[0]);
cout << "创建二叉排序树" << endl;
CreatBST(T, arr, len);
cout << "中序遍历" << endl;
InOrderTraversal(T);
printf("\n");
cout << "查找20子树" << endl;
InOrderTraversal(SearchBST(T, 20));
printf("\n");
cout << "删除结点20" << endl;
DeleteBST(T, 20);
InOrderTraversal(T);
printf("\n");
return 0;
}
1
2
3
4
5
6
7
创建二叉排序树
中序遍历
20->28->40->54->58->66->79->
查找20子树
20->28->40->
删除结点20
28->40->54->58->66->79->

2、查找效率分析

查找长度——在查找运算中,需要对比关键字的次数称为查找长度,反映了查找操作时间复杂度

若树高h, 找到最下层的一个结点需要对比 h 次

最好情况: n个结点的二叉树最小高度为[log2n] + 1。平均查找长度 = O(log2n)

最坏情况:每个结点只有一个分支,树高 h = 结点数n。 平均查找长度 = O(n)

1 数据结构-树和二叉树(四)树和森林

1.1 树的逻辑结构

==树==是n(n≥0)个结点的有限集合, n = 0时,称为空树,这是一种特殊情况。

在任意一棵非空树中应满足:

1、有且仅有一个特定的称为根的结点。

2、当n > 1时,其余结点可分为m(m > 0)个互不相交的有限集合T1, T2,…, Tm,其中每个集合本身又是一棵树,并且称为根结点的子树。

树的定义是递归的,即在树的定义中又用到了其自身,树是一种递归的数据结构。

树作为一种逻辑结构,同时也是一种分层结构,具有以下两个特点:

  1. 🌲除了根节点外,任何一个结点都有且仅有一个前驱
  2. 🌳中所有结点可以有零个或多个后继

1.2 双亲表示法

1.3 孩子表示法

1.4 孩子兄弟表示法

image-20210822104916075

1.5 树、森林与二叉树的转换

1.6 树和森林的遍历

1、树的遍历

(1)先根遍历

==先根遍历==。若树非空,先访问根结点,再依次对每棵子树进行先根遍历。 ==深度优先遍历==

树的先根遍历序列与这棵树相应二叉树的先序序列相同

(2)后根遍历

==后根遍历==。若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点。 ==深度优先遍历==

树的后根遍历序列与这棵树相应二叉树的中序序列相同。

(3)层次遍历

==层次遍历==(用队列实现) ==广度优先遍历==

① 若树非空, 则根节点入队

② 若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队

③ 重复②直到队列为空

2、森林的遍历

(1)先序遍历

==先序遍历森林==。

若森林为非空,则按如下规则进行遍历:

  1. 访问森林中第一棵树的根结点。
  2. 先序遍历第一棵树中根结点的子树森林。
  3. 先序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对==各个树进行先根遍历== ,等同于依次对==二叉树的先序遍历==

(2)中序遍历

==中序遍历森林==。

若森林为非空,则按如下规则进行遍历:

  1. 中序遍历森林中第一棵树的根结点的子树森林。
  2. 访问第一棵树的根结点。
  3. 中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对==各个树进行后根遍历== ,等同于依次对==二叉树的中序遍历==

数据结构算法每日一练(九)查找链表倒数元素

难度: ⭐⭐

题目: 已知一个带有表头结点的单链表,假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数

第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:

(1)描述算法的基本设计思想。

(2)描述算法的详细实现步骤。

(3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C、C++或Java语言实现),关键之处请给出简要注释。

阅读全文 »

数据结构算法每日一练(八)数组循环队列

难度: ⭐⭐

题目:下面是给定容量为MAX的使用循环数组实现队列的代码片段,其中T是队列中元素类型。

static int const MAX = 256; //队列的最大容量

static T* data; //循环数组,队列元素存储在此

static 其他必要数据;

(1)请给出循环数组实现队列所需的其他必要数据的定义;

(2)请使用循环数组实现队列的下述六个功能函数,请首先用语言描述实现的方法,再给出C/C++语言的具体实现。

阅读全文 »

数据结构算法每日一练(七)数组未出现最小正整数

难度: ⭐⭐

题目:给定一个含n(n≥1)个整数的数组A,请设计一个在时间上尽可能高效的算法。找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}

中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:

1)给出算法的基本设计思想。

2)根据设计思想,来用C或C++语言描述算法,关键之处给出注释。

3)说明你所设计算法的时问复杂度和空问复杂度。

阅读全文 »