数据结构学到二叉树你八成会先被前序、中序、后序遍历折腾一轮。等终于分清了“根左右”、“左根右”、“左右根”实验报告或者考研复习题里往往又冒出来一个“层序遍历”。我第一次写层序遍历时第一反应是好嘛又一个递归。结果照着递归思路写了半天越写越别扭。后来才彻底想明白层序遍历根本不是递归那一路的它是图的广度优先搜索BFS思想在二叉树上的落地核心就一句话用队列一层一层往外扫。这篇文章就把这件事讲透从层序到底在做什么、C 语言里队列怎么选到完整可运行代码再到那些让你“写二叉树程序总是报运行时错误”的典型坑最后再聊聊按层输出、之字形遍历、完全二叉树判断这些扩展玩法。适合刚学数据结构的学生、准备期末或考研 408 的复习党以及想用 C 语言刷二叉树面试题的人。1. 层序遍历到底在做什么先弄懂“横向推进”1.1 一个例子看懂访问顺序要理解层序遍历别急着背代码先拿一棵具体的树走一遍。假设有下面这棵二叉树1 / \ 2 3 / \ \ 4 5 6前序遍历根左右访问顺序是1, 2, 4, 5, 3, 6。中序遍历左根右是4, 2, 5, 1, 3, 6。后序遍历左右根是4, 5, 2, 6, 3, 1。层序遍历的顺序则是第 1 层1 第 2 层2, 3 第 3 层4, 5, 6合在一起就是1, 2, 3, 4, 5, 6。这里面有个很直观的特征层序遍历是按“层”为单位推进的先处理完第 k 层的所有节点才会碰第 k1 层的节点。它不关心某一条竖着的分支有多深只关心“同一水平线上的节点有没有处理完”。1.2 为什么偏偏要用队列前序、中序、后序用递归写得很顺手因为它们本质是深度优先搜索DFS沿着一条分支走到黑再回头走另一条。系统栈天然帮你保存了“回头路径”所以递归或者手动模拟栈都行。层序遍历就不一样了。它要求你把当前层节点从左到右全部记录然后先处理它们的下一层也就是“先进先出”。你想想看如果我用栈来做后入栈的左兄弟反而先弹出顺序直接乱掉。队列的先进先出特性正好卡住这个需求。用一个生活化的类比层序遍历就像食堂排队打饭。第一个窗口根节点先入队轮到它时就处理它同时把它左边的、右边的两个“新同学”安排到队列末尾然后队头的 2 出队又把 4 和 5 排到 3 后面。这样每个人都是按“从队头出来把孩子放到队尾”的规则移动队头的顺序天然就是从左到右、从上到下。1.3 和三种 DFS 遍历放在一起看我用同一棵树把所有遍历顺序列出对比这样期末复习时一眼就能分清遍历方式类别访问顺序辅助结构前序遍历DFS1, 2, 4, 5, 3, 6递归/显式栈中序遍历DFS4, 2, 5, 1, 3, 6递归/显式栈后序遍历DFS4, 5, 2, 6, 3, 1递归/显式栈层序遍历BFS1, 2, 3, 4, 5, 6队列很多初学者把前序和层序搞混是因为输出结果里都有“1 2”开头。但前序输出是“一条路走到黑”层序是“一层层摊开”。这个区别在代码实现上体现得更明显前序用递归自然就写出来了层序如果硬套递归处理“跨层顺序”会非常绕直接用队列才是正解。2. 动手前的设计节点、队列和几个关键决策2.1 二叉树节点长什么样在 C 语言里定义二叉树节点通常是三个字段值、左孩子指针、右孩子指针。#include stdio.h #include stdlib.h #include stdbool.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;学习阶段不需要搞太复杂值先放 int后面想换成 char 或者结构体都行。建树时我最常用的方式是写一个辅助函数直接动态分配内存TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); if (node NULL) { fprintf(stderr, malloc failed\n); exit(1); } node-val val; node-left NULL; node-right NULL; return node; }这里有一个很多新手会犯的致命错误把节点定义成普通局部变量然后返回它的地址。局部变量在函数返回后就失效了后面访问指针几乎必然崩溃。所以建树阶段务必用malloc分配并记得检查分配结果。2.2 队列用数组还是链表层序遍历的核心数据结构是队列。数据结构课里队列通常讲两种实现顺序队数组和链队链表。做二叉树题的时候我给一个非常实际的建议除非题目明确要求实现链队否则优先用数组环形队列。维度数组环形队列链表队列代码量少容易一次写对稍多要处理节点创建和释放容量限制需预设但可开大一些无固定上限入队出队操作下标取模逻辑清晰改指针稍微绕调试难度低数组内容能直接看中指针链路要逐步追适合场景算法题、实验、刷题生产级/弹性容量我在刷 LeetCode、写实验报告时默认就是MAX_QUEUE_SIZE开到 1000 或 10000 的数组环形队列。二叉树题目节点数量一般有限数组足够用而且数组版本没有链式结构里“改指针改串了”的风险。2.3 环形队列的三件套front、rear、count数组队列最怕的就是“假溢出”元素出队后数组前面空出一大片但 rear 已经走到末尾再入队就报满了。解决办法是让 rear 和 front 在数组末尾自动绕回开头也就是取模。#define MAX_QUEUE_SIZE 128 typedef struct { TreeNode* nodes[MAX_QUEUE_SIZE]; int front; int rear; int count; } Queue;这里我建议维护一个count字段而不是靠front rear判断空或满。原因很简单只靠 front 和 rear 判断时空队和满队都可能是front rear新手经常卡在这里。有了count判空判满没有任何歧义void initQueue(Queue* q) { q-front 0; q-rear 0; q-count 0; } bool isQueueEmpty(Queue* q) { return q-count 0; } bool isQueueFull(Queue* q) { return q-count MAX_QUEUE_SIZE; } bool enqueue(Queue* q, TreeNode* node) { if (isQueueFull(q)) { return false; } q-nodes[q-rear] node; q-rear (q-rear 1) % MAX_QUEUE_SIZE; q-count; return true; } bool dequeue(Queue* q, TreeNode** out) { if (isQueueEmpty(q)) { return false; } *out q-nodes[q-front]; q-front (q-front 1) % MAX_QUEUE_SIZE; q-count--; return true; }入队失败返回 false 是合理的说明队列容量不够。真正刷题时如果出现这种情况把MAX_QUEUE_SIZE调大即可。3. 代码实现从伪代码到可运行程序3.1 先写伪代码再动手不要一上来就闷头写 C。层序遍历的伪代码极其简洁你把它写在纸上在写代码时就会很少跑偏if root 为空直接返回 新建队列 q root 入队 while q 不为空: 出队一个节点 cur 访问 cur 如果 cur-left 不为空cur-left 入队 如果 cur-right 不为空cur-right 入队注意那个“不为空才入队”的判断。很多运行时错误的根源就是没有判断直接把 NULL 塞进队列出队时解引用空指针程序原地崩溃。3.2 完整示例代码下面是一个可以整体复制到本地编译器跑通的例子我保留了注释方便对照前面说的队列逻辑。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_QUEUE_SIZE 128 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct { TreeNode* nodes[MAX_QUEUE_SIZE]; int front; int rear; int count; } Queue; void initQueue(Queue* q) { q-front 0; q-rear 0; q-count 0; } bool isQueueEmpty(Queue* q) { return q-count 0; } bool isQueueFull(Queue* q) { return q-count MAX_QUEUE_SIZE; } bool enqueue(Queue* q, TreeNode* node) { if (isQueueFull(q)) { return false; } q-nodes[q-rear] node; q-rear (q-rear 1) % MAX_QUEUE_SIZE; q-count; return true; } bool dequeue(Queue* q, TreeNode** out) { if (isQueueEmpty(q)) { return false; } *out q-nodes[q-front]; q-front (q-front 1) % MAX_QUEUE_SIZE; q-count--; return true; } TreeNode* createNode(int val) { TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); if (node NULL) { fprintf(stderr, malloc failed\n); exit(1); } node-val val; node-left NULL; node-right NULL; return node; } void freeTree(TreeNode* root) { if (root NULL) { return; } freeTree(root-left); freeTree(root-right); free(root); } // 层序遍历入口 void levelOrder(TreeNode* root) { if (root NULL) { return; } Queue q; initQueue(q); enqueue(q, root); while (!isQueueEmpty(q)) { TreeNode* cur NULL; dequeue(q, cur); printf(%d , cur-val); if (cur-left ! NULL) { enqueue(q, cur-left); } if (cur-right ! NULL) { enqueue(q, cur-right); } } printf(\n); } int main(void) { // 构造示例树 TreeNode* root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); root-right-right createNode(6); printf(层序遍历: ); levelOrder(root); freeTree(root); return 0; }运行结果层序遍历: 1 2 3 4 5 63.3 关键步骤为什么要这么写第一步是“空树直接返回”。这个判断不写也不会每次都崩但写了能让函数在任何情况下都安全。你后面如果要写递归层数、求宽度入口健壮性会省很多调试时间。第二步是root入队。队里永远存放“已经遇到、但还没处理孩子”的节点。第三步是主循环。每次循环处理队头节点同时把它左右孩子放入队尾。这里有一个新手容易忽略的点访问 cur 时千万别顺手把 cur 释放掉。你还要读cur-left和cur-right释放早了同样会崩溃。第四步是“先左后右”。因为队列是 FIFO同一层的节点会按左到右的顺序进入队尾下一轮出队时顺序自然也是从左到右。如果反过来先入右再入左输出就变成从右到左了。3.4 时间复杂度与空间复杂度为什么是 O(n)层序遍历每个节点只入队一次、出队一次而且入队出队本身是 O(1) 操作所以时间复杂度是 O(n)n 是节点总数。空间复杂度是 O(n)。这一点要特别注意不能想当然写 O(logn)。队列在同一时刻存的是“某一层的若干节点”最坏情况下完全二叉树最后一层大约有 n/2 个节点队列就得同时容纳它们。所以队列空间上界约为二叉树最大层宽量级是 O(n)。这也是 BFS 和 DFS 的一个直观差别DFS 在栈上只存当前路径深度为 logn 量级时空间更省BFS 则要横向展开整个层空间消耗跟树宽有关。4. 写二叉树程序为什么总报运行时错误我踩过的坑和排查套路4.1 最常见的五类崩溃原因每次看到有人问“二叉树程序为什么总是报运行时错误”我看一眼代码十有八九是下面这几种情况。错误类型典型表现主要原因修复思路段错误程序运行后直接 Segmentation fault解引用空指针或野指针检查 malloc、检查入队前判空返回局部变量地址输出乱值或崩在奇怪的位置栈上节点在函数返回后失效用 malloc 分配节点别返回局部变量地址队列假溢出说好能存 128 个结果没到就“满”了没做环形取模front/rear 都要取模无限循环输出停不下来出队后没更新 front或队列条件写错检查 dequeue 里的 front 变化和 count--重复释放/内存泄漏报 double free 或内存越用越多同一块内存释放两次或该释放没释放设计好 freeTree保证每块 malloc 只 free 一次我单独把“返回局部变量地址”拎出来讲因为它太典型了。有些初学者写建树函数时图省事TreeNode* createNode(int val) { TreeNode node; node.val val; node.left NULL; node.right NULL; return node; }编译可能不报警运行却经常崩溃。原因是node是函数栈上变量函数一退这块内存就被系统收回了。你拿到手的是一个“悬空指针”后续一旦被改写行为完全不可预期。正确写法就是前面给的malloc版本。4.2 排查手段编译选项、printf 和内存工具遇到运行时错误别用眼睛干瞪。我平时排查顺序是这样第一用调试信息编译。GCC 下至少打开-g建议再开-Wall -Wextra让编译器帮你找可疑代码gcc -g -Wall -Wextra tree.c -o tree第二加 AddressSanitizer。这工具对内存类错误极其敏感能直接告诉你哪一行访问了非法地址gcc -g -Wall -Wextra -fsanitizeaddress tree.c -o tree运行后如果崩溃ASan 会输出类似“heap-buffer-overflow”的报告并准确指到源码行号。实验阶段用它排查 malloc、越界、重复释放问题非常高效。第三用 printf 插桩看队列状态。BFS 循环里可以临时打印 front、rear、count、当前节点的 val。比如printf(before dequeue: front%d rear%d count%d\n, q.front, q.rear, q.count);一般能看到两种异常count永远不减说明dequeue里忘了count--或者front不变说明dequeue没改 front。这两个字段配合起来队列有没有正常前进一目了然。第四如果用的是 VS Code 配 C/C 环境也可以在launch.json里配置 gdb 调试器直接打断点看变量。不过说实话二叉树题数据量小printf 插桩往往比图形调试更快我到现在也更喜欢先用日志定位。4.3 层序遍历和前序遍历怎么区分这也是线上线下经常被问的问题因为两种顺序在某些树上开头很像。关键区别就一句话层序是“横向层”前序是“纵向链”。拿文章前面那棵树举例前序输出1 2 4 5 3 6层序输出1 2 3 4 5 6。第一眼分不清没关系看第二、第三个节点就知道前序的 4 是 2 的左孩子意味着它一路扎到了左子树底部层序的 3 是根节点的右孩子说明它还留在第二层。如果题目给了你层序序列让你判断是否是前序序列的某种情况最好的办法是先把树画出来再对着树的形状看遍历路径。写代码时看到递归或栈想的是 DFS看到队列想的是 BFS这样基本不会混。5. 层序遍历还能怎么玩从实验报告到面试题5.1 按层分组输出先记本层节点数基础层序遍历只输出一个平的序列但很多实验报告和面试题要求“每一层单独一行”比如 LeetCode 102 题。实现上有个小而美的技巧每次进入 while 时先记下当前队列长度这段长度就是本层节点数。void levelOrderWithLevel(TreeNode* root) { if (root NULL) { return; } Queue q; initQueue(q); enqueue(q, root); int level 1; while (!isQueueEmpty(q)) { int levelSize q.count; // 关键本层节点数 printf(Level %d: , level); for (int i 0; i levelSize; i) { TreeNode* cur NULL; dequeue(q, cur); printf(%d , cur-val); if (cur-left ! NULL) { enqueue(q, cur-left); } if (cur-right ! NULL) { enqueue(q, cur-right); } } printf(\n); level; } }运行结果Level 1: 1 Level 2: 2 3 Level 3: 4 5 6这个levelSize q.count的思路适用范围很广你要“每层多少个节点”“二叉树最大宽度”“分层返回二维数组”都可以在这上面加代码。C 语言里如果想把每一层存成二维数组提前申请足够大的二维数组按层计数填入即可。5.2 完全二叉树判断、自底向上、之字形遍历层序遍历的价值不止于打印。很多二叉树性质判断用层序反而比递归清晰得多。判断完全二叉树的经典方法就是层序遍历配合“空节点标记”。规则是节点出队时如果遇到 NULL就把标志位置为 true之后如果再遇到非空节点说明中间有空缺这棵树就不是完全二叉树。如果是链式地一路空到底那就是完全二叉树。这个思路在做实验报告时非常好用因为它把“树满不满”这个空间问题变成了队列顺序问题。自底向上层序遍历也是层序的变体先正常按层收集得到[[1], [2,3], [4,5,6]]再反转层顺序变成[[4,5,6], [2,3], [1]]。实现时可以用一个二维数组暂存最后从后往前遍历。之字形锯齿形遍历则需要对层做个奇偶判断奇数层从左到右偶数层从右到左。最简单的方式是标准层序收集每一层偶数层把那一层的结果逆序也可以借助双端队列模拟从右向左访问。理解底层队列逻辑后这些变体都不难推出来。5.3 期末、考研和面试的复习要点如果是为期末或考研 408 复习我建议把层序当作“BFS 在树上的标准模板”来记。要掌握三个层次第一能画出给定树的层序序列第二能说清复杂度为什么是 O(n) 时间、O(n) 空间第三能手写完整队列版层序代码并扩展出按层统计。如果是在准备面试层序遍历相关的题目几乎必考。从基础版、按层分组、之字形、自底向上到求最大宽度、判断完全二叉树都是同一个模板的变体。用 C 语言刷题时把队列的两个接口enqueue和dequeue先封装好每题就能少重复写不少代码专注在题目本身的逻辑差异上。我自己平时还会做一个小改进把队列数组容量设到能容纳所有节点而不是刚好够一层。原因很简单二叉树最坏情况下最大层宽约为 n/2但你在循环里来不及精确计算设置成节点数 5或者直接开 1024、10000能少踩一个边界 bug。另一条经验是凡是往队列里放节点入队前一定要判空宁可多写两行也比运行时崩溃后查半天强。如果你正在写实验报告里的层序遍历或者刷题刷到怀疑人生记住这个最核心的画面从队头出一个把孩子放到队尾循环下去。想通这句话层序遍历就没有秘密了。