C语言层序遍历详解（手把手教你实现二叉树的层序遍历算法）

如上图所示，若一棵二叉树的结构如下：

       1     /   \    2     3   / \   /  4   5 6  

那么它的层序遍历结果就是：1 → 2 → 3 → 4 → 5 → 6。

为什么需要队列？

由于层序遍历是“先进先出”（FIFO）的访问方式，因此我们通常使用队列（Queue）来辅助实现。每当访问一个节点，就将其左右子节点依次入队；然后从队首取出下一个待访问节点，如此循环，直到队列为空。

C语言实现步骤

下面我们将用C语言完整实现C语言BFS算法。为了便于理解，我们将分步讲解。

1. 定义二叉树节点结构

typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;  

2. 实现一个简易队列

由于C标准库没有内置队列，我们用数组模拟一个固定大小的队列（实际项目中建议用链式队列）：

#define MAX_SIZE 100typedef struct Queue {    TreeNode* items[MAX_SIZE];    int front;    int rear;} Queue;// 初始化队列void initQueue(Queue* q) {    q->front = 0;    q->rear = 0;}// 入队void enqueue(Queue* q, TreeNode* node) {    if (q->rear < MAX_SIZE) {        q->items[q->rear++] = node;    }}// 出队TreeNode* dequeue(Queue* q) {    if (q->front < q->rear) {        return q->items[q->front++];    }    return NULL;}// 判断队列是否为空int isEmpty(Queue* q) {    return q->front == q->rear;}  

3. 层序遍历函数

void levelOrderTraversal(TreeNode* root) {    if (root == NULL) return;    Queue q;    initQueue(&q);    enqueue(&q, root);    while (!isEmpty(&q)) {        TreeNode* current = dequeue(&q);        printf("%d ", current->data);        if (current->left != NULL) {            enqueue(&q, current->left);        }        if (current->right != NULL) {            enqueue(&q, current->right);        }    }}  

4. 完整测试代码

#include #include // （此处插入上述 TreeNode 和 Queue 的定义及函数）int main() {    // 构建示例二叉树    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));    root->data = 1;    root->left = (TreeNode*)malloc(sizeof(TreeNode));    root->left->data = 2;    root->right = (TreeNode*)malloc(sizeof(TreeNode));    root->right->data = 3;    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));    root->left->left->data = 4;    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));    root->left->right->data = 5;    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));    root->right->left->data = 6;    root->right->right = NULL;    root->left->left->left = root->left->left->right = NULL;    root->left->right->left = root->left->right->right = NULL;    root->right->left->left = root->right->left->right = NULL;    printf("层序遍历结果：");    levelOrderTraversal(root);    printf("\n");    return 0;}  

运行结果

编译并运行上述代码，输出为：

层序遍历结果：1 2 3 4 5 6

总结

通过本教程，你已经掌握了如何用C语言实现层序遍历实现教程中的核心逻辑。关键点在于：使用队列模拟BFS过程，逐层处理节点。这种思想不仅适用于二叉树，还可扩展到图的广度优先搜索。

记住这四个关键词： C语言层序遍历、 二叉树层序遍历、 C语言BFS算法、 层序遍历实现教程。 它们将帮助你在面试或项目中快速定位相关知识。

动手试试吧！修改树的结构，观察输出变化，加深理解。