前言
承接上节,树的非递归三种遍历我们使用了栈,今天讲解的树的层序遍历,我们需要使用另外一种数据结构——队列
我们先简单的回忆一下什么是队列
1.队列
概念:一端入元素,另一端出元素的线性表
一端:队尾
另一端:队头
线性表:顺序表,链表
接下来我们就来完成树的层序遍历吧!
1.根结点入队
2.打印根结点的值并判断当前结点是否有左右子结点
若有,则左右依次入队,此时出队一个元素,并访问其左右子结点
若无,则遍历结束
void LevelOrder(TreeNode* T) {//二叉树的层序遍历if (T == NULL)return;TreeNode* Queue[MaxSize];//队列int front, rear;front = rear = 0;//队空TreeNode* p = NULL;//遍历指针//1.让根节点入队rear = (rear + 1) % MaxSize;Queue[rear] = T;while (front != rear) {front = (front + 1) % MaxSize;p = Queue[front];printf("%d ", p->data);if (p->left != NULL) {//判读左孩子rear = (rear + 1) % MaxSize;Queue[rear] = p->left;}if (p->right != NULL) {//判断右孩子rear = (rear + 1) % MaxSize;Queue[rear] = p->right;}}}
完整代码如下
#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#define MaxSize 20typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;}TreeNode;void LevelOrder(TreeNode* T) {//二叉树的层序遍历if (T == NULL)return;TreeNode* Queue[MaxSize];//队列int front, rear;front = rear = 0;//队空TreeNode* p = NULL;//遍历指针//1.让根节点入队rear = (rear + 1) % MaxSize;Queue[rear] = T;while (front != rear) {front = (front + 1) % MaxSize;p = Queue[front];printf("%d ", p->data);if (p->left != NULL) {//判读左孩子rear = (rear + 1) % MaxSize;Queue[rear] = p->left;}if (p->right != NULL) {//判断右孩子rear = (rear + 1) % MaxSize;Queue[rear] = p->right;}}}int main() {TreeNode n1;TreeNode n2;TreeNode n3;TreeNode n4;n1.data = 1;n2.data = 3;n3.data = 5;n4.data = 7;n1.left = &n2;n1.right = &n3;n2.left = &n4;n2.right = NULL;n3.left = NULL;n3.right = NULL;n4.left = NULL;n4.right = NULL;printf("层序遍历为:");LevelOrder(&n1);return 0;}
李白说得好啊:这篇文章写的这真不错,确定不给个关注&点赞!