递归和非递归遍历这个话题我前后给不同水平的读者讲过很多遍。很多人在初学二叉树时感觉递归版本三五行就搞定非递归版本却要换个栈绕来绕去总有一种“能用递归就懒得写非递归”的心态。实际上递归版本隐藏了函数调用栈的进出过程而真正理解二叉树的访问顺序恰恰需要你亲手把那个“隐藏的栈”用代码表达出来。这篇文章我就用C语言把递归和非递归的三种深度优先遍历全部写一遍再加上层序遍历顺便把创建二叉树、栈和队列的辅助实现都补齐让你能直接编译运行边跑边看结果。这篇文章适合正在复习数据结构、准备笔试面试的初学者也适合想快速重拾二叉树遍历细节的开发者。我会从“为什么要区分递归和非递归”讲起给出完整代码和运行结果最后分享一些我在调试这类代码时踩过的坑。看完之后你可以照着代码一步步跟也可以把它当成一份可复用地的手册下次遇到树的题目直接查。1. 二叉树基础与递归遍历1.1 链式存储与创建方式C语言里写二叉树最通用的结构体定义长这样typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree;每个节点只存三种信息当前节点自己的数据、左孩子指针、右孩子指针。叶子节点的左右孩子指针都指向NULL这是遍历过程中判断“能不能继续往下走”的关键条件。有了结构体之后还得解决“怎么从输入构建一棵树”。我习惯用先序序列配合空标记来创建输入中遇到特殊字符#就表示这个子树位置为空。比如序列AB#D##C##代表的是一棵特定形状的树创建函数的逻辑是典型的递归读到一个非空字符就创建当前节点然后递归创建左子树再递归创建右子树。BiTree createTree(char **str) { if (**str # || **str \0) { (*str); return NULL; } BiTree node (BiTree)malloc(sizeof(BiTNode)); node-data **str; (*str); node-lchild createTree(str); node-rchild createTree(str); return node; }我建议初学者自己动手画一画这棵树然后对照序列手动模拟一遍递归创建过程。只要这一步理解了后面理解遍历递归同样会顺畅很多。1.2 递归遍历为什么代码能这么短递归遍历的核心思想非常简单一棵二叉树本身由“根节点、左子树、右子树”组成那么遍历一棵树的问题就能拆成“处理根节点 遍历左子树 遍历右子树”三个子问题。因为左右子树仍然是二叉树所以同一个函数可以反复调用自己直到遇到NULL节点才返回。先序、中序、后序的唯一区别在于“访问根节点”这个动作放在什么位置。访问动作可以是打印、计数、累加也可以是其他业务逻辑。下面给出最常见的打印版本void preorderRecursive(BiTree root) { if (root NULL) return; printf(%c , root-data); // 先访问根 preorderRecursive(root-lchild); preorderRecursive(root-rchild); } void inorderRecursive(BiTree root) { if (root NULL) return; inorderRecursive(root-lchild); printf(%c , root-data); // 中序左、根、右 inorderRecursive(root-rchild); } void postorderRecursive(BiTree root) { if (root NULL) return; postorderRecursive(root-lchild); postorderRecursive(root-rchild); printf(%c , root-data); // 后序左、右、根 }三份代码唯一的不同就是printf(%c , root-data)这行代码的位置。很多人背顺序靠口诀“先根左右、中左根右、后左右根”但我一直觉得单纯背口诀不如理解调用顺序。你只要记住一句话递归函数在做同样的事把当前节点当作根来处理子问题就交给下一层递归顺序就自然写出来了。1.3 递归背后的调用栈递归之所以能跑起来是因为编译器和运行时系统维护了一个函数调用栈。每次进入preorderRecursive函数系统会为该次调用分配一块栈帧里面保存了返回值地址、参数root、局部变量等信息。当函数内部再次调用自身时新的栈帧压在旧的上面当前一层的子调用全部返回后栈帧弹出程序回到上一层继续执行。我用一个很简单的例子说明。假设树的结构是A / \ B C / \ D EpreorderRecursive(A)执行printf输出A然后调用preorderRecursive(B)。这时候A这一帧还在栈里等着B这一帧入栈。B输出B接着调用preorderRecursive(D)。D输出D左右子树都是NULLD函数返回B函数继续调用preorderRecursive(E)E输出E后返回B整个函数执行完毕返回A再继续调用preorderRecursive(C)C输出C后结束。所以最终结果是A B D E C。如果你在调试器里观察函数调用栈就能看到这种“往下钻、再往回退”的过程。理解了这一步非递归版本其实就是在用一个我们自己创建的栈来模拟这套行为只是栈里存的不是函数栈帧而是树的节点指针。2. 非递归遍历为什么要绕开递归2.1 递归的局限与栈模拟思路递归代码好写但不见得总是好用。每次函数调用都会消耗系统栈空间树的深度过大时比如一条链状的树有十万个节点函数调用深度会跟着到十万层系统栈往往只有几兆到几兆字节很容易栈溢出。非递归版本手动管理栈能在堆上分配空间容量可控而且逻辑明明白白不会出现“调用栈爆炸”的问题。除了稳定性面试和笔试也特别喜欢考非递归。原因很简单递归版本谁都会写但能把递归转换为迭代说明你真正看懂了“访问顺序到底是怎么形成的”。很多人一遇到非递归就懵归根到底是没想清楚一个关键问题栈里应该压什么什么时机弹出弹出之后下一步做什么以深度优先遍历来说非递归遍历需要在栈里保存“当前还没处理完的节点”。因为在树上往下走时我们随时可能要回到之前路过的节点而栈的后进先出特性刚好合适后遇到的子树先处理完先遇到的祖先节点最后处理完。这实际上和递归的函数调用顺序完全一致。2.2 手写栈的完整实现为了不依赖操作系统栈我要自己准备一个栈结构。这里用数组实现为了简化问题栈容量先固定为100足够应付演示场景。实际项目中你可以改成动态扩容版本逻辑大同小异。#define MAXSIZE 100 typedef struct { BiTree data[MAXSIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int push(Stack *s, BiTree node) { if (s-top MAXSIZE - 1) return 0; s-data[(s-top)] node; return 1; } int pop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node s-data[(s-top)--]; return 1; } int getTop(Stack *s, BiTree *node) { if (isEmpty(s)) return 0; *node s-data[s-top]; return 1; }top初始为-1入栈时先加一再写入出栈时先取出再减一。这个设计可以把“栈顶指针”理解为指向当前有效元素的索引而不是下一个空位置写起来比较直观。我在对照递归过程时用得最多的操作是getTop因为很多非递归算法的下一步要根据栈顶节点的情况来决定而并不急着弹出。2.3 前序和中序非递归的核心区别先看前序非递归。前序是“根左右”也就是说每遇到一个节点第一件事就是访问它然后再去处理子树。这时候访问完当前节点后需要先把右子树压栈再把左子树压栈。因为栈是后进先出先压右树下一轮才能先弹出左树保证左子树先被处理。void preorderIter(BiTree root) { Stack s; initStack(s); if (root ! NULL) push(s, root); while (!isEmpty(s)) { BiTree node; pop(s, node); printf(%c , node-data); if (node-rchild) push(s, node-rchild); if (node-lchild) push(s, node-lchild); } }整个过程可以这样理解栈顶永远放着“下一个要处理”的节点。弹出时立即打印打印完把自己的左右子树按“右先左后”压栈就能保持“先左边后右边”的遍历顺序。中序非递归就更有意思了。中序是“左根右”所以不能一遇到节点就打印得先把左子树整个处理完才能访问当前节点。实现思路是从根节点开始一直沿左子树往下走沿途经过的节点全部压栈直到左孩子为NULL然后弹出栈顶节点这个节点一定是“左子树已经处理完”的节点打印它随后把当前指针移到它的右子树对右子树重复同样的过程。void inorderIter(BiTree root) { Stack s; initStack(s); BiTree cur root; while (cur ! NULL || !isEmpty(s)) { while (cur ! NULL) { push(s, cur); cur cur-lchild; } pop(s, cur); printf(%c , cur-data); cur cur-rchild; } }这里最容易出错的地方在循环结束条件。很多初学版本只写了while (!isEmpty(s))结果当栈空但cur不为NULL时循环提前退出导致漏掉节点。正确条件是cur ! NULL || !isEmpty(s)栈空不能作为唯一结束标志因为刚弹出最后一个节点后它的右子树可能还没处理。我建议你手动拿一棵三个节点的树完整走一遍中序过程。比如树是B为根B有左孩子A和右孩子C中序应该是A B C。第一步一直走到最左的A并压栈然后弹A打印再移动到A的右子树NULL此时栈里还有B弹B打印移动到CC入栈弹C打印。总共执行了A B C每一步都清晰可见。2.4 后序非递归两种易用方案后序“左右根”是非递归里最麻烦的一个因为根节点必须等左右子树都处理完之后才能打印。如何在代码里判断“当前节点的左右子树都处理完了”我在这里给两种比较实用的方案。方案一双栈法双栈法的思路很巧妙。既然后序遍历是“左右根”那我能不能先求出一个“根右左”的序列然后反转成“左右根”前序遍历很容易实现是“根左右”。只要把前序中压栈的顺序稍微改一下变成先压左孩子再压右孩子遍历出来的结果就是“根右左”。把每一次访问到的节点压到第二个栈里最后把第二个栈全部弹出顺序就是后序。void postorderIterTwoStack(BiTree root) { if (root NULL) return; Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTree node; pop(s1, node); push(s2, node); if (node-lchild) push(s1, node-lchild); if (node-rchild) push(s1, node-rchild); } while (!isEmpty(s2)) { BiTree node; pop(s2, node); printf(%c , node-data); } }你可能会疑惑为什么push(s1, node-lchild)和push(s1, node-rchild)的顺序和前序正好相反因为s1弹出某个节点后会把左右子树入栈而栈的后进先出会让下一次优先弹出后压入的那一个。先压左再压右弹出的顺序就是先右后左于是s2中收集到的顺序就成了“根右左”。把s2倒序输出就得到“左右根”。方案二单栈标记法双栈法逻辑简单但需要两个栈。如果只想用一个栈最常用的办法是在栈里给每个节点附带一个状态标记表示“当前节点的左子树处理完了还是右子树也处理完了”。typedef struct { BiTree ptr; int flag; } StackElem; void postorderIterOneStack(BiTree root) { StackElem stack[MAXSIZE]; int top -1; BiTree cur root; while (cur ! NULL || top ! -1) { while (cur ! NULL) { stack[top].ptr cur; stack[top].flag 0; cur cur-lchild; } while (top ! -1 stack[top].flag 1) { printf(%c , stack[top--].ptr-data); } if (top ! -1) { stack[top].flag 1; cur stack[top].ptr-rchild; } } }这段代码的意思归纳为先把从当前节点出发的所有左孩子压栈标记都为0表示左子树还没处理完。当左子树到底之后检查栈顶如果栈顶节点的flag为0说明左子树已经遍历完轮到处理右子树于是把flag改成1然后把当前指针切换到右子树继续重复“往左钻”的过程。如果flag为1说明右子树也已经处理完这时弹出并打印节点。单栈法的优势是省空间但理解起来需要一点时间。我建议第一次接触时先跑双栈版把结果跑对了再回头把单栈版和递归调用的函数栈帧对照着看会更容易接受。3. 层序遍历与完整测试3.1 用队列实现层序遍历深度优先遍历是沿着一条路走到黑再回头。层序遍历则是按“层级”从上到下、从左到右逐个访问比如根节点一层、它的左右孩子一层、再下一层。层序遍历不能用栈得用队列因为先进来的节点要先被处理符合“一层一层推进”的逻辑。队列可以用数组模拟循环队列也可以用链表。为了和之前的栈代码保持一致我用数组加front和rear两个指针来实现#define QUEUE_MAX 100 typedef struct { BiTree data[QUEUE_MAX]; int front; int rear; } Queue; void initQueue(Queue *q) { q-front 0; q-rear 0; } int isQueueEmpty(Queue *q) { return q-front q-rear; } int enQueue(Queue *q, BiTree node) { if ((q-rear 1) % QUEUE_MAX q-front) return 0; q-data[q-rear] node; q-rear (q-rear 1) % QUEUE_MAX; return 1; } int deQueue(Queue *q, BiTree *node) { if (isQueueEmpty(q)) return 0; *node q-data[q-front]; q-front (q-front 1) % QUEUE_MAX; return 1; } void levelOrder(BiTree root) { Queue q; initQueue(q); if (root ! NULL) enQueue(q, root); while (!isQueueEmpty(q)) { BiTree node; deQueue(q, node); printf(%c , node-data); if (node-lchild) enQueue(q, node-lchild); if (node-rchild) enQueue(q, node-rchild); } }队列容量这里预留了一个空位来区分队列满和队列空所以实际能存99个节点。对于演示级别的树完全够用。如果你想处理更大规模的数据可以把队列改成链式存储逻辑是一样的。3.2 创建一棵测试树并验证结果光看代码不够直接跑一遍最直观。为了测试所有遍历函数我写了一个main函数按先序序列创建一棵固定树。假设树的形状是A / \ B C / \ \ D E F对应的先序序列为ABD##E##C#F##。其中#表示空节点。注意看C只有右孩子F所以C后面先是一个#表示左孩子为空再是F最后两个#表示F的左右孩子为空。int main() { char *str ABD##E##C#F##; BiTree root createTree(str); printf(先序递归: ); preorderRecursive(root); printf(\n); printf(中序递归: ); inorderRecursive(root); printf(\n); printf(后序递归: ); postorderRecursive(root); printf(\n); printf(先序非递归: ); preorderIter(root); printf(\n); printf(中序非递归: ); inorderIter(root); printf(\n); printf(后序非递归(双栈): ); postorderIterTwoStack(root); printf(\n); printf(后序非递归(单栈): ); postorderIterOneStack(root); printf(\n); printf(层序遍历: ); levelOrder(root); printf(\n); return 0; }编译运行后的输出应该是先序递归: A B D E C F 中序递归: D B E A C F 后序递归: D E B F C A 先序非递归: A B D E C F 中序非递归: D B E A C F 后序非递归(双栈): D E B F C A 后序非递归(单栈): D E B F C A 层序遍历: A B C D E F我特别想提醒你注意几个对应关系先序递归和非递归输出完全相同这验证了迭代版只是把递归的调用栈换成了显式栈中序同样如此两种后序非递归方法的结果也都一致说明两个不同思路实际上描述的是同一种遍历顺序。层序遍历按层输出根A、第二层B C、第三层D E F顺序清晰。如果你的运行结果和这个不一致多半是入栈顺序写反或者输入序列里的#数量不对。这时候不要急着改代码先在纸上画出树再手动模拟一遍往往比干瞪眼找bug快很多。4. 常见问题与避坑经验4.1 代码运行常见的坑栈容量不够前面写的固定大小为100的栈处理几十个节点的树没问题。但如果树的节点数超过容量压栈函数会返回0而我在演示代码里没有检查返回值结果就是元素丢失遍历结果莫名其妙。正式写代码时要么在push里处理扩容要么在调用处判断返回值缺一不可。空树处理很多遍历函数对空树返回的顺序很敏感。比如preorderIter在root为NULL时栈为空循环不执行函数自然结束这没问题。但单栈后序写法里如果cur初始为NULL且栈为空while (top ! -1 stack[top].flag 1)内部不会弹任何节点主循环判断条件cur ! NULL || top ! -1也很快退出输出为空。看起来输出空结果正确但如果你把空树的root传入某些没有初始化的函数可能访问野指针。建议在所有遍历函数开头先判断root NULL直接返回空结果。中序非递归循环条件写错我刚学的时候中序写成while (!isEmpty(s))遍历一个完整树时经常少打印右子树节点。原因前面提过栈空时cur可能还指向右子树必须把cur ! NULL纳入判断。这个错误非常隐蔽因为如果树刚好是完全二叉树可能结果碰巧是对的但只要右子树还有更深的节点漏节点问题就暴露了。后序单栈法搞混flag含义我见过很多人在单栈法里把flag0当作“右子树处理完”然后打印时机完全反了。要记住一个简单约定flag0表示这个节点刚刚入栈左子树还没处理flag1表示左子树已处理完接下来要处理右子树等右子树也处理完即遇到flag1且再次回到该节点时才允许打印。所以正确逻辑是初始入栈flag0出循环时遇到flag0就改成flag1并转到右子树遇到flag1就打印并弹出。次序反了输出就会变成“根左右”之类的前序遍历。4.2 怎么验证自己真的懂了我自己的经验是验证理解程度的最好办法不是默写代码而是拿着一个至少四层的树手动模拟每一步栈的变化。准备一张纸左边写树右边画栈每执行一步就把栈里从底到顶的元素列出来。举个例子中序遍历中第一次while (cur ! NULL)会一直压左孩子压到最底层。这时候栈里从底到顶是根、根的左孩子、左孩子的左孩子……你会看到栈底永远是最早的祖先节点栈顶是最新到达的节点。然后弹出栈顶并打印再切到它的右子树。这个过程模拟几轮以后自然就理解了“左根右”是怎么通过栈实现的。如果用手动模拟太慢我建议你在代码里临时加一个打印函数在每次入栈、出栈时输出当前栈内容。比如在inorderIter里压入一个节点后打印push: node-data弹出时打印pop: node-data运行结果就是完整的栈操作日志对照日志看代码会清楚很多。4.3 再往前一步可以做什么遍历是所有二叉树操作的基础会写递归和非递归之后可以顺手把下面几个问题一起练了用遍历序列重建二叉树已知先序和中序或者已知后序和中序重建整棵树。这个题目能反向检验你对遍历顺序的理解。线索化二叉树利用叶子节点空指针存前驱和后继信息让中序遍历不需要栈也能完成非递归遍历的延伸应用。表达式树求值把中缀表达式转成树用后序遍历求值那时你会再次感受到“后序遍历为什么适合计算”。层序遍历的变体比如按层输出、每层换行、之字形打印等这些题都是在层序基础上加点判断条件。这些扩展看着多但万变不离其宗。核心还是回到“栈模拟递归、队列模拟层次”这两个基本思路上。把今天这套C语言代码理解透了其他语言版本也就是换一层语法外壳而已。最后分享一个我调试时的小习惯在写非递归遍历前先写递归版本并把输出结果打印出来然后写迭代版本两个输出并排比较。只要某一条遍历顺序对不上就说明栈或队列的操作顺序有问题。这个方法虽然笨但排查效率很高比反复看代码猜错在哪里快得多。