层序遍历是二叉树里出场率极高的操作尤其在按层处理、序列化和广度优先搜索场景中。大多数人第一时间想到的写法就是队列要么用数组模拟要么直接递归。但数组队列有先天缺陷递归做层序又别扭。这篇文我就用纯链表实现一套层序遍历不用数组、不用递归把队列的底层结构、指针操作、内存释放这些细节全部摊开讲清楚适合正在学数据结构、准备手撕代码或想加深对队列理解的读者。如果你觉得“链表队列不是比数组队列更麻烦吗”先别急着下结论。数组队列确实实现简单但你在真实项目中跑一跑就会发现问题——假溢出、扩容、取模逻辑哪一个都不省心。而链表队列虽然多写几行代码但胜在结构干净、动态分配、不浪费空间。更何况把链表队列做扎实了后续处理二叉树按层输出、多叉树层序、图的BFS都会非常顺。1. 层序遍历的本质认识1.1 宽度优先搜索天然依赖队列层序遍历的核心思想是“一层一层往下扫”先把根节点拿到然后处理它的左右孩子接着处理孩子的孩子。这个顺序在计算机里有一个专用名字叫广度优先搜索BFS。BFS的特点是“先看到的节点先展开”这是先进先出FIFO的顺序而队列正是因为FIFO特性成了BFS的天然搭档。我用医院叫号来类比。你挂完号拿一个号诊室按号码从小到大的顺序叫每叫一个人就把他后续可能产生的“新号”排到队尾。层序遍历也一样每访问一个节点就把它的左右孩子加到队伍末尾下一个要访问的节点总是队伍最前面的那个。这完全就是队列的行为不是栈也不是递归能直接模拟出来的顺序。不少初学者会有个疑问二叉树的前序、中序、后序遍历都能用递归实现为什么层序遍历不行原因在于递归天然是深度优先的。函数调用会先一直往下钻进左子树直到碰见空节点才返回这对应的是“一路走到黑”而不是“一层一层的扫”。虽然你可以给递归函数加一个深度参数把同一深度的节点挂到同一个列表里再最后拼接输出但这种做法本质上还是在用递归模拟层序而且它需要额外的容器按深度缓存结果既绕又不高效。所以层序遍历最正统的实现方式就是队列迭代。1.2 不用数组和递归意味着什么从这个标题出发“不使用数组”是针对队列的底层存储来说的。常见教科书写法用数组模拟环形队列通过取模运算让front和rear在固定容量的数组里循环。这种实现适合刷题因为题目一般会明确告诉节点上限但在真实的工程代码里数据规模往往不可预知。数组小了会溢出数组大了浪费内存扩容时要整体搬移操作起来靠取模维持下标一旦front大于rear就得加倍小心。“不使用递归”则针对遍历方式。用递归做层序不是做不到而是写出来不符合BFS的直觉而且递归深度受调用栈限制树一旦退化成长链递归层数可能直接爆栈。换用迭代式层序遍历后循环次数等于节点数量不存在系统栈溢出风险代码逻辑也更贴近“一层一层处理”这个真实业务语义。我一开始做这个方案时也是从数组队列起步的。后来在一台配置很低的环境上处理一棵深度很大的二叉树数组队列不断扩容、搬移性能表现惨不忍睹。换上链表队列以后内存按需分配每个节点只多存一个指针整个过程顺滑很多。这也是我建议大家不要只停留在刷题层面的原因——数据结构的选型最终要回到真实场景里验证。2. 为什么数组队列不够好2.1 数组队列的假溢出和扩容痛点先说说数组实现队列最经典的坑假溢出。假设你开了一个长度为5的数组先入队三个元素再出队两个那front指针指向下标2rear指向下标3。此时数组前两个位置空着但rear已经走到数组中间不会自动回到前面。如果继续入队rear到尾部就卡住了哪怕数组头部还有空位也无法再插入新元素。这就是假溢出——空间明明还有却因为rear不回头而用不上。常见的解决办法是做环形队列用取模运算让下标循环。于是你每次入队要写queue[rear (rear 1) % capacity]出队要写front (front 1) % capacity判满还要留一个空位。这些操作在数学上不难但非常容易出错尤其是边界条件空队列和满队列的判别条件非常接近一旦把留空位的逻辑写错就会出现队列已满还能插入、或者空队列还能弹出的Bug。我在调试这类代码时吃过不少苦头最后都要靠打印front和rear的具体值一点点推演。数组队列还有一个隐藏问题扩容。如果不想让队列满就得在入队前检查容量满了就重新分配一块更大的内存把旧数据整体搬到新数组。这个搬移本身是O(n)的操作数据量一大入队的均摊开销就上去了。而且搬移之后front和rear的索引逻辑也要重新计算代码复杂度瞬间上升。2.2 链式队列的结构优势链式队列则不存在上述问题。它的结构一眼就能看懂每个元素是一个链表节点节点里存数据和指向下一个节点的指针。队列本身维护两个指针——front指向队头rear指向队尾。入队在rear后面挂新节点出队把front指向的节点摘下来时间复杂度都是O(1)不需要取模不需要判满不需要扩容。内存随用随申请随删随释放存储利用率是100%。链表队列唯一的代价是多存一个next指针一般占8字节64位系统。对于二叉树层序遍历这种场景节点数据和指针的总开销完全可控。而且链表实现的代码结构非常清晰从头到尾只有入队、出队、判空三个操作没有下标运算的弯弯绕绕。我建议读者把“链式队列”和“数组环形队列”这两种写法都亲自实现一遍对比一下各自的边界判断。说实话链表队列更锻炼指针操作能力尤其是空队列时front和rear两个指针的协同更新。这部分一旦想明白很多复杂链表的题都会迎刃而解。2.3 那为什么刷题时大家都用数组你可能想问既然链表队列这么好为什么刷题平台上的题解几乎清一色用数组模拟原因很简单刷题场景的数据规模是题目固定好的比如节点数不超过1000这时开一个大小为1005的数组完全够用代码写起来最短提交最快。再加上很多语言自带的队列封装比如STL queue底层虽然也是容器适配但对使用者来说底层细节被屏蔽了所以大家习惯性地调用现成结构。但从学习数据结构的角度我强烈建议至少手写一遍链式队列。因为理解底层实现后你才能判断什么时候用数组队列、什么时候用链式队列。真实系统中队列长度往往动态变化甚至可能出现长时间闲置再突然涌入大量数据的情况。数组定长要么浪费、要么不够链式结构则天然适配这种波动。这个取舍逻辑是写业务代码时经常遇到的也是面试官喜欢深挖的点。3. 链表队列的核心实现细节3.1 结构体设计链节点和队列分开先定义链表节点的结构体。层序遍历中队列里存的是二叉树节点指针所以数据域的类型可以写成二叉树节点指针。如果你希望队列更通用可以用void*或类型抽象但为了演示清晰这里直接面向二叉树实现。// 链表节点作为队列的基本存储单元 typedef struct QueueNode { struct TreeNode *data; // 存的是二叉树节点指针 struct QueueNode *next; // 指向队内下一个节点 } QueueNode; // 队列结构只维护头尾两个指针 typedef struct { QueueNode *front; // 队头指针 QueueNode *rear; // 队尾指针 } LinkQueue;这里的关键点是把“链表节点”和“队列”本身分开。链表节点解决数据的连接关系队列解决头尾定位。如果只定义一个head指针也能模拟队列但入队时需要从头遍历到尾部复杂度变成O(n)那层序遍历的总复杂度就会从O(n)退化到O(n²)。所以front和rear两个指针缺一不可——front保证出队O(1)rear保证入队O(1)。在数据结构领域想降低复杂度往往不是靠更复杂的算法而是靠多一个指针。3.2 入队和出队两个边界条件要盯死初始化队列时把front和rear都置为NULL表示空队列。入队操作分两种情况队列为空和非空。为空时新节点既是队头又是队尾front和rear都指向它非空时只需要把rear的next指向新节点然后rear后移。出队操作同样要处理边界如果队列只有一个节点出队后front和rear都要置NULL否则会让rear指向已被释放的内存。// 初始化队列 void initQueue(LinkQueue *q) { q-front NULL; q-rear NULL; } // 判空front为NULL即为空 int isEmpty(LinkQueue *q) { return q-front NULL; } // 入队尾插 void enQueue(LinkQueue *q, struct TreeNode *data) { QueueNode *newNode (QueueNode *)malloc(sizeof(QueueNode)); newNode-data data; newNode-next NULL; if (q-rear NULL) { // 队列为空时front和rear都指向新节点 q-front newNode; q-rear newNode; } else { // 队列非空时尾节点向后延伸 q-rear-next newNode; q-rear newNode; } } // 出队头删 struct TreeNode *deQueue(LinkQueue *q) { if (isEmpty(q)) { return NULL; } QueueNode *temp q-front; struct TreeNode *data temp-data; q-front q-front-next; if (q-front NULL) { // 队列中只有一个节点出队后队列为空 q-rear NULL; } free(temp); return data; }入队时的空队判断可以写成q-rear NULL或q-front NULL本质等价。出队时一定要记住弹出后如果front变成NULL说明队列已空必须同步把rear置空。这是一个非常经典的“忘了同步rear”Bug一旦漏写下一次入队时rear还指着已释放的旧节点后续操作全是野指针。我把这个边界问题的简化版本说给你听队列里的front和rear像两个人一前一后抬着一根木头。队伍只有一个节点时两个人其实站在同一个位置。前面的人走了后面的人如果不知道队伍空了还会朝原来那个位置跨步结果就踏空。所以出队时要有个“同步确认”机制。3.3 带不带头节点怎么选链表队列有两种风格带头节点的和不带头的。带头节点的队列会在真正存储第一个数据之前先挂一个空的头节点front永远指向它rear指向最后一个数据节点。这样入队和出队时不用特殊处理空队列代码更统一但浪费一个节点而且遍历时会多走一次空节点。不带头节点的写法就是上面的代码逻辑直观但要小心空队边界。如果写的是带头节点版本出队时即使队里只有一个数据节点front也不会变成NULL仍指向头节点所以rear不需要同步置空。两种写法都能用但风格要统一不要混着来。我个人偏好不带头节点的写法因为层序遍历最后要逐个释放二叉树节点和队列节点无头版本的内存归属更清晰释放时不容易漏。带头的版本每个队列节点多一层壳释放时得记得先摘头节点新手容易写漏。当然这是习惯问题。你如果接受不了空队时的两指针同步可以换带头版绕开它但底层的指针逻辑还是要吃透。4. 链表层序遍历的完整实操4.1 二叉树节点的定义搞定了队列接下来是二叉树本身。这里用最常规的二叉链表结构每个节点包含一个整数数据域和左右孩子指针。typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;有读者会问既然标题强调链表为什么不把二叉树也用孩子兄弟表示法改造成链表结构这其实是个好问题。树的孩子兄弟表示法适合多叉树或需要节省空间的场景但对经典的“左右孩子二叉树”来说直接用left/right两个指针更直观。队列里存的是树节点指针队列本身是链表结构这就已经满足“不使用数组”的要求了。如果非得把树也改成广义链表反而让代码复杂化不利于读者理解层序逻辑本身。4.2 层序遍历函数实现层序遍历的主函数很短核心逻辑就三步根节点入队循环弹出队头每弹出一个节点就把它的左右孩子依次入队。这个流程就是BFS的骨架。// 层序遍历主函数使用链表队列迭代实现 void levelOrderTraversal(TreeNode *root) { if (root NULL) { return; } LinkQueue queue; initQueue(queue); enQueue(queue, root); while (!isEmpty(queue)) { TreeNode *current deQueue(queue); printf(%d , current-val); if (current-left ! NULL) { enQueue(queue, current-left); } if (current-right ! NULL) { enQueue(queue, current-right); } } printf(\n); }为什么入队时只入不空的孩子因为出队后要访问节点的数据域如果入队空孩子出队时就得增加一次空判断访问current-val就会崩溃。与其在出队时判断不如在入队时就把空节点全部拦截掉。这样队列里只存在有效节点代码少一个分支逻辑也更顺。循环结束的条件是队列为空。队列为空说明所有已经入队的节点都处理完了而每个节点处理完又会让它的孩子入队孩子处理完再让孙子入队……这个链式反应会一直持续到叶子节点叶子无孩子可入队列逐渐清空遍历结束。4.3 测试用例与运行过程我构建一棵简单的二叉树来验证根节点值为1左孩子2右孩子3节点2的左孩子4节点3的右孩子5。树的结构如下1 / \ 2 3 / \ 4 5按层序输出的预期结果1 2 3 4 5。模拟一下执行过程。初始队列空。根节点1入队队列变成[1]。弹1打印1把2和3依次入队队列变成[2, 3]。弹2打印2把4入队队列变成[3, 4]。弹3打印3把5入队队列变成[4, 5]。弹4打印4没有孩子入队。弹5打印5。最后队列空结束。整个过程每一步都严格按照FIFO顺序先进入队列的2和3一定先于后进入的4和5被弹出。这保证了同一层的节点按从左到右的顺序输出不同层的节点按上到下的顺序输出。我在实际操作中还会加一个“遍历统计”功能顺便统计总节点数用来快速验证结果对不对。对上面的树来说打印5个节点后队列正好为空说明遍历没有遗漏也没有循环死锁。这种做法推荐给刚开始写树遍历的读者多一层校验能及早发现队列指针更新的错误。4.4 内存释放不写就会泄漏代码写完了很多初学者却忘了释放内存。链表队列里的每个节点都是malloc出来的使用完后不free程序就会内存泄漏。尤其是做服务端开发时这种泄漏会在长时间运行后逐渐耗尽内存。层序遍历结束后要遍历队列剩下的节点依次释放而二叉树节点也要通过后序遍历释放干净。// 遍历队列并释放所有节点 void freeQueue(LinkQueue *q) { QueueNode *current q-front; while (current ! NULL) { QueueNode *temp current; current current-next; free(temp); } q-front NULL; q-rear NULL; } // 后序释放二叉树节点 void freeTree(TreeNode *root) { if (root NULL) { return; } freeTree(root-left); freeTree(root-right); free(root); }释放顺序很关键。必须先释放左右子树再释放根节点如果反过来先把根释放了就再也找不到左右子树的指针了那两棵子树就真的泄漏了。队列释放则要先用临时变量保存下一个节点再free当前节点否则free之后next指针就访问不到了。5. 常见问题与排查技巧实录5.1 死循环rear和front指针不同步最常见的错误就是死循环。某开发者在第一次实现时出队后只更新了front没有判断队列是否为空导致最后一次出队时front变为NULL但循环条件却还在检查一个q-front NULL的旧状态程序直接崩溃。另一种死循环情况是入队逻辑里只在rear不为NULL时才更新rear但空队入队时忘了设置rear导致下一次入队时rear依旧是NULL插入的节点没有被正确链接。排查这类问题我习惯在前面提到的printf法在入队和出队处各打一行日志打印当前队列的front和rear的值。如果你能看到指针在反复跳动而不是单调向后移动大概率是循环条件写错了——比如用while (front ! rear)判断而链式队列中的front和rear在只有一个元素时是重合的这个条件在一开始就不成立。5.2 空指针崩溃访问了不存在的孩子有些读者在入队时不判断左右孩子是否为空直接enQueue左右孩子。这样出队时如果有空节点访问current-val就会触发段错误。正确的做法是入队前判断而不是出队后增加分支。还有一种情况是根节点本身为空调用层序函数前没有任何保护执行到enQueue(queue, root)时把NULL塞进队列循环里第一次访问current-val就崩。所以函数开头那个if (root NULL)绝对不能省。5.3 按层输出怎么做标准的层序遍历只输出一长串但很多业务场景要求按层打印比如把二叉树按层渲染成可视化结构。实现方法是在BFS循环里加一个“层宽度记录”——进入每层前先取当前队列长度这个长度值就是当前层的节点数然后只弹出这个数量的节点。细节是利用当前队列大小在循环过程中是动态变化的比如根节点入队后size1弹1打印后把2和3入队此时size变为2于是下一轮循环的层宽就是2恰好对应第2层。我曾经在某标签体系的树结构展示中用过这个变体。树每一层的节点数量不固定用size记录后就能按层把节点对齐输出生成的展示效果非常直观。如果你还要做锯齿形遍历之字形可以配合一个方向标记奇数层从左到右访问偶数层从右到左访问。实现上可以用两个链表队列交替轮换或者用双向链表模拟双端队列核心本质还是BFS按层推进只是每层内的输出顺序不同。5.4 复杂度分析为什么这个方案值得用层序遍历中每个节点入队一次、出队一次每次入队和出队都是O(1)整体时间复杂度是O(n)n是二叉树节点数。空间复杂度方面队列中同时存在的元素个数不会超过树某一层的最大节点数最坏情况下是完全二叉树的最后一层约有n/2个节点所以空间复杂度是O(n)。相比递归版本可能消耗的调用栈空间链式队列在树深度大时不会爆栈空间分配也更均衡。对比一下数组队列和链表队列在几个关键维度的表现可以看这个表维度数组环形队列链式队列入队操作O(1)但要判断满和取模O(1)直接尾插出队操作O(1)front后移O(1)front后移并free空间利用率有容量上限可能浪费或溢出按需分配利用率高扩容需要搬移全部数据无需扩容边界逻辑取模和判满容易写错空队和非空队需同步两指针适用场景容量确定、追求极致性能数据量动态变化、工程化更友好5.5 调试技巧从小处着眼调试链表相关代码我有一条原则永远先用最小的数据结构验证。比如先写一个只有三个节点的队列手动跑通入队、出队、空队列三种情况再接入二叉树层序逻辑。如果直接写完整代码后从报错往回查指针问题会比较难定位因为队列和树两层结构交叠在一起出错时很难判断是谁的锅。另外我习惯在入队和出队函数里加上注释标明“前置条件”和“后置条件”。比如出队的前置条件是队列非空后置条件是front和rear保持有效。这样代码虽然多了几行注释但后续维护和排错会轻松很多。调试时把这两处注释当成断言来检查一旦违反立刻就能定位到问题函数。6. 写在最后的实践经验链式队列实现层序遍历这段代码我前后在不同项目和练习中写过很多遍。每一次重写对于指针的边界条件都会多一分肌肉记忆。在实际工程中真正用到层序遍历时我会优先考虑队列底层是否要自己实现还是直接用现成封装。如果是在一个性能敏感且数据规模无法预估的组件里链表队列是我常规选择方案之一如果是快速原型验证我可能会偷懒用现成队列。但无论用哪种理解底层原理都是前提否则出了问题你连排查方向都没有。最后再分享一个小技巧如果你在面试中手写这道题可以主动和面试官聊一聊“为什么层序遍历用队列而不用栈”“为什么链表队列在动态数据场景下更合适”。这类问题比背代码更能体现对数据结构的理解深度。能把这些原理讲清楚比单纯把代码写出来更有说服力。