热门标签
热门文章
- 1数据结构之 Map 和 Set_字符串 包含 map
- 2房地产画册制作成手机在线翻页效果
- 3Win10电脑 打开SMB协议共享文件，手机端查看_win10电脑smb服务怎么看
- 42024华为软件测试笔试面试真题，抓紧收藏不然就看不到了
- 5基于springboot的物流快递管理系统的设计与实现_快递物流管理系统设计
- 6使用OpenCV进行人脸检测和戴墨镜特效实战（附Python源码）_python 捕捉人脸,添加特效
- 7[C++] 哈希详解_c++哈希介绍
- 8Android高德地图定位实现签到打卡功能（全网最详细+收藏）_androidd1高德地图电子围栏签到
- 9后端架构师技术图谱_从程序员到架构师 pdf 脚本之家
- 10仿 trello php,分享|4 个开源的可自行托管的 Trello 替代品
当前位置: article > 正文
二叉树的遍历总结_queue
作者：2023面试高手 | 2024-04-30 20:27:45
赞
踩
queue
二叉树的遍历总结
二叉树结构
用二叉链表来存储二叉树
typedef struct BiTNode //二叉树
{
int data; //结点数值
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
- 1
- 2
- 3
- 4
- 5
- 6
建立二叉树
输入一个数组，以层次遍历的顺序进行建树，规定数组元素都大于0。当数组元素为-1时，表示该结点为空。
举个例子，比如数组大小为 12，数组元素为
3 5 6 8 -1 2 7 8 1 34 -1 65
- 1
则建立的二叉树为
建立二叉树的代码：
queue<BiTree> q;//辅助队列 void createBiTree() { int n; int a[1010]; //读取输入 scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } //建立二叉树 int counts = 1; for (int i = 1; i <= n; i++) { BiTree tmp = (BiTree)malloc(sizeof(BiTNode)); tmp = q.front(); q.pop(); tmp->data = a[i];//赋值 tmp->lchild = (BiTree)malloc(sizeof(BiTNode)); tmp->rchild = (BiTree)malloc(sizeof(BiTNode)); if(a[i] != -1) { tmp->num = counts;//给非空结点编号 counts++; q.push(tmp->lchild);//后面的元素必须挂在非空结点下面 q.push(tmp->rchild); } else //空结点标记 { tmp->lchild->data = -1; tmp->rchild->data = -1; } } while(!q.empty())//清除队列中的空结点 { q.front()->data = -1; q.pop(); } }
- 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
层次遍历
访问结点
- 如果该结点不为空，输出该结点的值
void visit(BiTree T)
{
if(T->data != -1)
printf("%d ", T->data);
}
- 1
- 2
- 3
- 4
- 5
层次遍历
- 先把二叉树的根结点入队。然后队首元素出队，访问出队结点。若它有左子树，则将左子树根结点入队；若它有右子树，右子树根结点入队。然后继续出队，访问出队结点······重复这个过程，直到队列为空
void LevelOrder(BiTree T) { while(!q.empty())//初始化队列 { q.pop(); } q.push(T);//根结点入队 while(!q.empty()) { BiTree tmp = q.front(); q.pop();//队头结点出队 visit(tmp);//访问出队结点 if(tmp->lchild->data != -1) q.push(tmp->lchild); if(tmp->rchild->data != -1) q.push(tmp->rchild); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
递归的三种遍历
先序遍历，也叫前序遍历
- 访问根结点
- 先序遍历左子树
- 先序遍历右子树
void PreOrder(BiTree T)
{
if(T->data != -1)//结点非空
{
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
中序遍历
- 中序遍历左子树
- 访问根结点
- 中序遍历右子树
void InOrder(BiTree T)
{
if(T->data != -1)//结点非空
{
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
后序遍历
- 后序遍历左子树
- 后序遍历右子树
- 访问根结点
void PostOrder(BiTree T)
{
if(T->data != -1)//结点非空
{
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
非递归的三种遍历
中序遍历
- 沿着根的左孩子，依次入栈，直到左孩子为空
- 栈顶元素出栈并访问，若其右孩子为空，继续执行 2
- 若其右孩子不空，将右子树转向执行 1
void InOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; while((p->data != -1) || (!s.empty()))//p不空或栈不空 { if(p->data != -1) //非空结点 { s.push(p); //入栈，一路向左 p = p->lchild; } else //出栈，转向出栈结点的右子树 { p = s.top(); s.pop(); visit(p); p = p->rchild; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
先序遍历和中序遍历很相似，区别在于扫描结点时先访问结点，再将其入栈
void PreOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; while((p->data != -1) || (!s.empty()))//p不空或者栈不空 { if(p->data != -1) //结点非空 { visit(p); //先访问结点，再入栈 s.push(p); p = p->lchild; } else { p = s.top(); //出栈，转向出栈结点的右子树 s.pop(); p = p->rchild; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
后序遍历
-
初始时依次扫描根结点的所有左侧结点并将它们全部依次进栈
-
读栈顶元素，若其右孩子不为空且未被访问过，将右子树转向 1
-
否则，栈顶元素出栈并访问
注意：
在第二步中，需要分清返回时是从左子树返回的还是右子树返回的，设置一个辅助指针 r，指向最近访问过的结点。
每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，需要将 p 置空。
void PostOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; BiTree r = NULL; //r指针记录最后一个访问的结点 BiTree kong = (BiTree)malloc(sizeof(BiTNode));//空指针，方便p置空 kong->data = -1; while((p->data != -1) || (!s.empty()))//p不空或栈不空 { if(p->data != -1) //非空结点 { s.push(p); //入栈，一路向左 p = p->lchild; } else { p = s.top(); //访问栈顶元素（不出栈） if((p->rchild->data != -1) && (p->rchild != r))//右子树存在且未被访问过 { p = p->rchild; //转向右子树 s.push(p); p = p->lchild; //仍然一路向左 } else //否则，弹出栈顶元素并访问 { s.pop(); visit(p); r = p; //记录最近访问过的结点 p = kong; //结点访问完后，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
- 34
- 35
完整代码
#include <cstdio> #include <cstdlib> #include <queue> #include <stack> using namespace std; typedef struct BiTNode //二叉树 { int data; //结点数值 struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode, *BiTree; queue<BiTree> q;//辅助队列 void createBiTree(); //层次序列建立二叉树 void visit(BiTree R); //访问结点 void LevelOrder(BiTree R); //层次遍历 /* 递归的先序、中序、后序遍历 */ void PreOrder(BiTree R); void InOrder(BiTree R); void PostOrder(BiTree R); /* 非递归的先序、中序、后序遍历 */ void PreOrder2(BiTree R); void InOrder2(BiTree R); void PostOrder2(BiTree R); int main() { BiTree bit; bit = (BiTree)malloc(sizeof(BiTNode)); q.push(bit); createBiTree(); //层次遍历 printf("\n层次遍历： "); LevelOrder(bit); printf("\n\n"); /* 递归 */ printf("递归\n"); printf("先序遍历： "); PreOrder(bit); printf("\n"); printf("中序遍历： "); InOrder(bit); printf("\n"); printf("后序遍历： "); PostOrder(bit); printf("\n\n"); /* 非递归 */ printf("非递归\n"); printf("先序遍历： "); PreOrder2(bit); printf("\n"); printf("中序遍历： "); InOrder2(bit); printf("\n"); printf("后序遍历： "); PostOrder2(bit); printf("\n"); return 0; } void createBiTree() { int n; int a[1010]; //读取输入 scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } //建立二叉树 for (int i = 1; i <= n; i++) { BiTree tmp = (BiTree)malloc(sizeof(BiTNode)); tmp = q.front(); q.pop(); tmp->data = a[i];//赋值 tmp->lchild = (BiTree)malloc(sizeof(BiTNode)); tmp->rchild = (BiTree)malloc(sizeof(BiTNode)); if(a[i] != -1) { q.push(tmp->lchild);//后面的元素必须挂在非空结点下面 q.push(tmp->rchild); } else //空结点标记 { tmp->lchild->data = -1; tmp->rchild->data = -1; } } while(!q.empty())//清除队列中的空结点 { q.front()->data = -1; q.pop(); } } void visit(BiTree T) { if(T->data != -1) printf("%d ", T->data); } void LevelOrder(BiTree T) { while(!q.empty())//初始化队列 { q.pop(); } q.push(T);//根结点入队 while(!q.empty()) { BiTree tmp = q.front(); q.pop();//队头结点出队 visit(tmp);//访问出队结点 if(tmp->lchild->data != -1) q.push(tmp->lchild); if(tmp->rchild->data != -1) q.push(tmp->rchild); } } void PreOrder(BiTree T) { if(T->data != -1)//结点非空 { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T) { if(T->data != -1)//结点非空 { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } void PostOrder(BiTree T) { if(T->data != -1)//结点非空 { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } void PreOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; while((p->data != -1) || (!s.empty()))//p不空或者栈不空 { if(p->data != -1) //结点非空 { visit(p); //先访问结点，再入栈 s.push(p); p = p->lchild; } else { p = s.top(); //出栈，转向出栈结点的右子树 s.pop(); p = p->rchild; } } } void InOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; while((p->data != -1) || (!s.empty()))//p不空或栈不空 { if(p->data != -1) //非空结点 { s.push(p); //入栈，一路向左 p = p->lchild; } else //出栈，转向出栈结点的右子树 { p = s.top(); s.pop(); visit(p); p = p->rchild; } } } void PostOrder2(BiTree T) { stack<BiTree> s; BiTree p = T; BiTree r = NULL; //r指针记录最后一个访问的结点 BiTree kong = (BiTree)malloc(sizeof(BiTNode));//空指针，方便p置空 kong->data = -1; while((p->data != -1) || (!s.empty()))//p不空或栈不空 { if(p->data != -1) //非空结点 { s.push(p); //入栈，一路向左 p = p->lchild; } else { p = s.top(); //访问栈顶元素（不出栈） if((p->rchild->data != -1) && (p->rchild != r))//右子树存在且未被访问过 { p = p->rchild; //转向右子树 s.push(p); p = p->lchild; //仍然一路向左 } else //否则，弹出栈顶元素并访问 { s.pop(); visit(p); r = p; //记录最近访问过的结点 p = kong; //结点访问完后，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
- 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
程序运行结果如下：
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/515035
推荐阅读
相关标签
