老实说二叉树遍历是那种“上课一听就懂、拿起键盘就卡壳”的经典题目。递归版本三五行搞定非递归版本一写就晕尤其是后序不知道卡过多少人。我当年第一次写非递归后序对着空指针和栈标记来回折腾了整整两天最后在草稿纸上把每次压栈、出栈的节点一个一个画出来才算真正弄明白。这篇就把 C 语言实现二叉树递归与非递归遍历这件事从头到尾讲透前序、中序、后序、层序四种方式全都有可直接运行的代码和逐步推演读完你不仅能抄作业还能理解每一步为什么要这么写。这篇文章适合正在学数据结构的同学、准备面试或者考研的人也适合那些会用递归但始终没搞懂“非递归到底是怎么模拟递归”的开发者。我会先讲清楚递归版遍历背后的调用栈逻辑再讲非递归版如何用显式栈复刻这套流程最后聊一聊层序遍历以及实际调试中踩过的坑。这个过程说白了就是先把递归吃透再用栈把递归“翻译”成循环翻译得多了你对程序运行的理解会上一个台阶。1. 整体设计与思路拆解1.1 为什么“递归好写非递归难写”递归版本之所以简单是因为编译器替你维护了一个隐藏的调用栈。每次递归调用当前函数系统都会把当前的局部变量、返回地址压栈等子调用返回之后再弹栈恢复现场。也就是说你在代码里写“先遍历左子树再遍历右子树”实际上是在不断压栈和弹栈只是这部分工作交给了运行时。非递归版本则要求你把这个隐藏的调用栈用代码明确地模拟出来自己控制“什么时候压栈、什么时候出栈、出栈之后做什么”。大多数人写非递归前序没问题因为“先访问当前节点再处理左右孩子”这个顺序和栈的 LIFO 特性刚好合拍。到了中序就开始别扭因为要先一路压到最左弹栈访问之后再转向右子树。到了后序更麻烦根节点要等左右子树都处理完才能访问你无法靠“出栈一次就访问”完成全部流程必须想办法记住“这个节点的右子树到底处理完了没有”。这些差异不是靠背代码能解决的而是必须理解“栈顶元素代表什么状态”。1.2 递归与非递归的等价关系递归遍历的调用过程可以画成一棵递归树。比如对某个节点 root 调用中序遍历它会先对 root-left 调用同样函数这个过程遇到左孩子又继续对左孩子的左孩子调用一路到底直到遇到空节点。此时函数开始返回每返回一层就处理一个节点的根值然后转向它的右子树。非递归中序做的其实是一模一样的事用一个显式栈保存“我还没处理完的祖先节点”先沿左链一路压栈压到空指针后出栈访问再转向右孩子。你可以这样理解递归代码里函数被调用时当前节点被隐式地压进了系统栈非递归代码里则是你手动把当前节点压进自己的栈。两个版本唯一的区别是系统栈由操作系统管理你的栈由写在代码里的数据结构管理。理解了这一层后面看各种非递归实现就不会再觉得是魔术。1.3 关于存储结构的选择很多教材喜欢用数组存完全二叉树因为下标 2i 和 2i1 可以直接定位孩子节点。但实际题目里遇到的二叉树大概率不是完全二叉树用数组存会出现大量空洞纯粹浪费空间。所以本文采用更通用的二叉链表结构每个节点保存数据域和左右孩子指针。这种结构对递归、非递归、层序的适配性都很好也贴近真实工程里最常见的二叉树实现。下面是我习惯用的节点定义后面所有代码都基于它#include stdio.h #include stdlib.h #include string.h #define MAXN 1024 #define EMPTY 0 // 数组中 0 表示空节点 typedef struct Node { int data; struct Node *left; struct Node *right; } Node;代码结构上我建议你把栈、队列、树的定义放在同一个 .c 文件里先跑通整体之后再按头文件、源文件的方式拆开。学习阶段最忌讳一开始就考虑模块化过度设计先把核心逻辑跑通比什么都重要。2. 先把地基打好树的构建与打印2.1 如何快速手动造一棵测试树写遍历代码之前至少要有一棵能用的树。手动一个个 malloc 然后指来指去太痛苦我一般用一个辅助函数根据先序序列递归建树。序列里用 0 表示空节点每次读取一个值如果是 0 就返回 NULL否则创建节点先递归建左子树再递归建右子树。Node* buildTree(int arr[], int *idx, int len) { if (*idx len) return NULL; if (arr[*idx] EMPTY) { (*idx); return NULL; } Node *node (Node *)malloc(sizeof(Node)); node-data arr[*idx]; (*idx); node-left buildTree(arr, idx, len); node-right buildTree(arr, idx, len); return node; }这个函数之所以采用先序顺序是因为先序序列是“根-左-右”只要固定了根的位置就能确定左子树和右子树各自的边界。比如下面这棵测试树1 / \ 2 3 / \ \ 4 5 6 / 7它的先序序列是{1, 2, 4, 7, 0, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0}。手动写这个序列的时候要格外小心节点 4 有个左孩子 7那 7 的两个孩子都是空所以 7 后面要跟两个 0节点 4 没有右孩子所以 7 的两个 0 之后还要再补一个 0接着才是节点 5。很多初学者在这里序列写错导致建出来的树和自己预期完全不一样。2.2 建树之后先跑一个遍历验证可以在 main 函数里先建树再调用一个最简单的递归先序打印看看建出来的树对不对void printPreorder(Node *root) { if (root NULL) return; printf(%d , root-data); printPreorder(root-left); printPreorder(root-right); } int main() { int arr[] {1, 2, 4, 7, 0, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0}; int idx 0; Node *root buildTree(arr, idx, sizeof(arr) / sizeof(arr[0])); printPreorder(root); printf(\n); return 0; }如果输出是1 2 4 7 5 3 6说明树构建正确。后面所有遍历代码都以这棵树作为测试基准统一数据才好对比不同算法的输出差异。3. 递归遍历三行代码背后的调用栈逻辑3.1 前序、中序、后序递归差别只在访问位置递归遍历可以写成同一种模板只是 printf 的位置不同void preorder(Node *root) { if (root NULL) return; printf(%d , root-data); // 前序在递归左子树之前访问 preorder(root-left); preorder(root-right); } void inorder(Node *root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); // 中序左子树访问完回到当前节点时访问 inorder(root-right); } void postorder(Node *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-data); // 后序左右子树都访问完才访问当前节点 }前序对测试树的输出是1 2 4 7 5 3 6中序是7 4 2 5 1 3 6后序是7 4 5 2 6 3 1。这三个结果后面会反复用到你可以先记下来等写完非递归版本比对输出是否一致。为什么仅仅调整 printf 的位置就能得到三种完全不同的顺序关键在于访问节点和递归调用谁先谁后。前序遍历要求“当前节点先被处理再处理子树”中序要求“左子树处理完回到当前节点时处理”后序要求“左右都处理完回到当前节点时才处理”。递归代码里访问位置代表的就是当前调用层“恢复现场后第一件要做的事”。3.2 用一个具体例子拆解递归全过程以中序遍历为例拿测试树从头推一遍。第一次调用 inorder(1)root 非空于是先调用 inorder(2)。在 inorder(2) 里又先调用 inorder(4)在 inorder(4) 里又先调用 inorder(7)。inorder(7) 里先调用它的左孩子发现是 NULL直接返回然后 printf 7再调用右孩子 NULL返回。于是 inorder(7) 结束回到 inorder(4) 的调用现场printf 4再调用右孩子 NULL返回。再回到 inorder(2) 的调用现场printf 2再调用右孩子 inorder(5)inorder(5) 先调用左孩子 NULL然后 printf 5再调用右孩子 NULL结束。回到 inorder(1)printf 1再处理右子树得到 3 和 6。这就是7 4 2 5 1 3 6的来历。你可以注意到递归调用过程中函数并没有“跳到”子节点直接把当前节点丢弃而是先把当前节点相关信息压入系统栈等子树处理完再弹出来继续。非递归版本的核心工作就是把“压在系统栈里的信息”换到我们自己定义的栈里逻辑一样只是控制权握在自己手里。3.3 递归虽然简单但有两个明显短板短板一是深度受限。递归深度等于树的高度如果是一棵高度为几万的退化树每个节点都只有一个孩子递归会反复压栈最终导致栈溢出。短板二是对于“层序”这种天然需要先处理同一层所有节点的问题递归并不好写因为递归的结构是“沿着一条分支一直深入”而层序要求一层一层横向推进。这就是为什么后文要专门讨论非递归和层序遍历。注意如果你的递归遍历在测试大树时突然崩溃先别急着怀疑代码逻辑多半是函数调用栈不够用了。可以小规模测试代码逻辑再考虑用非递归替换。4. 非递归遍历用栈还原递归现场4.1 前序非递归压栈顺序是关键前序非递归是所有非递归实现里最友好的核心思路是根节点先入栈循环里弹出栈顶节点并访问然后把右孩子、左孩子依次压栈。为什么先压右孩子再压左孩子因为栈是后进先出后压进去的左孩子会先被弹出这样就能保证处理顺序是根、左、右。void preorderNonrec(Node *root) { if (root NULL) return; Node *stack[MAXN]; int top -1; stack[top] root; while (top 0) { Node *cur stack[top--]; printf(%d , cur-data); if (cur-right) stack[top] cur-right; if (cur-left) stack[top] cur-left; } }用测试树走一遍根 1 入栈弹出 1 并访问压入 3 再压入 2下次弹出 2压入 5 和 4再弹出 4压入 7弹出 7。输出是1 2 4 7 5 3 6和递归前序完全一致。如果不小心把压栈顺序写反先压左孩子再压右孩子输出就会变成1 3 6 2 5 4 7这是我初学时长踩的坑。4.2 中序非递归空指针时不要慌中序非递归比前序复杂一点核心思路是沿左链持续入栈直到遇到空指针然后出栈访问再转向当前节点的右子树。循环的推进条件是“当前指针不为空时入栈并往左走当前指针为空时出栈访问并往右走”。void inorderNonrec(Node *root) { Node *stack[MAXN]; int top -1; Node *cur root; while (top 0 || cur ! NULL) { if (cur ! NULL) { stack[top] cur; cur cur-left; } else { cur stack[top--]; printf(%d , cur-data); cur cur-right; } } }代码里的 while 条件top 0 || cur ! NULL很容易写漏如果只写top 0那么一开始栈是空的root 非空时根本进不了循环。另一个常见错误是出栈访问之后忘记把 cur 指向右孩子导致只输出左链上的节点。这个分支一漏整个遍历会在左子树走到底之后卡死或乱序。用测试树推演开头几步cur 从 root1 进入连续压栈 1、2、4、7直到 7 的左孩子为空。此时出栈输出 7cur 指向 7 的右孩子 NULL再次循环cur 为空出栈输出 4cur 指向 4 的右孩子 NULL再次出栈输出 2cur 指向 5……整个过程就是不断“深入左链、后退一步、处理右子树”。4.3 后序非递归最需要慢慢啃的一块后序非递归难在根节点不能最先弹出访问它必须等左右子树都处理完才能输出。我常用的实现是给每个入栈节点加一个 visited 标记标记为 0 表示“这个节点已经入栈但它的子树还没处理完”标记为 1 表示“左右子树都处理完了现在可以输出”。typedef struct { Node *node; int visited; } StackElem; void postorderNonrec(Node *root) { StackElem stack[MAXN]; int top -1; if (root NULL) return; stack[top] (StackElem){root, 0}; while (top 0) { StackElem *cur stack[top]; if (cur-visited 0) { cur-visited 1; if (cur-node-right) stack[top] (StackElem){cur-node-right, 0}; if (cur-node-left) stack[top] (StackElem){cur-node-left, 0}; } else { printf(%d , cur-node-data); top--; } } }这个方案的本质是什么是在节点第一次出现在栈顶时先不输出而是把它重新标记为“已处理过”然后把右孩子和左孩子依次压栈。由于栈后进先出左孩子会先被处理等右孩子也处理完了栈顶又会回到这个标记成 1 的祖先节点此时才输出它。测试树推演开头初始栈里是(1,0)。栈顶标记为 0于是改成(1,1)压入右孩子(3,0)和左孩子(2,0)。此时栈顶是(2,0)处理它改成(2,1)压入(5,0)和(4,0)。栈顶(4,0)处理改成(4,1)压入(7,0)。栈顶(7,0)处理改成(7,1)它没有孩子什么都不压。下一次循环发现 visited1输出 7 并弹出。接着栈顶是(4,1)输出 4弹出再输出 5、2、6、3、1得到7 4 5 2 6 3 1和递归完全一致。注意后序还有一种实现是“用两个栈”一个栈存节点指针一个栈存标记本质思路和我上面的版本一样只是把标记独立出来。两种写法你可以都试一下我更喜欢上面这种把标记揉进栈元素的写法因为代码更紧凑不容易忘更新标记。4.4 三种非递归的思想差异表遍历方式核心思想栈的作用最容易出错的地方前序出栈即访问右先压、左后压保存等待访问的节点压栈顺序颠倒中序沿左链压栈到底空则出栈访问再转右保存左链上尚未访问的祖先循环条件少写一半或出栈后忘转右后序标记第二次出现在栈顶才允许输出保存等待子树处理完的祖先忘记修改标记导致死循环这张表你可以贴在电脑旁边写代码之前先默念一遍对应行的思想。实际面试或者考试时只要能把核心思想讲清楚代码细节略有不完整面试官通常也会给分。5. 层序遍历队列让二叉树换个姿势输出5.1 层序非递归实现层序遍历不能再靠栈了因为每一层是从左到右横向推进正好符合队列的先进先出特性。思路是先将根节点入队然后循环取出队头节点并访问将其左孩子、右孩子依次入队。队列为空时结束。typedef struct { Node *data[MAXN]; int head, tail; } Queue; void initQueue(Queue *q) { q-head q-tail 0; } void enQueue(Queue *q, Node *node) { q-data[q-tail] node; } Node* deQueue(Queue *q) { return q-data[q-head]; } int isEmptyQueue(Queue *q) { return q-head q-tail; } void levelOrder(Node *root) { if (root NULL) return; Queue q; initQueue(q); enQueue(q, root); while (!isEmptyQueue(q)) { Node *cur deQueue(q); printf(%d , cur-data); if (cur-left) enQueue(q, cur-left); if (cur-right) enQueue(q, cur-right); } }对测试树的层序输出是1 2 3 4 5 6 7。这里要注意队列的尾指针只会增加如果 MAXN 不够大会越界。上面的简单实现适合固定大小的测试数据实际做题目时建议改成环形队列或者使用动态扩容的队列。5.2 层序还能顺手解决哪些问题层序遍历是很多“按层处理”问题的基础。比如想按层打印可以在遍历时额外维护一个 level 变量每当一层结束时换行想求树的最大宽度可以在每次进入下一层前记录当前队列长度取最大即可想求树的最小深度层序遍历一旦遇到第一个叶子节点直接返回当前层数这比递归深搜要直观得多。我在实际项目里需要按层输出二叉树结构时用的就是这个思路层序遍历每一层累积所有节点值在层结束时一起输出。这样做的好处是能保证节点从左到右的顺序不被递归搜索的路径打乱。6. 常见错误与排查技巧实录6.1 段错误的排查套路我见过最多的段错误来自两个方面一是建树时数组下标越界二是非递归遍历时把空指针压栈或访问了空指针成员。排查建议是先用固定小规模的测试树跑递归版本确保输出正确再跑非递归版本如果段错误使用调试器定位崩溃行。如果崩溃发生在访问cur-data说明 cur 是空指针如果发生在函数调用深处多半是构建序列写错导致建出无限深度的树。另外一个隐蔽问题是递归建树函数里忘记更新数组下标。buildTree 函数里每次读到一个非 0 值就要自增 idx然后再递归左右子树。如果漏了自增同一个位置会被反复读取树的结构会完全错乱。这是很多人卡住却想不到检查的位置。6.2 遍历结果错乱时先检查顺序如果你的非递归前序输出成了“根、右、左”不用怀疑算法原理去检查压栈顺序。栈是后进先出想要“左先出栈”就必须“左后入栈”所以代码里要先压右再压左。中序如果输出缺了前半段检查 while 条件里有没有cur ! NULL这一半。后序如果死循环检查栈顶元素的 visited 标记有没有从 0 改成 1。我调试的时候喜欢在每个循环打印“当前栈顶元素、栈顶标记、当前指针”这样能把错误定位到具体一步。比如中序里当 cur 一直不前进时打印一下就能发现出栈后没有把 cur 指向右孩子。6.3 一个可以直接复用的测试框架我写这类代码时从不直接丢进题目系统里而是先组成一个本地测试函数把所有遍历结果打印出来和理论结果比对。下面是一个简单的 main 函数你可以直接拿走用int main() { int arr[] {1, 2, 4, 7, 0, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0}; int idx 0; Node *root buildTree(arr, idx, sizeof(arr) / sizeof(arr[0])); printf(递归前序: ); preorder(root); printf(\n); printf(非递归前序: ); preorderNonrec(root); printf(\n); printf(递归中序: ); inorder(root); printf(\n); printf(非递归中序: ); inorderNonrec(root); printf(\n); printf(递归后序: ); postorder(root); printf(\n); printf(非递归后序: ); postorderNonrec(root); printf(\n); printf(层序: ); levelOrder(root); printf(\n); return 0; }跑一遍之后你会发现递归和非递归输出完全相同这说明你的非递归实现真正等价于递归。不要小看这步很多网上代码看着对实际跑起来顺序是错的。7. 实际应用与进一步扩展7.1 释放二叉树内存必须用后序有一种场景可以立刻检验你对后序的掌握程度释放整棵树。如果先释放根节点再释放左右子树代码会先 free(root)之后再去访问 root-left这就是典型的野指针访问。正确做法是先递归释放左右子树再释放根节点void freeTree(Node *root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); }7.2 中序、前序在搜索树和序列化中的应用如果节点是一棵二叉搜索树中序遍历的结果一定是递增序列。所以“验证一棵树是不是二叉搜索树”可以直接改成中序遍历它检查输出是否严格递增。前序遍历则常用于序列化把树按先序输出到数组或字符串之后用类似 buildTree 的方式重建。后序在某些场景适合先处理完子树再做汇总计算比如表达式二叉树后序输出的就是后缀表达式非常像编译器处理表达式时的顺序。7.3 想进一步提升可以试试 Morris 遍历当你把非递归遍历彻底写熟之后可以了解更加进阶的遍历方法。Morris 遍历能做到不用额外栈和队列只用 O(1) 额外空间完成前序、中序、后序它的核心是你把当前节点的左子树最右空指针临时指向当前节点相当于借用叶子节点的空指针做“回溯标记”。这已经超出了本文范围但如果你把本文讲的递归、显式栈都吃透了再去看 Morris 会发现很多“咦原来是把递归压栈的线索藏到了空指针里”的顿悟感。但是我必须提醒一句面试或考试时先写递归版本没问题要能说清楚递归版本背后的调用栈逻辑需要优化时再切换非递归版本能讲明白为什么栈能替代递归只有被追问到空间复杂度极致优化才需要上 Morris。别一上来就背一个 Morris 花式遍历的代码那几个旋转空指针的细节背起来容易忘起来也快。最后分享一个小技巧。写非递归遍历之前我永远会在纸上先把树画出来然后给每个节点标一个序号比如先序访问顺序是 1、2、4、7、5、3、6然后再去对照代码里每一步出栈节点。这样做最大的好处是当代码输出和预期不一致时你能立刻知道是“第几步”出了问题而不是盲目加打印重跑。这个过程看起来慢但对于真正理解二叉树遍历比我见过任何一个花哨的调试器都管用。
