前言
二叉树除了有前序遍历，中序遍历，后序遍历外，还有一个层序遍历，二叉树的层序遍历相比较于前三个稍微复杂一点，我们将在本篇文章详细分析一下层序遍历是怎么实现的。
一、层序遍历的概念
二叉树的层序遍历就跟它的名字一样，一层一层遍历。先遍历第一层的根结点，再从左往右遍历第二层，接着是第三层，直到遍历完整个二叉树为止。
emmmm，看起来层序遍历也不是很难嘛，但感觉…嘶，不知道咋实现啊哈哈🤣🤣🤣。那接下来我们就好好分析分析。
二、层序遍历的思想
其实有一个比较好想到的一点：先遍历根结点，然后再 准备 遍历根结点的孩子，每遍历到一个结点，就准备遍历其孩子，意思就是，我得找一个空间或者一个结构，能够保存我准备遍历的结点的顺序。那么什么结构可以呢，先准备遍历的要先遍历，后准备遍历的要后遍历。啊，有了，使用队列！
队列有个特点，数据都是先进先出的，非常符合我们层序遍历的思想。我们可以先让根结点入队列，队列每出一个数据，就让其左右孩子结点入队列，那么就能完美解决了。
三、代码实现
1.引入库函数头文件及函数声明
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> // 宏定义数据类型 typedef char BTDataType; // 链式二叉树结构体 typedef struct BinaryTreeNode { // 数据域 BTDataType data; // 指向左孩子的指针域 struct BinaryTreeNode* left; // 指向右孩子的指针域 struct BinaryTreeNode* right; }BTNode; // 通过前序遍历构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int* pi); // 二叉树销毁 void BinaryTreeDestroy(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); // 队列的数据类型，存的是 二叉树结构体指针 类型 typedef struct BinaryTreeNode* QDataType; // 队列的结构体 typedef struct QueueNode { // 队列的数据域 QDataType val; // 队列的指针域 struct QueueNode* next; }QNode; // 传参结构体 typedef struct Queue { // 有一个指向队列的头结点(队头)的指针 QNode* phead; // 有一个指向队列的尾节点(队尾)的指针 QNode* ptail; // 队列的元素个数 int size; }Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 在队尾插入 void QueuePush(Queue* pq, QDataType x); // 在队头弹出 void QueuePop(Queue* pq); // 查询队头元素 QDataType QueueFront(Queue* pq); // 判断队列是否为空 bool QueueEmpty(Queue* pq);
2.其他函数实现
// 通过前序遍历构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { // 如果数组第*pi的值为‘#’，说明遇到了空结点，说明该结点不存在 if (a[*pi] == '#') { // 准备查看数组的下一个元素 ++(*pi); // 返回空 return NULL; } // 如果当前值不为空 // 为当前结点开辟一个新的二叉树结构体大小的空间 BTNode* root = (BTNode*)malloc(sizeof(BTNode)); // 开辟空间失败 if (!root) { // 弹出反馈 perror("malloc fail"); // 退出程序 exit(-1); } // 开辟空间成功 // 将当前的数组的值赋值给该结点的数据域，并让*pi增加1，准备查看下一个数组元素 root->data = a[(*pi)++]; // 递归传回该结点的左孩子的地址 root->left = BinaryTreeCreate(a, pi); // 递归传回该结点的右孩子的地址 root->right = BinaryTreeCreate(a, pi); // 返回当前结点的地址 return root; // 二叉树销毁 void BinaryTreeDestroy(BTNode* root) { // 空结点直接返回 if (!root) return; // 递归左孩子 BinaryTreeDestroy(root->left); // 递归右孩子 BinaryTreeDestroy(root->right); // 销毁根结点 free(root); } // 队列接口函数 // 队列初始化 // 传入传参结构体成员的地址 void QueueInit(Queue* pq) { // pq是指向传参结构体的指针，只要结构体创建了，那pq就不可能为空，为空说明传参错误或者结构体没创建 assert(pq); // 让指向首元结点的头指针和指向尾结点的尾指针置空，说明队列为空 pq->phead = pq->ptail = NULL; // 队列目前有效数据为0 pq->size = 0; } // 销毁队列 void QueueDestroy(Queue* pq) { // pq不可能为空，可以断言一下以免出现小差错 assert(pq); // 如果pq指向的结构体里面的phead不为空，即存在结点 while (pq->phead) { // 创建一个临时指针变量指向首元结点 QNode* tmp = pq->phead; // 让phead指向第二个结点 pq->phead = pq->phead->next; // 释放首元结点空间 free(tmp); // 释放空间后指针置空是好习惯 tmp = NULL; } // 最后没有结点的时候，把尾结点置空 pq->ptail = NULL; // 让有效数据大小为0 pq->size = 0; } // 入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); // 为新结点开辟空间 QNode* newNode = (QNode*)malloc(sizeof(QNode)); // 开辟失败时 if (newNode == NULL) { // 弹出反馈 perror("malloc fail"); // 终止程序 exit(-1); } // 为新结点赋值 newNode->val = x; newNode->next = NULL; // 当队列为空时 if (pq->ptail == NULL) { // 头指针指向新结点 pq->phead = pq->ptail = newNode; } // 当队列非空时 else { // 原尾结点的指针域指向新结点 pq->ptail->next = newNode; // 尾指针指向新结点 pq->ptail = newNode; } // 队列的有效个数+1 ++pq->size; } // 出队列 void QueuePop(Queue* pq) { assert(pq); // 队列为空不能删除 assert(pq->phead); // 临时指针指向首元结点 QNode* tmp = pq->phead; // 当队列中只有一个结点时 if (pq->phead == pq->ptail) { // 将两个指针置空 pq->phead = pq->ptail = NULL; } // 当队列中不止一个结点时 else { // 让头结点指向第二个结点 pq->phead = pq->phead->next; } // 有效数据个数-1 --pq->size; // 释放原首元结点的空间 free(tmp); // 释放空间后指针置空 tmp = NULL; } // 查询队头数据 QDataType QueueFront(Queue* pq) { assert(pq); // 队列不为空才有队头数据 assert(pq->phead); // 根据头指针找到队头数据 return pq->phead->val; } // 判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); // 返回队列有效数据的个数是否等于0来判断队列是否为空 return pq->size == 0; }
这里需要注意的是，队列内存放的是指向链式二叉树结构体的指针，所以在宏定义队列的数据类型的时候，要将链式二叉树的结构体名称宏定义为 QDataType 。
3.层序遍历函数
void BinaryTreeLevelOrder(BTNode* root) { // 创建一个队列 Queue q; // 初始化队列 QueueInit(&q); // 如果根结点存在，则将根结点入队 if (root) QueuePush(&q, root); // 如果队列非空 while (!QueueEmpty(&q)) { // 获取队头元素 BTNode* front = QueueFront(&q); // 打印队头元素 printf("%c", front->data); // 如果左孩子非空 if (front->left) // 左孩子入队 QueuePush(&q, front->left); // 如果右孩子非空 if (front->right) // 右孩子入队 QueuePush(&q, front->right); // 弹出队头元素 QueuePop(&q); } // 队列已经空了，说明遍历结束，销毁队列 QueueDestroy(&q); }
该函数的主要思想就是，每次让队头元素出队列的时候，让其左右孩子入队列，由于左孩子先比右孩子入队列，所以左孩子就比右孩子出队列，左孩子的孩子就会先入队列。但是一旦父结点出了队列，就会被销毁，就无法借其找到其左孩子和右孩子，所以在出队列前需要先入队列，再将队头元素出队列。
4.主函数
int main() { // 创造二叉树数据 char a[] = "ABD##E#H##CF##G##"; int b = 0; // 通过前序遍历的方式读取数组数据建立二叉树 BTNode* root = BinaryTreeCreate(a, &b); printf("二叉树的层序遍历："); // 层序遍历 BinaryTreeLevelOrder(root); printf("\n"); // 销毁二叉树 BinaryTreeDestroy(root); // 销毁空间后指针置空 root = NULL; return 0; }
5.结果演示
我们通过数组构建的链式二叉树长这样：
根据层序遍历的性质，我们可以求出，层序遍历的结果应该是：ABCDEFGH 。来看看结果：
完美。
总结
层序遍历主要就是利用队列结构，通过有序的入队列和出队列来达成层序遍历的效果，虽然相比较于二叉树的前，中，后序遍历来说有点不一样，但是在理解了队列的结构和实现，搭配一下构建二叉树，就能轻松写出层序遍历。
博主水品有限，若是发现文章中出现错误，还请大家不吝赐教。谢谢。
