-
数据结构题型14-二叉树的遍历
参考博客： 二叉树遍历方法——前、中、后序遍历（图解）1、先序遍历
2、中序遍历
3、后序遍历
4、非递归遍历
5、层次遍历
6、C语言版本(参考)
C语言版本，参考博客：二叉树遍历方法——前、中、后序遍历（图解）
#define _CRT_SECURE_NO_WARNINGS /*引入头文件*/ #include#include #include #include #define Maxsize 100 typedef char Elemtype; typedef struct BiTNode /*定义二叉树链式存储结构*/ { Elemtype data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; typedef struct Stack /*定义堆栈存储结构*/ { BiTree data[Maxsize]; int top; }SqStack; /*设置字体颜色*/ void color(short x); /*测试菜单*/ int TestMeanu(void); /*初始化堆栈*/ void InitStack(SqStack* S); /*判断栈空*/ bool IsEmpty(SqStack S); /*入栈*/ bool Push(SqStack* S, BiTree x); /*出栈*/ bool Pop(SqStack* S, BiTree *x); void CreateBiTree1(BiTree* T); /*二叉树的遍历递归算法*/ /*先序遍历*/ void PreOrder(BiTree T); /*中序遍历*/ void InOrder(BiTree T); /*后序遍历*/ void PostOrder(BiTree T); /*输出树结点*/ void visit(BiTree T); /*二叉树的遍历非递归算法*/ /*先序遍历*/ void PreOrder2(BiTree T); /*中序遍历*/ void InOrder2(BiTree T); /*后序遍历*/ /*利用标志*/ void PostOrder3(BiTree T); int main(void) { BiTree T = NULL; printf("请输入以下字符串创建二叉树!!!\n"); printf("ABD##EG###C#F##\n"); CreateBiTree1(&T); while (1) { int choice = TestMeanu(); switch (choice) { case 0: exit(0); break; case 1: printf("1、先序遍历\n"); printf("2、中序遍历\n"); printf("3、后序遍历\n"); printf("请输入要遍历的方式："); int choice1; scanf("%d", &choice1); color(11); switch (choice1) { case 1: PreOrder(T); break; case 2: InOrder(T); break; case 3: PostOrder(T); break; default: printf("输入不规范，请规范输入！！！！\n"); } break; case 2: printf("1、先序遍历\n"); printf("2、中序遍历\n"); printf("3、后序遍历\n"); printf("请输入要遍历的方式："); int choice2; scanf("%d", &choice2); color(11); switch (choice2) { case 1: PreOrder2(T); break; case 2: InOrder2(T); break; case 3: PostOrder3(T); break; default: printf("输入不规范，请规范输入！！！！\n"); } } } return 0; } void CreateBiTree1(BiTree* T) { Elemtype ch; scanf("%c", &ch); if (ch == '#') *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode)); if (*T == NULL) exit(false); (*T)->data = ch; (*T)->lchild = (*T)->rchild = NULL; CreateBiTree1(&( (*T)->lchild )); //构建左子树 CreateBiTree1(&( (*T)->rchild)); //构建右子树 } } /*设置字体颜色*/ void color(short x) { /* 颜色函数SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),前景色 | 背景色 | 前景加强 | 背景加强); 前景色：数字0-15 或 FOREGROUND_XXX 表示 （其中XXX可用BLUE、RED、GREEN表示） 前景加强：数字8 或 FOREGROUND_INTENSITY 表示 背景色：数字16 32 64 或 BACKGROUND_XXX 三种颜色表示 背景加强： 数字128 或 BACKGROUND_INTENSITY 表示 主要应用：改变指定区域字体与背景的颜色 前景颜色对应值： 0=黑色 8=灰色 1=蓝色 9=淡蓝色 十六进制 2=绿色 10=淡绿色 0xa 3=湖蓝色 11=淡浅绿色 0xb 4=红色 12=淡红色 0xc 5=紫色 13=淡紫色 0xd 6=黄色 14=淡黄色 0xe 7=白色 15=亮白色 0xf 也可以把这些值设置成常量。 */ if (x >= 0 && x <= 15)//参数在0-15的范围颜色 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x); //只有一个参数，改变字体颜色 else//默认的颜色白色 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); } int TestMeanu(void) { color(16); int choice; printf("欢迎使用二叉树三种遍历算法测试程序!!!!!\n"); printf("0、退出测试程序\n"); printf("1、二叉树的递归遍历算法\n"); printf("2、二叉树的非递归遍历算法\n"); printf("请输入你需要测试的功能："); scanf("%d", &choice); return choice; } void InitStack(SqStack* S) { S->top = -1; } bool IsEmpty(SqStack S) { if (S.top == -1) return true; else return false; } bool Push(SqStack* S, BiTree x) { if (S->top == Maxsize - 1) return false; S->data[++(S->top)] = x; return true; } bool Pop(SqStack* S, BiTree* x) { if (S->top == -1) return false; *x = S->data[(S->top)--]; return true; } /*二叉树遍历的递归算法*/ /*先序遍历*/ void PreOrder(BiTree T) { if (T != NULL) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } /*中序遍历*/ void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } /*后序遍历*/ void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } /*输出树结点*/ void visit(BiTree T) { printf("树结点的值：%c\n", T->data); } /*二叉树的非递归算法*/ /*先序遍历*/ void PreOrder2(BiTree T) { SqStack S; InitStack(&S); BiTree p = T; while (p || !IsEmpty(S)) { if (p) { visit(p); Push(&S, p); p = p->lchild; } else { Pop(&S, &p); p = p->rchild; } } } /*中序遍历*/ void InOrder2(BiTree T) { SqStack S; InitStack(&S); BiTree p = T; while (p || !IsEmpty(S)) { if (p) { Push(&S, p); p = p->lchild; } else { Pop(&S, &p); visit(p); p = p->rchild; } } } /*利用标志*/ struct stack { BiTree t; int tag; // 标志 }; void PostOrder3(BiTree T) { struct stack s[Maxsize]; int top = -1; while (T != NULL || top >= 0) { while (T != NULL) { s[++top].t = T; s[top].tag = 0; T = T->lchild; // 沿左分支向下 } while (top != -1 && s[top].tag == 1) visit(s[top--].t); // 退栈 if (top != -1) { s[top].tag = 1; // 标志访问过右子树被访问 T = s[top].t->rchild; // 沿右分支向下遍历 } } } - 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
7、C++语言版本
#define _CRT_SECURE_NO_WARNINGS /*引入头文件*/ #include//引入头文件 #include using namespace std; #define Maxsize 100 typedef char Elemtype; typedef struct BiTNode /*定义二叉树链式存储结构*/ { Elemtype data; struct BiTNode* lchild, * rchild; }BiTNode, * BiTree; typedef struct Stack /*定义堆栈存储结构*/ { BiTree data[Maxsize]; int top; }SqStack; /*设置字体颜色*/ void color(short x); /*测试菜单*/ int TestMeanu(void); /*初始化堆栈*/ void InitStack(SqStack &S); /*判断栈空*/ bool IsEmpty(SqStack S); /*入栈*/ bool Push(SqStack &S, BiTree x); /*出栈*/ bool Pop(SqStack &S, BiTree &x); void CreateBiTree1(BiTree &T); /*二叉树的遍历递归算法*/ /*先序遍历*/ void PreOrder(BiTree T); /*中序遍历*/ void InOrder(BiTree T); /*后序遍历*/ void PostOrder(BiTree T); /*输出树结点*/ void visit(BiTree T); /*二叉树的遍历非递归算法*/ /*先序遍历*/ void PreOrder2(BiTree T); /*中序遍历*/ void InOrder2(BiTree T); /*后序遍历*/ /*利用标志*/ void PostOrder3(BiTree T); int main(void) { BiTree T = NULL; printf("请输入以下字符串创建二叉树!!!\n"); printf("ABD##EG###C#F##\n"); CreateBiTree1(T); while (1) { int choice = TestMeanu(); switch (choice) { case 0: exit(0); break; case 1: printf("1、先序遍历\n"); printf("2、中序遍历\n"); printf("3、后序遍历\n"); printf("请输入要遍历的方式："); int choice1; scanf("%d", &choice1); color(11); switch (choice1) { case 1: PreOrder(T); break; case 2: InOrder(T); break; case 3: PostOrder(T); break; default: printf("输入不规范，请规范输入！！！！\n"); } break; case 2: printf("1、先序遍历\n"); printf("2、中序遍历\n"); printf("3、后序遍历\n"); printf("请输入要遍历的方式："); int choice2; scanf("%d", &choice2); color(11); switch (choice2) { case 1: PreOrder2(T); break; case 2: InOrder2(T); break; case 3: PostOrder3(T); break; default: printf("输入不规范，请规范输入！！！！\n"); } } } return 0; } void CreateBiTree1(BiTree &T) { Elemtype ch; scanf("%c", &ch); if (ch == '#') T = NULL; else { T = (BiTree)malloc(sizeof(BiTNode)); if (T == NULL) exit(false); T->data = ch; T->lchild = T->rchild = NULL; CreateBiTree1(T->lchild); //构建左子树 CreateBiTree1(T->rchild); //构建右子树 } } /*设置字体颜色*/ void color(short x) { /* 颜色函数SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),前景色 | 背景色 | 前景加强 | 背景加强); 前景色：数字0-15 或 FOREGROUND_XXX 表示 （其中XXX可用BLUE、RED、GREEN表示） 前景加强：数字8 或 FOREGROUND_INTENSITY 表示 背景色：数字16 32 64 或 BACKGROUND_XXX 三种颜色表示 背景加强： 数字128 或 BACKGROUND_INTENSITY 表示 主要应用：改变指定区域字体与背景的颜色 前景颜色对应值： 0=黑色 8=灰色 1=蓝色 9=淡蓝色 十六进制 2=绿色 10=淡绿色 0xa 3=湖蓝色 11=淡浅绿色 0xb 4=红色 12=淡红色 0xc 5=紫色 13=淡紫色 0xd 6=黄色 14=淡黄色 0xe 7=白色 15=亮白色 0xf 也可以把这些值设置成常量。 */ if (x >= 0 && x <= 15)//参数在0-15的范围颜色 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x); //只有一个参数，改变字体颜色 else//默认的颜色白色 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); } int TestMeanu(void) { color(16); int choice; printf("欢迎使用二叉树三种遍历算法测试程序!!!!!\n"); printf("0、退出测试程序\n"); printf("1、二叉树的递归遍历算法\n"); printf("2、二叉树的非递归遍历算法\n"); printf("请输入你需要测试的功能："); scanf("%d", &choice); return choice; } void InitStack(SqStack &S) { S.top = -1; } bool IsEmpty(SqStack S) { if (S.top == -1) return true; else return false; } bool Push(SqStack &S, BiTree x) { if (S.top == Maxsize - 1) return false; S.data[++S.top] = x; return true; } bool Pop(SqStack &S, BiTree &x) { if (S.top == -1) return false; x = S.data[S.top--]; return true; } /*二叉树遍历的递归算法*/ /*先序遍历*/ void PreOrder(BiTree T) { if (T != NULL) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } /*中序遍历*/ void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } /*后序遍历*/ void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } /*输出树结点*/ void visit(BiTree T) { printf("树结点的值：%c\n", T->data); } /*二叉树的非递归算法*/ /*先序遍历*/ void PreOrder2(BiTree T) { SqStack S; InitStack(S); BiTree p = T; while (p || !IsEmpty(S)) { if (p) { visit(p); Push(S, p); p = p->lchild; } else { Pop(S, p); p = p->rchild; } } } /*中序遍历*/ void InOrder2(BiTree T) { SqStack S; InitStack(S); BiTree p = T; while (p || !IsEmpty(S)) { if (p) { Push(S, p); p = p->lchild; } else { Pop(S, p); visit(p); p = p->rchild; } } } /*利用标志*/ struct stack { BiTree t; int tag; // 标志 }; void PostOrder3(BiTree T) { struct stack s[Maxsize]; int top = -1; while (T != NULL || top >= 0) { while (T != NULL) { s[++top].t = T; s[top].tag = 0; T = T->lchild; // 沿左分支向下 } while (top != -1 && s[top].tag == 1) visit(s[top--].t); // 退栈 if (top != -1) { s[top].tag = 1; // 标志访问过右子树被访问 T = s[top].t->rchild; // 沿右分支向下遍历 } } } - 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
-
相关阅读:
【数据结构】C++实现红黑树
PHP连接达梦数据库DM8（Window）
【数据结构】带头双向循环链表
ExtJS-Theme（主题配置）
什么蓝牙耳机好用？音质好佩戴舒适蓝牙耳机推荐
在线客服系统源码开发实战总结：需求分析及前端代码基本技术方案
Debezium系列之：IDEA集成词法和语法分析ANTLR，查看debezium支持的ddl、dml等语句
【分享】“小鹅通“在集简云平台集成应用的常见问题与解决方案
Kettle安装初始化问题
前端环境 本机可切换node多版本 问题源头是node使用的高版本
- 原文地址：https://blog.csdn.net/qq_41735476/article/details/133669515
