二叉树层序遍历（c语言，非递归）

article/2025/9/18 18:16:33

层序遍历的作用是将二叉树，从上到下，从左到右依次遍历。如下图遍历的结果是A->B->C->D->E->F->G->H。其实，这就相当于族谱一样，从辈分大到小遍历（从祖宗到孙子）狗头保命。

那么，该如何实现呢，接下来我们运用队列的知识，用入队列，出队列的方式来解决。

1.思路

2.具体实现

（1）准备步骤

（2）队列源码（Queue.h 和 Queue.c)

（3）层序遍历实现

（4）层序遍历源码

1.思路

（1）将A入队列

（2）判断队列是否为空，不为空就将A出队列，再将A的”孩子“入队列。

（3）判空，将B出队列，将B的“孩子”入队列。

(4)判空，将C出队列，将C的“孩子”入队列。

（5）判空，将D出队列，将D的“孩子”入队列（“孩子”为空则不进队列）

。。。。。。。。（步骤同理）

（6）最后，队列为空结束遍历。

2.具体实现

（1）准备步骤

因为c语言不像c++一样有队列的库函数，所以就需要我们自己来实现一个队列。下面我给大家写了一个队列（才，才不是为了给你们用的呢.傲娇脸）。

（2）队列源码（Queue.h 和 Queue.c)

下面只有层序遍历要使用到的函数（绝对不是因为懒.jpg）

Queue.h

注意，头文件一定要包含#include”tree.h",包含二叉树的“tree.h"以免下面定义队列元素出错（下面，会写"tree.h"文件的先不要着急。

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>#include"tree.h"//包含二叉树的“tree.h"以免下面定义队列元素出错typedef BTNode* Type;//定义队列中元素类型为二叉树节点类型typedef struct QueueNode
{struct QueueNode* next;Type data;
}Qnode;typedef struct Queue
{Qnode* head;Qnode* tail;int size;
}Queue;//初始化
void Queue_init(Queue* pq);
//入队列
void Queue_push(Queue* pq, Type x);
//出队列
void Queue_pop(Queue* pq);
//取队首
Type Queue_front(Queue* pq);
//判空
bool Queue_empty(Queue* pq);

Queue.c

#include"Queue.h"//初始化
void Queue_init(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
//入队列
void Queue_push(Queue* pq, Type x)
{assert(pq);Qnode* newNode = (Qnode*)malloc(sizeof(Qnode));if (newNode == NULL){perror("malloc");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;}pq->size++;
}
//出队列
void Queue_pop(Queue* pq)
{assert(pq);assert(!Queue_empty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{Qnode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}pq->size--;
}
//队首
Type Queue_front(Queue* pq)
{assert(pq);assert(!Queue_empty(pq));return pq->head->data;
}//判空
bool Queue_empty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

（3）层序遍历实现

tree.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef char TreeType;typedef struct BinaryTreeNode
{TreeType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* TreeCreate();
// 二叉树销毁
void TreeDestory(BTNode* root);
// 层序遍历
void TreeLevelOrder(BTNode* root);

tree.c

注意，这里也一定要有#include“Queue.h",否则队列就无法正常使用。

我用了最粗暴的创建方法（让人见了直呼好家伙）

#include"tree.h"
#include"Queue.h"//构建二叉树 （最粗暴的创建方法）
BTNode* TreeCreate()
{BTNode* nA = (BTNode*)malloc(sizeof(BTNode));assert(nA);BTNode* nB = (BTNode*)malloc(sizeof(BTNode));assert(nB);BTNode* nC = (BTNode*)malloc(sizeof(BTNode));assert(nC);BTNode* nD = (BTNode*)malloc(sizeof(BTNode));assert(nD);BTNode* nE = (BTNode*)malloc(sizeof(BTNode));assert(nE);BTNode* nF = (BTNode*)malloc(sizeof(BTNode));assert(nF);BTNode* nG = (BTNode*)malloc(sizeof(BTNode));assert(nG);BTNode* nH = (BTNode*)malloc(sizeof(BTNode));assert(nH);nA->data = 'A';nB->data = 'B';nC->data = 'C';nD->data = 'D';nE->data = 'E';nF->data = 'F';nG->data = 'G';nH->data = 'H';nA->left = nB;nA->right = nC;nB->left = nD;nB->right = nE;nC->left = nF;nC->right = nG;nD->left = NULL;nD->right = NULL;nE->left = NULL;nE->right = nH;nF->left = NULL;nF->right = NULL;nG->left = NULL;nG->right = NULL;nH->left = NULL;nH->right = NULL;return nA;
}// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}// 层序遍历
void TreeLevelOrder(BTNode* root)
{Queue q;Queue_init(&q);if (root != NULL)Queue_push(&q, root);while (!Queue_empty(&q))//判空{BTNode* front = Queue_front(&q);//让front保存要出队列的节点Queue_pop(&q);printf("%c ", front->data);//下一层入队列（”孩子“入队列）if (front->left)Queue_push(&q, front->left);if (front->right)Queue_push(&q, front->right);}
}

（4）层序遍历源码

// 层序遍历
void TreeLevelOrder(BTNode* root)
{Queue q;Queue_init(&q);if (root != NULL)Queue_push(&q, root);while (!Queue_empty(&q)){BTNode* front = Queue_front(&q);Queue_pop(&q);printf("%c ", front->data);//下一层入队列if (front->left)Queue_push(&q, front->left);if (front->right)Queue_push(&q, front->right);}
}

我的杀手皇后已经摸过了这篇文章了，当我按下按钮时，这篇文章将会爆炸。所以，还不快逃！！！！！☠️☠️☠️☠️