用ML Kit搭建属于自己的机器学习手机平台软件

温习二叉树的内容

预置知识

我们首先先说一下 时间复杂度和空间复杂度

学会估计空间复杂度(清华初试题)

时间复杂度T(n)主要是看循环结构和判断结构,用这个来衡量时间的复杂度。

空间复杂度S(n)主要看运行完一个程序所需内存的大小

二叉树与别的数据结构(2018清华考研)

然后让我们说一下二叉树的时间复杂度的区别

假设当前我们准备对十万个数据进行排序插入。

有序链表查找成本为O(n),但是插入成本为O(1)

有序数组查找成本为O(1),但是插入成本为O(n)

而二叉树则恰好都是O((log_2N))。

折中使用排序二叉树(二叉树仅仅作为排序二叉树的基础)进行查找。相对来说就会处于一个中庸的位置。

我们再来分析一下他们的空间复杂度,说白了就是内存的占用比。

三者常用的方法的对应空间复杂度为f(1)

给个小小的应用

具体的应用就是由排序二叉树(由于普通排序二叉树可能会有不平衡的情况)引申出来的红黑树(Linux系统中ext3文件系统管理),avl树“windows对程地址空间的管理”。

当前绝大多数的文件系统都是用二叉树进行搜索。

树与二叉树的区别

  1. 树中节点的子节点个数没有限制,而二叉树的节点最多为两个
  2. 树中的节点无左右之分,而二叉树有左右之分

完全二叉树

若设二叉树的高度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层有叶子节点,并且叶子节点都是从左到右一次排布。

叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

注意:堆是基于完全二叉树

img

满二叉树

除了叶子节点外每一个节点都要左右子节点,并且叶子节点都处在最底层的二叉树。

img

平衡二叉树

基于二分法的策略提高数据的查找速度的二叉树的数据结构;

B树

数据库常用这个

(1)树种的每个节点最多拥有m个子节点且m>=2,空树除外(注:m阶代表一个树节点最多有多少个查找路径,m阶=m路,当m=2则是2叉树,m=3则是3叉);

(2)除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个,非根节点关键字数必须>=2;(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)

(3)所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子

(4)如果一个非叶节点有N个子节点,则该节点的关键字数等于N-1;

(5)所有节点关键字是按递增次序排列,并遵循左小右大原则;

B+树

上边的树的升级版。

二叉树的遍历(清华机试常考)

  1. 先序遍历(根节点-左孩子-右孩子)
  2. 中序遍历(左孩子-根节点-右孩子)
  3. 后序遍历(左孩子-右孩子-根节点)

img

图示的遍历效果:

先序遍历:A-B-D-G-C-E-F

中序遍历:D-G-B-A-E-C-F

后续遍历:G-D-B-E-F-C-A

如图的树,在用代码实现是可定义为String expression = "A(B(D(,G)),C(E,F))"

  • 遇到字母,将要创建节点
  • 遇到”(“,创建左孩子节点
  • 遇到”,”,创建右孩子节点
  • 遇到”)”,返回到上一层节点
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
#include <stdio.h>
#include <stdlib.h>
#define QueueMaxSize 20 //定义队列数组长度
#define StackMaxSize 10 //定义栈数组长度
typedef char ElemType; //定义ElemType类型
struct BTreeNode //结点类型定义
{
ElemType data;
struct BtreeNode* left; // 左指针域
struct BtreeNode* right;// 右指针域
};

//1.初始化二叉树
void InitBTree(struct BTreeNode** BT)
{
*BT = NULL; //把树根指针置空
}

//2.建立二叉树,采用广义表表示的输入法,如:A(B(C,D),E(F,G))
void CreateBTree(struct BTreeNode** BT, char* string)
{
struct BTreeNode* p;
struct BTreeNode* s[StackMaxSize]; //定义s数组作为存储根结点的指针的栈使用
int top = -1; //栈顶指针置为-1,表示空栈
int k; //把k作为处理结点的标志,k=1处理左子树,k=2处理右子树
int i =0;
*BT = NULL; //把树根指针置空,即从空树开始建立二叉树
while (string[i])
{
switch (string[i])
{
case ' ':break;
case '(':
{
if (top == StackMaxSize - 1)
{
printf("栈空间太小,需要增加StackMaxSize!\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
}
case ')':
{
if (top == -1)
{
printf("二叉树广义表字符串错!\n");
exit(1);
}
top--;
break;
}
case ',':k =2 ;break;
default:
{
p = malloc(sizeof(struct BTreeNode));
p->data = string[i];
p->left = p->right = NULL;
if (*BT == NULL)
*BT = p;
else
{
if (k == 1)
s[top]->left = p;
else
s[top]->right = p;
}
}
}
i++;
}//while end
}

//3.检查二叉树是否为空
int BTreeEmpty(struct BTreeNode* BT)
{
if (BT == NULL)
return 1;
else
return 0;
}

//4.求二叉树深度
int BTreeDepth(struct BTreeNode* BT)
{
if (BT == NULL)
return 0;
else
{
int dep1 = BTreeDepth(BT->left); //计算左子树深度
int dep2 = BTreeDepth(BT->right); //计算右子树深度
if (dep1 > dep2)
return dep1 + 1;
else
return dep2 + 1;
}
}

//5.从二叉树中查找值为x的结点,若存在则返回元素存储位置,否则返回空值(算法类似于前序遍历)
ElemType* FindBTree (struct BTreeNode* BT, ElemType x)
{
if (BT == NULL)
return NULL;
else
{
if (BT->data == x)
return &(BT->data);
else
{
ElemType* p;
if (p = FindBTree(BT->left,x))
return p;
if (p = FindBTree(BT->right,x))
return p;
return NULL;
}
}
}

//6、输出二叉树,可在前序遍历的基础上修改。采用广义表输出格式:A(B(C,D),E(,F(G)))
void PrintBTree(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%c", BT->data); //输出根结点的值
if (BT->left != NULL || BT->right != NULL)
{
printf("(");
PrintBTree(BT->left); //输出左子树
if (BT->right != NULL)
printf(",");
PrintBTree(BT->right); //输出右子树
printf(")");
}
}
}


//7.消除二叉树,使之成为一棵空树,算法类似于后序递归遍历
void ClearBTree(struct BTreeNode** BT)
{
if (*BT != NULL)
{
ClearBTree(&((*BT)->left));//删除左子树
ClearBTree(&((*BT)->right));//删除右子树
free(*BT);//释放根结点
*BT = NULL;//置根结点为空
}
}

//8.前序遍历
void Preorder(struct BTreeNode* BT)
{
if (BT != NULL)
{
printf("%c,",BT->data);
Preorder(BT->left);
Preorder(BT->right);
}
}

//9.中序遍历
void Inorder(struct BTreeNode* BT)
{
if (BT != NULL)
{
Inorder(BT->left);
printf(("%o",BT->data));
Inorder(BT->right);
}
}

//10、后序遍历
void Postorder(struct BTreeNode* BT)
{
if (BT != NULL)
{
Postorder(BT->left);
Postorder(BT->right);
printf("%c,", BT->data);
}
}
//11、按层遍历
//按层遍历算法需要使用一个队列,开始时把整个树的根结点入队,然后每从队列中删除一个结点并输出该结点时,
//都把它的非空的左右孩子结点入队,当队列为空时算法结束。
//算法中,队列的最大长度不会超过二叉树中相邻两层的最大结点数,
//所以在提前在程序开始处定义最大队列长度QueueMaxSize大于队列的最大长度,就无需考虑队满溢出的事了
void Levelorder(struct BTreeNode* BT)
{
struct BTreeNode* p;
struct BTreeNode* q[QueueMaxSize];//定义队列所使用的数组空间,元素类型为指向结点的指针类型
int front = 0;
int rear = 0;
if (BT != NULL)//将树根指针入队
{
q[rear] = BT;
rear = (rear + 1) % QueueMaxSize;
}
while (front != rear)//当队列非空时执行循环
{
p = q[front];//保存队首元素
front = (front + 1) % QueueMaxSize;//删除队首元素,使队首指针指向队首元素
printf("%c,", p->data);//输出队首元素
if (p->left != NULL)//若结点存在左孩子,则左孩子结点指针入队
{
q[rear] = p->left;
rear = (rear + 1) % QueueMaxSize;
}
if (p->right != NULL)//若结点存在右孩子,则左孩子结点指针入队
{
q[rear] = p->right;
rear = (rear + 1) % QueueMaxSize;
}
}
}

//主函数
void main()
{
struct BTreeNode* bt;
char b[50];
ElemType x, *px;
InitBTree(&bt);
printf("输入二叉树广义表字符串:\n");
scanf("%s", b);
CreateBTree(&bt, b);
PrintBTree(bt);
printf("\n");

printf("前序:");
Preorder(bt);
printf("\n");

printf("中序:");
Inorder(bt);
printf("\n");

printf("后序:");
Postorder(bt);
printf("\n");

printf("按层:");
Levelorder(bt);
printf("\n");

printf("输入一个待查找的字符:\n");
scanf(" %c", &x); //格式串中的空格可以跳过任何空白符
px = FindBTree(bt, x);
if (px)
printf("查找成功:%c\n", *px);
else
printf("查找失败\n");

printf("二叉树的深度为:");
printf("%d\n", BTreeDepth(bt));
ClearBTree(&bt);
}

本文作者: Bon
本文地址https://bonxg.com/p/8.html
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!

# Bon
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×