💞💞 前言
hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
前面我们学习了二叉树的三种遍历前序、中序、后序，大家都还记得吗？
不记得的伙伴可以点击这里二叉树前、中、后序遍历进行查看哦~
🥳🥳今天我们将学习另外一种遍历——层序遍历。
层序遍历需要借助我们之前讲过的队列来实现，对队列有疑问的可以点击这里数据结构——lesson5栈和队列详解进行查看哦~
1.什么是层序遍历？
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
2.层序遍历的实现
// 层序遍历 void LevelOrder(BTNode* root);
实现之前我们还是简单创造一颗符合我们心意的二叉树：
BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->right = NULL; newnode->data = x; newnode->left = NULL; return newnode; } BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
二叉树形状如下：
//层序遍历 void LevelOrder(BTNode* root) { Queue qt;//创建队列 QueueInit(&qt);//队列初始化 if (root)//判断节点是否为空 QueuePush(&qt, root);//不为空入队列 while (!QueueEmpty(&qt))//判断队列是否为空 { BTNode* front = QueueFront(&qt);//不为空取队头值 printf("%d\n", front->data);//打印队头值 QueuePop(&qt);//删除队头值 if (front->left)//接着将左右子树的节点依次入队列 QueuePush(&qt, front->left); if (front->right) QueuePush(&qt, front->right); } QueueDestroy(&qt);//销毁队列 }
层序遍历利用队列先进先出的特点达到遍历的效果，以上就是实现层序遍历的函数啦~🥳🥳🥳
运行结果如下：
✨✨队列的实现在这里，记得使用前要声明哦~
也可以查看土土的博客二叉树前、中、后序遍历进行详细的学习。
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; typedef BTNode* QDataType; typedef struct QListNode { struct QListNode* pNext; QDataType data; }QNode; // 队列的结构 typedef struct Queue { QNode* front; QNode* rear; }Queue; // 初始化队列 void QueueInit(Queue* q) { assert(q); q->front = NULL; q->rear = NULL; } // 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点 if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = data; newnode->pNext = NULL; //队列为空的情况入队列 if (QueueEmpty(q)) { q->front = newnode; q->rear = newnode; return; } //队列不为空的情况入队列 else { q->rear->pNext = newnode; q->rear = newnode; return; } } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q));//判断队列非空 QNode* tmp = q->front;//先保存队头指针 q->front = tmp->pNext; free(tmp); } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q));//判断队列非空 return q->front->data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q));//判断队列非空 return q->rear->data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); assert(!QueueEmpty(q));//判断队列非空 int count = 0;//记录元素个数 QNode* cur = q->front; while (cur) { cur = cur->pNext; count++; } return count; } // 检测队列是否为空，如果为空返回true,非空返回false bool QueueEmpty(Queue* q) { assert(q); return q->front == NULL; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); //assert(!QueueEmpty(q));//判断队列非空 while (q->front) { QueuePop(q); } } //队列的特点是先进先出
3.结语
层序遍历关键点在于它对于队列的使用与理解，🥳🥳大家都学废了吗完结撒花~ 🎉🎉🎉
