目录
深度和广度优先遍历
层序遍历思路和代码实现
思路
代码实现
队列相关代码
层序遍历代码
深度和广度优先遍历
在之前的这篇博客二叉树的概念及三种遍历方法（C语言）_Perfectkn的博客-CSDN博客中，代码实现了二叉树的前中后序遍历，其实这种遍历叫深度优先遍历。即这种遍历和二叉树深度有关，访问到最深，递归回来继续访问其他的。
而层序遍历，就是广度优先遍历，即以根为主，一层一层往下遍历。借助队列的先进先出。核心思路就是：上一层带下一层。
层序遍历思路和代码实现
思路
借助队列先进先出的方法，以上面二叉树为例，先访问第一层根结点A，放到队列里面，此时判断队列不为空，因为有结点A。然后A出队列先遍历A。
再把下一层B和C放入队列，此时判断队列不为空。只取出结点B，一次只能取一个。
再把B的下一层D和E放入队列，此时判断队列不为空，队列有CDE。然后取出结点C。
结点C下面没有其他与之相连结点，此时队列还有DE，取出结点D。
D下面没有结点，此时队列还有E，取出结点E。E下一层也没有其他结点
最后判断队列为空，遍历结束。
即遍历结束标志：队列为空。
代码实现
队列相关代码
Queue.h
#pragma once#include <stdio.h>#include <stdbool.h>#include <assert.h>#include <stdlib.h>// 前置声明struct BinaryTreeNode;typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode{struct QueueNode* next;QDataType data;}QNode;typedef struct Queue{QNode* head;QNode* tail;}Queue;void QueueInit(Queue* pq);void QueueDestory(Queue* pq);// 队尾入void QueuePush(Queue* pq, QDataType x);// 队头出void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);
Queue.c
#include "Queue.h"void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}// 队尾入void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}// 队头出void QueuePop(Queue* pq){assert(pq);assert(pq->head);// 1、一个// 2、多个if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(pq->head);return pq->tail->data;}int QueueSize(Queue* pq){assert(pq);int size = 0;QNode* cur = pq->head;while (cur){++size;cur = cur->next;}return size;}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}
层序遍历代码
void LevelOrder(BTNode* root){Queue q;QueueInit(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)) //队列不为空则继续{BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c", front->data);if (front->left) //左边不为空{QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestory(&q);}
main函数直接调用LevelOrder();即可，括号里面加一个根结点，比如A。
