avatar

C语言实现二叉树的各种遍历及求解深度

一、介绍

  二叉树是一种重要的数据结构,在很多方面都有重要的应用,此文主要记录了二叉树的基础知识,包括二叉树的建立、前中后序遍历方式、层次遍历方式、求解二叉树的深度、求解二叉树的节点总数、求解二叉树每层的节点数目等。

二、实现思路

  主要借助栈和队列方式实现二叉树的非递归访问等操作,二叉树的建立采用递归方式。层次遍历时,借助队列数据结构,将根节点入队,当队列不为空时,退出队列的一个节点,判断此节点是否有左孩子,如有则访问,并将此孩子入队列,然后判断此节点是否有右孩子,如有则访问,并将有孩子入队列;重复此过程即可。

三、实现代码

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
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef char dataType;
//二叉树结构
typedef struct bnode{
dataType data;
struct bnode *lChild,*rChild;
}Bnode,*BTree;
//队列结构
typedef struct {
BTree data[MAXSIZE];
int front,rear;
}SeqQueue,*PSeqQueue;
//栈的结构
typedef struct {
BTree data[MAXSIZE];
int top;
}SeqStack,*PSeqStack;

//队列的初始化
PSeqQueue initSeqQueue(){
PSeqQueue queue;
queue = (PSeqQueue)malloc(sizeof(SeqQueue));
if(queue){
queue->front = queue->rear = 0;
}
return queue;
}
//判断队列是否为空
int emptyQueue(PSeqQueue queue){
if(queue && queue->front==queue->rear){
return 1;
}else{
return 0;
}
}
//入队列
int pushQueue(PSeqQueue queue,Bnode *node){
if((queue->rear+1)%MAXSIZE == queue->front){//判断队列是否满了
return -1;
}else{
queue->rear = (queue->rear+1)%MAXSIZE;//位置为0的地址空间不用,方便判断是否为空
queue->data[queue->rear] = node;
return 1;
}
}
//出队列
int popQueue(PSeqQueue queue,BTree *node){
if(emptyQueue(queue)){
return -1;
}else{
queue->front = (queue->front +1)%MAXSIZE;
*node = queue->data[queue->front];
return 1;
}
}
//读取队头元素
int frontQueue(PSeqQueue queue,BTree *node){
if(queue->rear == queue->front){
return -1;
}else{
*node = queue->data[(queue->front+1)%MAXSIZE];
return 1;
}
}
//销毁队列
void destroyQueue(PSeqQueue *queue){
if(*queue){
free(*queue);
*queue = NULL;
}
}
//栈的初始化
PSeqStack initStack(){
PSeqStack stack;
stack = (PSeqStack)malloc(sizeof(SeqStack));
if(stack){
stack->top = -1;
}
return stack;
}
//判断栈是否为空 1,空;0,非空
int emptyStack(PSeqStack stack){
if(stack->top == -1){
return 1;
}else{
return 0;
}
}
//入栈
int pushStack(PSeqStack stack,Bnode *node){
if(stack->top == MAXSIZE-1){
return 0;
}else{
stack->top ++;
stack->data[stack->top] = node;
return 1;
}
}
//出栈
int popStack(PSeqStack stack,BTree *node){
if(emptyStack(stack) == 1){
return 0;
}else{
*node = stack->data[stack->top];
stack->top --;
return 1;
}
}
//打印元素
void visit(char ch){
printf("%c \t",ch);
}

//二叉树的建立
BTree createTree(){
BTree tree;
dataType str;
str = getchar();
if(str == '#'){
tree = NULL;
}else{
tree = (BTree)malloc(sizeof(Bnode));
tree->data = str;
tree->lChild = createTree();
tree->rChild = createTree();
}
return tree;
}
//先序遍历二叉树
void perOrder(BTree tree){
PSeqStack stack;
BTree p = tree;
stack = initStack();
while(p || ! emptyStack(stack)){
if(p){
visit(p->data);
pushStack(stack,p);
p = p->lChild;
}else{
popStack(stack,&p);
p = p->rChild;
}
}
}
//中序遍历此二叉树
void inOrder(BTree tree){
PSeqStack stack;
BTree p = tree;
stack = initStack();
while(p || !emptyStack(stack)){
if(p){
pushStack(stack,p);
p = p->lChild;
}else{
popStack(stack,&p);
visit(p->data);
p = p->rChild;
}
}
}

//后序遍历打印元素
void postOrder(BTree tree){
PSeqStack s1,s2;
BTree p = tree;
s1 = initStack();
s2 = initStack();
while(p || !emptyStack(s2)){
if(p){
pushStack(s1,p);
pushStack(s2,p);
p = p->rChild;
}else{
popStack(s2,&p);
p = p->lChild;
}
}
while(!emptyStack(s1)){
popStack(s1,&p);
visit(p->data);
}
}
//层次遍历二叉树
void levelOrder(BTree tree ){
BTree p = tree;
PSeqQueue queue = initSeqQueue();
if(p){
pushQueue(queue,p);
while(!emptyQueue(queue)){
popQueue(queue,&p);
visit(p->data);
if(p->lChild){
pushQueue(queue,p->lChild);
}
if(p->rChild){
pushQueue(queue,p->rChild);
}
}
}
}
//求二叉树的高度
int height(BTree tree){
int h1,h2;
if(tree == NULL){
return 0;
}else{
h1 = height(tree->lChild);
h2 = height(tree->rChild);
if(h1>h2){
return h1+1;
}else{
return h2+1;
}
}
}
//求解二叉树每层节点的个数
void levelCount(BTree tree,int l,int num[]){
if(tree){
num[l]++;
levelCount(tree->lChild,l+1,num);
levelCount(tree->rChild,l+1,num);
}
}
//求解二叉树节点总数
int countTree(BTree tree){
int lCount,rCount;
if(tree == NULL){
return 0;
}
lCount = countTree(tree->lChild);
rCount = countTree(tree->rChild);
return lCount + rCount +1;
}

int main(){
BTree tree = createTree();
int i=0;
int countNum[10]={0,0,0,0,0,0,0,0,0,0},l=1,treeHeight,treeCount;//记录每层的节点数,l从1开始,树的深度

treeHeight = height(tree);
printf("\n此二叉树的深度为: %d\n",treeHeight);

treeCount = countTree(tree);
printf("此二叉树的节点总数为: %d\n",treeCount);

levelCount(tree,l,countNum);
printf("此二叉树各层的节点数为: ");
for(i=1;i<=treeHeight;i++){
printf("第%d层数目: %d, ",i,countNum[i]);
}
printf("\n\n");

printf("先序遍历此二叉树: ");
perOrder(tree);
printf("\n");

printf("中序遍历此二叉树: ");
inOrder(tree);
printf("\n");

printf("后序遍历此二叉树: ");
postOrder(tree);
printf("\n");

printf("层次遍历此二叉树: ");
levelOrder(tree);
printf("\n");
return 0;
}

四、实验结果截图

实验结果截图

文章作者: IT之旅
文章链接: https://www.meijindong.top/posts/2679181756.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 程序员在旅途
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论