前序&中序&后序遍历：深度优先遍历dfs
层序遍历：广度优先遍历bfs
层序遍历概念&结构
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。
设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历的实现
层序遍历用队列实现，需要把队列的代码拷贝到多文件项目里面：单链表实现【队列】_单链表队列出队-CSDN博客
整体思路
- 把根节点放入队列
- 保存根节点在tmp，打印根节点（遍历），然后把根节点的左右孩子入队列
- 根节点出队列
- 循环上诉过程（父亲出的时候就带入父亲的左右孩子）
- 若为NULL则不入队列
- 达到一层一层遍历（层序遍历）
- 注意
- tmp保存的是树节点的地址
- 销毁的是队列的头节点（里面也是树节点的地址）
- 不会销毁树的节点
代码实现
测试代码在前面博文有：链式二叉树（1）-CSDN博客
//层序遍历 void LevelOrder(BTNode* root) { Queue pq; QueueInit(&pq); if(root) QueuePush(&pq, root); while (!QueueEmpty(&pq)) { BTNode* tmp = QueueFront(&pq);//队列头的元素 QueuePop(&pq);//出元素到队头 printf("%d ", tmp->data); if(tmp->left) QueuePush(&pq, tmp->left); if(tmp->right) QueuePush(&pq, tmp->right); } QueueDestroy(&pq); } int main() { BTNode* root = CreatBinaryTree(); LevelOrder(root); BinaryTreeDestory(root); root = NULL; return 0; }
图示理解
BT升级
若我们想要一层一层打印，怎样去一层一层打印？
整体思路
- 设置一个变量LeveSize记录每层的个数
- 每一层的数据个数，控制一层一层数据出队列
- 换行打印
代码实现
//BT升级换行打印 //层序遍历 void LevelOrder(BTNode* root) { Queue pq; QueueInit(&pq); if (root) QueuePush(&pq, root); int levesize = 1; while (!QueueEmpty(&pq)) { while (levesize--) { BTNode* tmp = QueueFront(&pq);//队列头的元素 QueuePop(&pq);//出元素到队头 printf("%d ", tmp->data); if (tmp->left) QueuePush(&pq, tmp->left); if (tmp->right) QueuePush(&pq, tmp->right); } printf("\n"); levesize = QueueSize(&pq);//队列里面的元素个数 } QueueDestroy(&pq); } int main() { BTNode* root = CreatBinaryTree(); LevelOrder(root); BinaryTreeDestory(root); root = NULL; return 0; }
图示理解 
应用
大家可以思考扫雷用递归去实现？QQ加好友的好友？
- 展开形式：广度优先遍历
- 展开形式：深度优先遍历
- 八度递归
- 层序遍历：加好友的好友（搜索算法）>>>>后面的算法篇章我们会介绍
题目
练习：请写出下面的前序/中序/后序/层序遍历
1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
答案：AADA
🙂感谢大家的阅读，若有错误和不足，欢迎指正。大家新年快乐！！
