链表实现队列的二叉树层序遍历：不用数组和递归的完整方案

提到二叉树的层序遍历，绝大多数人第一反应是“开一个队列，根节点入队，然后循环出队、打印、再入队左右孩子”。教科书上这一套确实干净，但有个小细节经常被一笔带过：那个“队列”到底用什么实现？默认答案通常是数组——分配一块连续内存，维护头尾下标。可一旦遇到禁止用数组、禁止用递归的约束，比如嵌入式裸机环境、底层库缺失，或者纯粹想验证自己对指针和链表抽象的理解，教科书方案就会直接失效。

“使用链表实现的层序遍历 - 不使用数组和递归”这个题目，我最近拿它做了一个完整落地项目。拆解下来会发现，它其实不是“换一种姿势写同一段代码”，而是把“队列”这个抽象从容器底层重新实现了一遍，同时逼着你把递归思维切换成迭代思维。这篇文章就把我当时的完整思路、代码实现、踩坑记录都整理出来，给同样被这个题目卡住的人一个可以直接抄作业的版本。

1. 项目背景与核心问题拆解

1.1 传统层序遍历的默认答案为什么是“数组队列”

我见过太多教材写层序遍历时，直接假定“队列”是一个已经存在的东西。用 C 语言写的时候，最常见的做法是开一个足够大的数组，头指针和尾指针各自往后移动：

int queue[MAX_N]; int head = 0, tail = 0;

出队就是queue[head++]，入队就是queue[tail++] = value。这种写法在刷题软件里不会有任何问题，因为测试用例的规模是预先定好的，数组开大一点就完了。

但真实项目里，“开一个足够大的数组”这个前提本身就是隐患。你根本不知道树的最大宽度是多少：一颗完全二叉树，最后一层可能有几万个节点；一颗退化链表树，队列里任何时候都只有一个节点。用固定数组要么白白浪费一大块内存，要么在最坏情况下直接溢出不给你任何容错机会。哪怕你改用动态扩容的数组方案，本质上还是“连续内存 + 下标访问”那一套，底层逻辑并没有变。

这个项目选择链表实现队列，最直接的理由就在这里：队列的长度不需要预先知道，入队一个节点就动态创建一个队列节点，出队一个节点就释放一个队列节点，内存占用和树的当前宽度严格成正比。不浪费，也不溢出。

另外还有一层现实原因：在很多嵌入式或教学场景里，标准库容器是不可用或者不被允许的。你不能指望环境里自带std::queue或者封装好的队列类型，唯一能确定存在的就是malloc和指针。用链表实现队列，是这套环境里最可靠、最可移植的方案。

1.2 递归做层序遍历的三个真实困境

“不用递归”这条约束乍看有点奇怪，因为二叉树和递归绑定得太深了。但递归天然是深度优先的工具，它靠系统调用栈保存路径信息，而层序遍历是按宽度推进的，两者本质上错位。

最简单的递归式层序遍历，是拿到一棵树之后，先求出树的高度 H，然后一层一层调用函数往下打印：

void printGivenLevel(TreeNode *root, int level) { if (root == NULL) return; if (level == 1) { printf("%d ", root->data); return; } printGivenLevel(root->left, level - 1); printGivenLevel(root->right, level - 1); }

每组 for 循环从第 0 层遍历到第 H 层，每一层都要把整棵树重新走一遍。平衡二叉树的高度是 O(log n)，总复杂度勉强能接受；但一旦遇到退化树，高度变成 O(n)，每一层都从头递归一遍，整体直接退化成 O(n²)。这个性能在几千层的时候就能肉眼可见地卡顿，更不用说百万级节点了。

更隐蔽的坑是系统栈深度。递归层序遍历时，递归深度等于二叉树高度。普通开发机的函数栈空间通常只有几兆，深度的二叉树递归到几万层就会栈溢出，程序直接崩溃。这种崩溃还特别难排查，因为它不是显式的错误信息，而是一个措手不及的 segmentation fault。

还有一种稍微聪明点的递归写法：递归 DFS 的过程中，把当前节点按照“所在层级”记录到一个结果容器里，最后再按层输出。这种做法时间上是 O(n)，但它至少依赖两样东西：一个可动态增长的数组/向量容器，以及递归调用栈本身。前者在“禁止数组”的约束下直接出局，后者在深树场景下仍然有爆栈风险。

所以“不用递归”不是题目故意刁难，而是把层序遍历真正放回迭代思路的必由之路。

1.3 链表方案的核心思路：FIFO 语义不变，存储介质更换

想通之后，你会发现这个题目的核心其实就一句话：层序遍历的本质是广度优先搜索（BFS），BFS 的本质是先入先出（FIFO），FIFO 的天然物理载体就是队列。你只需要把队列的底层存储从数组换成链表，其余逻辑保持不变。

所以整个项目的设计思路可以拆成三条线：

• 树的遍历顺序完全由 BFS 算法决定，与队列用数组还是链表无关。
• 队列只负责“按顺序暂存待处理的树节点”，它存的是树节点的指针，不是树的拷贝。
• 所有处理都发生在 while 循环里，整个过程没有任何函数递归调用。

换句话说，这不是一个全新的遍历算法，而是一个把“辅助数据结构”从内到外重新实现的项目。理解到这一层，后面写代码就有了明确的方向：先把链表队列封装好，再套层序遍历框架，问题自然解开。

2. 数据结构设计与底层原理解析

2.1 两套链表各司其职，互不干扰

很多人第一次写这个题目时容易走进一个误区：试图把树的 left/right 指针改造成队列指针，实现“复用节点”的效果。这个思路在特定面试题里确实存在，比如完美二叉树的 next 指针连接问题，但在这个项目里只会把事情搞复杂，因为你一旦动了 left/right，树的结构就被破坏了，遍历结束后还要想办法恢复，完全是自找麻烦。

正确的做法是：定义两套完全独立的结构体，各管各的一亩三分地。

树的节点只管树本身：

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

队列的节点只管保存树节点的指针，以及指向下一个队列节点的指针：

typedef struct QueueNode { TreeNode *tree; struct QueueNode *next; } QueueNode;

这里一定要想清楚一件事：队列节点里保存的是TreeNode *，不是 TreeNode 本体。这意味着队列的入队出队操作只涉及指针的搬运，完全不会复制树的数据。哪怕树有几十万个节点，队列里任意时刻也只保存“当前层的节点指针”，内存消耗被严格限制在当前层的宽度上。

很多写着写着就乱了套的人，问题多半出在搞混了这两套结构：在队列入队的时候去改树节点的 left/right，或者直接拿 TreeNode 冒充 QueueNode 用。记住这条原则就不会乱：树节点属于树，队列节点属于队列，两者的关系是“队列节点引用树节点”，仅此而已。

2.2 队首队尾指针的边界处理是真正的考点

链表队列本身是一个单向链表，但和普通链表不同的是，它必须同时维护两个指针：

• front 指向链表头部，出队时从这里取。
• rear 指向链表尾部，入队时从这里插。

入队的逻辑是标准的尾部插入，但空队列是特例：如果队列为空，front 和 rear 都必须指向新节点；如果队列不为空，只需要把新节点挂到 rear 后面，然后更新 rear。

出队的逻辑是标准头部删除，但同样有特例：如果删除的是最后一个节点，删除之后队列变空，此时必须把 rear 也置为 NULL。否则 rear 会成为一个悬空的野指针，指向一块已经被释放的内存。

我在写这个项目时，一开始出队函数只更新了 front，忘记处理 rear，结果在遍历到最后一层的最后一个节点时，队列明明已经空了，rear 还指着一个被 free 掉的节点。下一次入队时，入队函数检查q->rear发现不为空，就试图对一块已释放内存执行q->rear->next = newNode，段错误立刻出现。

这个边界处理不是细节，是链表队列能否正确工作的生死线。凡是写链表队列，都必须把“空队列”、“单节点队列”、“删除最后一个节点”这三个状态穷举一遍，任何一步漏掉都会在后续运行中爆发。

2.3 “不用数组”到底省掉了什么

有人可能会问：既然题目说不用数组，那我用 C 语言自带的malloc动态分配队列节点，这算不算“用数组”？显然不算。这里说的“数组”指的是在一块连续内存上用下标索引访问的线性结构，而链表是靠指针把分散在堆里的节点串起来的非线性存储结构，两者在内存布局上有本质区别。

更准确地说，“不用数组”这句话要表达的是三层意思：

• 不需要预先知道树的宽度，也就没有“队列最大容量”这个概念。
• 不需要下标运算，只靠指针的 next 关系就能完成全部 FIFO 操作。
• 不需要一次性申请大块连续内存，每次只需要申请一个小节点，释放时也按小节点归还。

这第三点在内存碎片化严重的嵌入式系统里是实打实的优势。数组队列需要一次性申请一块完整的连续内存，如果系统经过长时间运行，堆被切割得七零八落，一块几 KB 的连续空间可能根本分配不出来。链表队列则完全规避这个问题，因为每次只申请一个结构体大小的空间，成功率远高于大块连续分配。

3. 实操代码实现与逐段拆解

3.1 队列基础函数：入队、出队、判空

整个项目可以直接在标准 C 环境下编译运行，不依赖任何第三方库。先写队列的基础操作，这是后面所有功能的地基：

void enqueue(LinkQueue *q, TreeNode *tree) { QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode)); if (n == NULL) { fprintf(stderr, "malloc failed\n"); exit(EXIT_FAILURE); } n->tree = tree; n->next = NULL; if (q->rear == NULL) { // 队列为空，首尾都指向新节点 q->front = q->rear = n; return; } q->rear->next = n; // 挂到队尾 q->rear = n; // 更新队尾指针 } TreeNode *dequeue(LinkQueue *q) { if (q->front == NULL) return NULL; QueueNode *old = q->front; TreeNode *tree = old->tree; q->front = q->front->next; // 头指针后移 if (q->front == NULL) { // 出队后队列变空 q->rear = NULL; } free(old); return tree; }

malloc失败的处理我直接用exit终止了，这是教学项目里最干脆的做法；生产环境可以改成返回错误码或者走节点池复用逻辑，后面踩坑章节会专门展开。

这里有个细节值得注意：dequeue返回的是TreeNode *，并且是在free(old)之前从 old 节点里取出来的。如果你把顺序写反——先 free 再取指针——恭喜你提前获得一个野指针 bug。指针变量的生命周期和对它指向的内存的操作是两回事，一定要先取出需要的数据，再释放容器节点。

3.2 基础版层序遍历主流程

队列函数就绪之后，层序遍历的核心代码非常短：

void levelOrderByLinkQueue(TreeNode *root) { if (root == NULL) { printf("empty tree\n"); return; } LinkQueue queue = { NULL, NULL }; enqueue(&queue, root); while (queue.front != NULL) { TreeNode *cur = dequeue(&queue); printf("%d ", cur->data); if (cur->left != NULL) enqueue(&queue, cur->left); if (cur->right != NULL) enqueue(&queue, cur->right); } printf("\n"); }

这段代码的逻辑用一个例子就能走通。假设有这样一棵树：

1 / \ 2 3 / \ \ 4 5 6 / 7

执行过程如下：

最终输出结果是1 2 3 4 5 6 7，每一层的顺序完全正确。这背后的原理其实很朴素：出队一个节点时，把它的左右孩子按顺序排到队尾，正好形成“先处理上一层、再处理下一层”的天然递进。这就是 BFS 在二叉树上的直观体现。

3.3 分层打印增强版：两种计数方案对比

很多场景需要的不是一行平铺输出，而是每一层单独一行。这个需求我在项目里也实现了，而且试了两种不同口味。

第一种方案最简单：每一轮循环开始前，先遍历一遍当前队列，数出当前层有多少个节点，然后按这个数量出队。

void levelOrderLevelByLevel1(TreeNode *root) { if (root == NULL) return; LinkQueue q = { NULL, NULL }; enqueue(&q, root); while (q.front != NULL) { int levelSize = 0; QueueNode *p = q.front; while (p != NULL) { // 扫描队列，统计当前层节点数 levelSize++; p = p->next; } for (int i = 0; i < levelSize; i++) { TreeNode *cur = dequeue(&q); printf("%d ", cur->data); if (cur->left != NULL) enqueue(&q, cur->left); if (cur->right != NULL) enqueue(&q, cur->right); } printf("\n"); } }

这个方案好在思路直白，容易理解，但每次统计都要额外扫一遍队列。虽然统计的总开销摊下来仍是 O(n)，却多了一次遍历指针的过程，代码看着也不太优雅。

第二种方案效率更高，思路是维护两个计数器：一个记录当前层剩余节点数，一个记录下一层累计节点数。每出队一个节点，当前层计数减一；每入队一个节点，下一层计数加一。当前层计数归零时，说明这一层处理完了，两层的计数对调，然后输出换行符。

void levelOrderLevelByLevel2(TreeNode *root) { if (root == NULL) return; LinkQueue q = { NULL, NULL }; int currentLevel = 1; // 根节点所在层开始时只有 1 个节点 int nextLevel = 0; enqueue(&q, root); while (q.front != NULL) { TreeNode *cur = dequeue(&q); printf("%d ", cur->data); currentLevel--; if (cur->left != NULL) { enqueue(&q, cur->left); nextLevel++; } if (cur->right != NULL) { enqueue(&q, cur->right); nextLevel++; } if (currentLevel == 0) { printf("\n"); currentLevel = nextLevel; nextLevel = 0; } } }

这两种方案用同一个测试树跑，输出结果完全一致：

1 2 3 4 5 6 7

就我个人偏好，生产环境里我会选第二种，因为它避免了一次额外扫描，代码实际运行次数更少；教学讲解时我会先用第一种，因为它直接把“当前层节点数等于当前队列长度”这个核心观察讲透了。

3.4 完整测试样例与输出验证

项目里我写了一个标准的完整测试程序，包含建树、遍历、释放三个环节：

#include <stdio.h> #include <stdlib.h> // 这里省略 3.1 和 3.2 节中定义的各类结构体与函数 TreeNode *makeNode(int data) { TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode)); n->data = data; n->left = n->right = NULL; return n; } TreeNode *buildSampleTree(void) { TreeNode *root = makeNode(1); root->left = makeNode(2); root->right = makeNode(3); root->left->left = makeNode(4); root->left->right = makeNode(5); root->right->right = makeNode(6); root->left->right->left = makeNode(7); return root; } void freeTree(TreeNode *root) { if (root == NULL) return; freeTree(root->left); freeTree(root->right); free(root); } int main(void) { TreeNode *root = buildSampleTree(); printf("基础版层序遍历: "); levelOrderByLinkQueue(root); printf("\n"); printf("分层打印（方法一）:\n"); levelOrderLevelByLevel1(root); printf("\n"); printf("分层打印（方法二）:\n"); levelOrderLevelByLevel2(root); freeTree(root); return 0; }

编译命令很简单：gcc -Wall -Wextra -g -o level_order main.c。-Wall -Wextra这两个编译选项强烈建议加上，C 程序里大量的指针问题只有靠编译器警告和自己的检查结合才能尽早暴露。

4. 复杂度对比与使用边界

4.1 时间空间复杂度推演

先从时间维度看。每个树节点恰好被入队一次、出队一次。入队操作是 O(1) 的尾部插入，出队操作是 O(1) 的头部删除。所以整棵树遍历下来，总时间复杂度是 O(n)，n 是树中节点总数。这一点和数组队列没有任何区别，链表方案没有劣化。

再考虑分层打印的两个版本。方法一每一层开始时扫描一次队列，扫描的节点总数等于当前层节点数，所有层扫描总次数等于全树节点数，所以总时间仍然是 O(n)。方法二的入队和出队操作同样是 O(1)，额外维护两个计数器也是 O(1)，总时间还是 O(n)。两个方法在渐进复杂度上完全一致，只是常数存在差别。

从空间维度看，最关键的数据是“队列中任意时刻最多有多少个节点”。任何一次 while 循环开始时，队列里存放的都是当前层的节点；接下来这一层逐步出队，下一层逐步入队。在这个过程的最极端瞬间，队列里同时存在“当前层剩余节点”和“下一层已经入队的节点”，总数量不超过当前层宽度加下一层宽度之和，而上界是树的某一层最大宽度，记为 w。如果树是完全二叉树，w 约等于 n/2；如果是退化链表树，w 始终等于 1。

所以空间复杂度是 O(w)，或者更宽松地写 O(n)。这和“任何 BFS 都要付出 O(最大宽度) 辅助空间”的结论完全一致，链表方案并没有减少空间复杂度，它只是让这部分空间的分配方式变成了动态的、精确的——用多少，申请多少。

4.2 数组队列、链表队列、递归逐层三方案横向对照

我把三种方案放在同一张表里对比了一次，各自的性格差异一目了然：

这三者没有绝对谁优谁劣。数组队列胜在简单，一个数组两个下标就能转起来；链表队列胜在稳健，不依赖连续内存和固定容量；递归逐层打印胜在代码可读性高，但性能和栈安全性都最差。

4.3 真正应该用它的场景

做完这个项目之后，我给可以从中受益的目标场景画了个范围：

首先，嵌入式开发是最大的受益方。裸机环境往往没有完整标准库，更不可能有现成的动态数组容器，链表队列用malloc加上 C 语言最基本的语法就能构建，代价最小。

其次，深树遍历场景。树高度可能达到百万级时，递归一定会爆栈，数组队列无法预先知道宽度，链表队列是唯一能自然容纳未知宽度的选择。

再次，面试和教学场景。很多面试官出这道题的目的不是让你实现 BFS，而是验证你有没有吃透“队列是一种抽象，底层可以用不同结构实现”这一层。如果你能顺手说清楚链式队列的入队出队边界条件和空间复杂度，这一题基本就过了。

5. 踩坑记录与调试技巧

5.1 首尾指针的经典陷阱

我在前面提过对 rear 指针处理不当的问题，这里再展开一次。链表队列的绝大多数 bug 都出在首尾指针的一致性上，这几乎是所有写链式队列的人都会踩的坑。

我建议任何人在写完队列函数后，都做一次“三状态测试”：空队列入队、单节点队列出队、连续出队直到空。这三个状态的代码路径彼此独立，只要有一个没覆盖，就会在某个具体输入下炸出来。

调试的时候有个小技巧：不要只盯着出错的现场看，而是在每一步操作后把 front 和 rear 打出来。如果出现front == NULL但rear != NULL，或者反过来，基本可以断定是边界状态没处理干净。把这两个指针的不变量记在心里，排查效率会高很多。

5.2 内存生命周期管理是第二道关卡

这个项目涉及两类内存：树节点的内存和队列节点的内存。两类内存必须分开管理，生命周期需要严格分明。

遍历开始前，树节点已经被创建并且在堆上存在；入队时，队列节点被创建出来，保存树节点的指针；出队时，队列节点被释放，但树节点完全不受影响；遍历结束后，树节点仍存在，需要单独释放。一图以蔽之：队列节点是临时容器，树节点是树本身，谁都不该提前释放谁。

我在项目初期犯过的错误是，在 dequeue 里顺手把tree也给free了。这在遍历到倒数第二层时就会出现悬空指针——因为一个树节点被释放后，它的父节点可能还在队列里等待被访问，下一轮出队时拿到一个已经非法访问的地址。这个 bug 的隐蔽之处在于：程序可能不会马上崩溃，而是在某次极端输入下随机出现段错误，极难排查。

5.3 进一步优化：节点池与“不用数组”的边界

malloc和free每次调用都有开销，而且频繁的小块分配释放会在堆上留下碎片。对嵌入式实时系统来说，这两个问题都值得认真对待。我当时做的优化是引入“节点池”：

思路是，队列节点本身只在遍历期间使用，用完就释放；与其反复 malloc/free，不如维护一个空闲节点链表。出队时把节点插回空闲链表，入队时优先从空闲链表取，取不到才调用 malloc。

// 伪代码示意 QueueNode *getQueueNode(TreeNode *tree) { QueueNode *n = freePool; if (n != NULL) { freePool = freePool->next; } else { n = (QueueNode *)malloc(sizeof(QueueNode)); } n->tree = tree; n->next = NULL; return n; } void releaseQueueNode(QueueNode *n) { n->next = freePool; freePool = n; }

节点池化简了大量 malloc/free 调用，遍历速度能提升不少。这个优化完全符合“不用数组”的约束，因为它依然是链式结构，没有开辟连续内存。但需要提醒一句：节点池只适合“对象规格一致、生命周期短”的场景，通用系统里过度使用反而会让代码难以理解。

另外，如果你的题目要求严格禁用任何“预分配”手段，那节点池就得谨慎了。面试时最好先说清楚普通版本，再补一句“如果性能要求高，我可以用空闲链表做节点池复用”，面试官通常会认为你考虑得足够成熟。

5.4 一个更狠的实现思路：树节点自身指针复用的边缘方案

写项目时我还考虑过一种“完全不额外分配队列节点”的做法：每一层节点在入队之前，先把上一层的 left 和 right 指针临时借用为队列的 next 指针，等遍历完当前层后，边出队边恢复指针。这种方案理论上可以把辅助空间降到 O(1)，代价是遍历过程中树结构被临时破坏。

这个思路很有野心，也很有面试观赏性，但我不建议把它作为第一版交付。原因是恢复指针的顺序极容易出错，错一个节点整棵树就废了，调试成本远高于收益。如果真想尝试，建议只在线索化二叉树或完美二叉树这种特殊结构里实验，普通二叉树就先老老实实用独立队列节点。

最后再分享一点实际体会

做完整个项目，我最深的体会是“层序遍历”和“链表”两个词放在一起，没有表面上看起来那么违和。层序遍历本来就是一个关于顺序的算法，队列负责维护顺序，链表负责实现队列；当你把“顺序”从“存储方式”里彻底剥离出来之后，代码反而比教科书式的数组实现更容易说清楚每一步在干什么。

如果你也需要在禁数组、禁递归的约束下实现层序遍历，我的建议是把精力分成三份：一份给队列的边界状态，一份给内存的生命周期，一份给遍历主流程。前两者解决的是“正确性”，最后一项解决的是“完整性”。队列函数单独测试通过之后，再套层序遍历逻辑，基本一次就能跑通。这个思路适用于几乎所有“自定义数据结构 + 算法”组合的项目，算是意外收获。