二叉树遍历这个知识点几乎是每个学数据结构的人都要迈过去的一道坎。面试要问、考试要考、平时写点树相关的代码也绕不开。很多人在递归实现里还能勉强写出来一到非递归就懵了尤其是后序遍历简直能用“玄学”来形容。这篇文章我打算用 C 把二叉树的三种遍历方式从头到尾拆一遍先讲清楚递归版本里那几行代码为什么顺序换一下就变了再用栈把递归“翻译”成非递归版本最后补一个层序遍历作为延伸。无论你是刚学到树结构的新手还是准备招聘面试想快速捡起来这篇文章都适合你直接照着敲一遍。我会固定用一棵测试树贯穿全文每个函数的输出都拿它验证这样你跟着跑一遍就能确认自己写对了没有。1. 先把树的骨架搭起来节点定义与建树学遍历之前得先把树在内存里长什么样搞清楚。C 里最经典的二叉树节点定义是这种指针结构struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这个结构很好理解val 存数据left 和 right 分别指向左孩子和右孩子没有孩子就是 nullptr。对比数组存储用指针串起来的二叉树天然更适合递归处理因为每个节点都可以当作一棵子树的根而子树又有自己的 left 和 right于是“递归”这个动作在结构上就自然成立了。1.1 为什么“访问时机”决定了遍历顺序不要直接背“根左右”“左根右”“左右根”背了也容易混。先看清楚一个事实三种遍历的共同点是“先左后右”区别只有根节点在什么时候被访问。先序遍历先输出当前节点再去处理左子树和右子树核心是“进树就输出”。中序遍历先把左子树整个处理完再输出当前节点最后处理右子树核心是“左子树回来再输出”。后序遍历左右子树都处理完最后才输出当前节点核心是“全部干完再汇报”。这么一拆你会发现所谓先序、中序、后序命名依据就是根节点被访问在三个位置中的哪一个。后面所有递归代码不过是把“输出”这一行放到左递归和右递归的不同位置罢了。这也解释了为什么很多教材会强调“二叉树本身是递归定义的”每个节点的左子树和右子树仍然是一棵二叉树所以遍历的操作可以一直套用到子树上直到遇到空节点为止。1.2 固定一棵测试树后面所有输出都对它为了让你能自己验证我把全文统一的测试树定为下面这棵1 / \ 2 3 / \ \ 4 5 6左子树挂在 1 的左边右子树挂在 1 的右边其中 3 没有左孩子、右孩子是 6。建树代码可以直接照抄TreeNode* buildExampleTree() { TreeNode* n1 new TreeNode(1); TreeNode* n2 new TreeNode(2); TreeNode* n3 new TreeNode(3); TreeNode* n4 new TreeNode(4); TreeNode* n5 new TreeNode(5); TreeNode* n6 new TreeNode(6); n1-left n2; n1-right n3; n2-left n4; n2-right n5; n3-right n6; return n1; }这棵树的遍历结果如果你能提前背下来后面调试自己的代码就非常省事先序 1 2 4 5 3 6中序 4 2 5 1 3 6后序 4 5 2 6 3 1层序 1 2 3 4 5 6。我建议你把这四个结果抄在便利贴上写完一个函数就对一次。别小看这一步我见过太多人写完后序遍历对着屏幕发愣就是因为没有标准答案可以对照。2. 递归实现三份代码看懂三种遍历递归版本是理解遍历的基础代码短得惊人很多人背的就是这一版。这里的核心是每个函数都只做三件事判空、递归左、递归右再加上“输出当前节点”这个动作。输出放在哪里就决定了遍历顺序。2.1 先序遍历进树就输出void preorder(TreeNode* root) { if (!root) return; cout root-val ; preorder(root-left); preorder(root-right); }代码逻辑就是“先输出自己再往左走左子树走完回来再往右走”。用固定测试树走一遍进入 1输出 1进入 2输出 2进入 4输出 44 的孩子都是空回到 2 再进入 5输出 5……整个过程就像“走到哪报到到哪”最后输出 1 2 4 5 3 6。先序的一个经典用途是复制一棵二叉树你只需要先创建当前节点然后递归创建左子树和右子树顺序完全是先序。2.2 中序遍历左子树处理完再输出void inorder(TreeNode* root) { if (!root) return; inorder(root-left); cout root-val ; inorder(root-right); }和先序只差一行位置输出被放到了左递归和右递归之间。对测试树结果是 4 2 5 1 3 6。注意看它正好把 1 放到了中间2 放到了它的左子树 4 和 5 的中间这就是中序的“左根右”。中序还有个很重要的性质如果这棵树是二叉搜索树中序遍历输出的一定是升序序列。很多算法题让“判断二叉树是不是二叉搜索树”“找第 k 小节点”本质都是在利用中序的这个单调性。说实话这个性质在笔试里出现频率极高值得单独记下来。2.3 后序遍历左右都处理完才输出void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); cout root-val ; }输出测试树的后序4 5 2 6 3 1。根节点 1 是最后一个输出的因为要先等它的左右子树全部处理完。后序的一个典型用途是删除整棵树。你想删掉一个节点必须先把它的两个孩子删掉否则删掉父节点后你再也找不到子节点就会内存泄漏。这个“先处理孩子再处理自己”的顺序正好就是后序遍历。另一个相关场景是求树的高度先知道左右子树的高度取最大值再加一就是当前节点的高度这也是典型的后序思路。你观察一下代码就会发现后序里“输出自己”的位置在两次递归之后这种“收集完孩子信息再处理自己”的模式在很多树形 DP 题目里都是通用套路。2.4 递归调用栈你的“隐式助手”很多人卡在递归上是因为试图人肉展开递归。三层以内的树还能展开四层五层就很难了。正确做法是“相信你的函数定义”如果preorder(root)的定义就是“输出 root 然后遍历左右子树”那么当它调用preorder(root-left)时你只需要相信这句话不需要展开它。递归底层靠的是一块叫“调用栈”的内存区域。每次调用函数系统会把当前函数的状态压栈函数返回后再从栈里恢复状态继续执行。二叉树递归遍历里调用栈帮你记住的就是那些“左子树还没处理完的祖先节点”。三种遍历的区别只是“输出自己”发生在压栈前、左子树返回后还是右子树返回后。打个比方先序像一进办事大厅就喊号中序像把左手边窗口全办完再喊号后序像把所有窗口都办完才喊号。系统栈就是那个帮你排队叫号的工作人员它默默记住了你还没处理的节点。3. 非递归实现用栈把递归翻译出来递归版本虽然好写但有两个实际问题一是函数调用有额外开销树很深时可能栈溢出二是很多面试官会追问非递归怎么写想看你是不是真的理解遍历过程。非递归的核心思路是用一个显式的栈来模拟系统栈把递归里“暂时挂起的节点”保存下来。3.1 非递归先序出栈即访问void preorderIterative(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); cout cur-val ; if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); } }这里有个很容易写反的细节一定要先压右孩子再压左孩子。为什么因为栈是后进先出右孩子先进栈会待在栈底左孩子后进栈会待在栈顶下一次循环先弹出左孩子这样才能得到“根-左-右”的顺序。顺序一换输出就变成“根-右-左”了虽然程序不报错但结果错得很隐蔽。这是我在面试题里见过最经典的“看似会做实际写错”的版本。3.2 非递归中序一路向左再回头void inorderIterative(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); cout cur-val ; cur cur-right; } }中序没有先序那么直接因为中序要先处理左子树所以你得先“一路向左”把沿途节点全部入栈直到 cur 变成 nullptr说明最左边走到底了。此时弹出栈顶节点并输出然后让 cur 指向它的右子树继续循环。用测试树推演开头几步cur11 入栈cur22 入栈cur44 入栈curnullptr。第一次 pop 出来的是 4输出 4cur4-rightnullptr。接着再 pop 出来 2输出 2cur5。5 入栈后 cur 又走到 nullptr再 pop 输出 5。你看这个“一路向左再回头”的过程正好等价于递归里“把左子树整个处理完再回来”。空树的情况也不用担心while (cur || !st.empty())条件里 cur 为 nullptr、栈为空时循环直接跳过自然不会有输出。3.3 非递归后序双栈法和标记法后序是三种里最容易卡壳的。问题在于先序和中序只需要在“往下走”的时候入栈回来的时候输出就行后序要求左右子树都处理完再输出单靠一个栈很难判断当前节点到底是被“路过”还是终于可以输出了。这里给两种我实际用下来最顺手的写法。方法一双栈法先序变种反转。void postorderIterative(TreeNode* root) { if (!root) return; stackTreeNode* st1; stackTreeNode* st2; st1.push(root); while (!st1.empty()) { TreeNode* cur st1.top(); st1.pop(); st2.push(cur); if (cur-left) st1.push(cur-left); if (cur-right) st1.push(cur-right); } while (!st2.empty()) { cout st2.top()-val ; st2.pop(); } }注意这个循环里入栈顺序和先序相反先压左、再压右。于是 st1 弹出的顺序是“根-右-左”也就是先序的镜像顺序。每次弹出的节点我们都压进 st2最后再把 st2 整体弹出由于 LIFO“根右左”反着出来就是“左右根”正好是后序。这个方法优点是代码短、不容易错缺点是用了两个栈。面试时如果只要求写非递归后序我一般先写这个稳妥。方法二标记法一个栈visited 标志。void postorderIterative2(TreeNode* root) { stackpairTreeNode*, bool st; st.push({root, false}); while (!st.empty()) { auto [cur, visited] st.top(); st.pop(); if (!cur) continue; if (visited) { cout cur-val ; } else { st.push({cur, true}); // 当前节点标记已访问 st.push({cur-right, false}); st.push({cur-left, false}); } } }每个节点第一次从栈里弹出时 visited 为 false说明只是路过把它标记为 true 后重新入栈同时把左、右孩子入栈。栈是 LIFO谁后入谁先出所以想让左孩子先被处理就要把左孩子最后入栈于是代码里写入栈顺序是 cur、right、left实际处理顺序就是 left、right、cur完全符合后序。当 cur 第二次弹出时 visited 为 true说明它的左右子树一定已经处理完了这时候才输出。注意这个入栈顺序和处理顺序是反的。看到st.push({cur, true})先执行别以为当前节点会先被处理它反而会等 right 和 left 都从栈里弹出并处理完之后才轮到。这种“反直觉”正是标记法容易看迷糊的原因。方法二比双栈法更贴近递归的本质只需要一个栈但每个节点会入栈两次压栈次数多一倍。两种写法我都建议敲一遍敲完你会对“递归隐式栈”有非常直观的感受。如果面试官继续问“能不能用一个栈且不用额外标记实现后序”那种写法也有但阅读性和稳定性都一般不建议优先展示。4. 层序遍历从 DFS 跳到 BFS前三种遍历都属于深度优先DFS核心是沿着一条分支走到底再回头层序遍历则是广度优先BFS逐层往下扫。很多讨论里会提到“按层遍历”“层序遍历”这里顺手讲掉也方便你把它和前面三种放在一起对比。4.1 队列实现按层扫描void levelOrder(TreeNode* root) { if (!root) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }队列保证先进先出所以同一层从左到右依次扩展先处理到的节点它的孩子也会先被处理这样就实现了按层推进。对测试树输出是 1 2 3 4 5 6。注意层序并不是三种遍历之一它是另一种维度上的遍历方式。面试题里经常会出现“按层输出二叉树每层放一个数组”的变体做法是在 while 循环里先记下当前队列长度size q.size()然后连续弹出 size 个节点把这些节点单独作为一层收集起来再进入下一层。这个技巧在很多“之字形打印”“按层统计节点数”的题目里都能复用。4.2 DFS 与 BFS 的选型对比四种遍历用哪个取决于你要解决什么问题。我把常见场景列个表遍历方式数据结构典型用途先序栈递归或显式复制一棵树、二叉树序列化中序栈递归或显式二叉搜索树有序输出、找第 k 小后序栈递归或显式删除整棵树、表达式树求值、求树高层序队列最短路径、按层统计、判断完全二叉树空间复杂度上也值得记一下DFS 的栈空间取决于树高 h最坏是 O(h)层序 BFS 的空间取决于某一层的最大节点数最坏是 O(w)。对于一棵完全二叉树BFS 的空间通常更可控对于斜树DFS 深一点但仍能用BFS 反而要维护较宽的队列。没有绝对好坏按场景选。5. 高频翻车现场与排查手册带过不少新同事也看过很多刷题群里的提问二叉树遍历的翻车点来来回回就那么几个。下面整理成速查遇到问题直接对着查。5.1 编译和运行错误速查表现象可能原因排查/解决Segmentation fault对 nullptr 解引用比如递归边界漏了 root nullptr每个遍历函数入口先判空非递归里访问 cur-val 前确认 cur 不为空Stack overflow递归深度太大树退化成链改用非递归实现或先让树尽量平衡输出顺序不对递归三个语句顺序写反非递归压栈顺序写反用固定测试树跑一遍对比标准输出程序不停止死循环非递归后序标记法忘记标记 visited中序 cur 指针没有右移检查每次弹栈后 cur 是否更新标记法必须有 visited 标志编译报 Microsoft Visual C 14.0 or greater is required环境缺 VS Build Tools常见于装带 C 扩展的包或使用 vcpkg按提示安装 VS Build Tools跟代码逻辑无关另外补一句环境的事VS Code 里写 C 如果连“hello world”都跑不起来多半是 tasks.json 和 launch.json 没配好不是遍历代码的问题。我建议先用命令行把编译器调通再回到二叉树遍历上否则环境问题和代码问题混在一起特别浪费精力。5.2 顺序全错但不报错的隐蔽陷阱最坑的错误不是崩溃而是程序跑得很欢结果却是错的。比如后序标记法如果忘了把 visited 标志重新入栈写成了这样// 错误示范结果其实是先序遍历 void postorderWrong(TreeNode* root) { stackpairTreeNode*, bool st; st.push({root, false}); while (!st.empty()) { auto [cur, visited] st.top(); st.pop(); if (!cur) continue; cout cur-val ; // 错第一次经过就输出 st.push({cur-right, false}); st.push({cur-left, false}); } }这段代码对测试树输出的是 1 2 4 5 3 6也就是先序结果。程序不会崩也不报错但遍历逻辑完全不对。所以做题时只把“能跑出结果”当通过是不够的一定要拿几棵不同的树对比标准输出才能发现这种隐蔽错误。注意程序不报错不代表写对了。每次改完遍历至少拿一棵非满二叉树验证输出顺序比如上面那棵测试树就能暴露大多数“错序但能跑”的问题。5.3 三个自测方法确认遍历写对了手算一棵固定树用上面那棵测试树先把期望结果写在本子上程序输出和你手写的一致基本说明当前实现没问题。交叉验证学过“前序中序可以唯一确定一棵二叉树”之后你可以把程序生成的先序和中序拿来回推树看能不能还原出原树推不出来遍历大概率有问题。边界测试至少跑空树、只有根节点、只有左子树的斜树、只有右子树的斜树、完全二叉树这五组。很多人只在满二叉树上测试结果斜树上出了 bug 都不知道。边界测试里有两组非常值得注意只有左子树的链 1-2-3先序是 1 2 3中序是 3 2 1后序也是 3 2 1只有右子树的链 1-2-3先序是 1 2 3中序是 1 2 3后序是 3 2 1。看到中序在不同形态下会剧烈变化你就会理解为什么“先左后右”的分支处理对中序影响这么大。最后说点实在的。我带新人时发现非递归后序是很多人卡得最久的地方一卡就是一下午。其实它没有玄学核心就一句话递归帮你隐藏了栈的细节非递归只是把这个栈显式地写出来。你先手动走几遍上面那棵小树再把代码敲三遍基本就能形成肌肉记忆。学完之后我建议顺手把 LeetCode 144、94、145 和 102 四道题做了做完你会觉得二叉树遍历真的很死板——只要套路对了剩下的就是体力活。如果你在验证过程中发现自己的遍历结果和参考值对不上优先检查三个地方递归边界有没有判空、输出语句的位置、非递归里栈的压入顺序九成问题都出在这三个地方。