直接看标题就知道这题没少折腾人。作为数据结构课的经典算法实操二叉树的中序、后序非递归遍历用C语言实现几乎是每一个学计算机的人绕不过去的坎。递归版本三行代码写完但一到非递归很多朋友就卡住了特别是后序硬是想不明白那个“第二次经过节点”怎么判断。这篇文章我用C语言把这俩遍历给你彻底讲透。不绕弯子直接讲栈模拟的思路、节点状态标记以及我在调试过程中踩过的坑。适合正在学数据结构的本科生、准备考研或面试刷算法的人也适合那些学完就忘、想一次性看明白的朋友。1. 既然递归能解决为什么还要用非递归先回答一个问得最多的问题递归它不香吗中序递归十行代码后序递归也就十行为什么要费劲去手工模拟栈答案取决于应用场景。递归本质上是使用系统调用栈每次函数调用都会发生压栈、跳转、返回、弹栈这一整套动作而且栈帧里还要保存局部变量、参数和返回地址。当二叉树深度比较大的时候递归版本很容易把调用栈撑爆。我在实际开发里没少被这种问题坑过Linux线程默认栈大小只有8MB如果树退化成一个长链深度到十万、百万级递归基本就game over了。非递归遍历把“栈”从系统调用栈换成了程序员自己管理的数据结构内存分配可控不会出现不可预期的爆栈。更重要的是非递归的每个步骤都是显式的不像递归那样把逻辑藏在函数调用里。在某些对性能要求苛刻的场景比如嵌入式开发、实时系统里少一次函数调用少一层栈帧就是实打实的性能收益。再有就是面试和考试。非递归遍历是面试官非常喜欢考察的点因为它能直接检验你是否真正理解了遍历的本质而不只是会背递归模板。能不能用自己的话讲清楚中序和后序的入栈、出栈时机基本上决定了这道题能不能拿满分。理解非递归遍历的前提是搞清楚递归版本到底做了什么。中序递归的顺序是先往左走到底打印再往右走。后序递归的顺序是先往左走到底再往右走到底最后打印。我们非递归要做的事情就是用一个显式栈把递归版本的隐式逻辑给复刻出来。2. 准备工作栈结构、节点定义与辅助函数既然是C语言实现准备工作就得做得扎实。C语言没有现成的泛型栈容器不像C里面有std::stack可以直接用所以一切从零开始。2.1 二叉树节点的结构体定义二叉树的节点结构体定义没有什么争议常见的形式是这样的typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;这里我用的数据域是int类型方便测试和调试。如果你需要存储其他类型替换data的类型即可。在真正的实战代码中data字段可能会是一个结构体、字符串甚至是一个用户自定义类型但遍历逻辑是完全一样的。2.2 栈结构的设计栈的结构有两种方案。一种是固定数组栈简单高效适合节点数量已知或可预估的情况。另一种是链式栈动态分配内存不受初始容量限制代码稍微复杂一点。我在实际操作中更推荐数组栈理由很简单性能好代码直观调试时也能直接看整个栈的内容。固定大小取一个足够大的值就行比如1000个节点。但如果你的二叉树可能非常大那就考虑链式栈避免栈溢出的问题。数组栈的定义如下#define MAX_SIZE 1000 typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; }这里有一个细节需要特别注意栈顶指针top的初始值。我习惯把top初始化为-1这样入栈时先加一再存数据出栈时先取数据再减一。数组下标从0开始存第一个元素逻辑上非常清晰。2.3 测试用二叉树为了验证代码我定义了这样一棵二叉树1 / \ 2 3 / \ \ 4 5 6中序遍历的结果应该是4 2 5 1 3 6。 后序遍历的结果应该是4 5 2 6 3 1。建树的核心代码大概是这样的BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; }后序遍历时3号节点的左孩子为空右孩子是6号节点。这种“一边为空另一边非空”的结构正好用来验证后序遍历的细节有没有写对。3. 中序非递归遍历的完整实现中序非递归遍历的思路相对好理解。说是“中序”规则就是先处理左子树再处理当前节点最后处理右子树。那么用栈模拟时核心思想就是“沿着左子树一直往下走一路把节点都压入栈中直到左子树为空然后弹出栈顶节点访问再转向右子树继续这个过程”。3.1 中序非递归遍历的代码中序非递归遍历的典型代码如下void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到头沿途节点全部入栈 while (p ! NULL) { push(s, p); p p-lchild; } // 此时p为空弹出栈顶元素并访问 if (!isEmpty(s)) { p pop(s); printf(%d , p-data); // 转向右子树 p p-rchild; } } printf(\n); }3.2 逐步拆解执行过程我拿上面定义好的二叉树来走一遍流程帮你直观感受代码的运行逻辑。第一次进入外层while循环时p指向根节点1。内层while循环开始节点1入栈p指向节点2节点2入栈p指向节点4节点4入栈p指向NULL。此时栈从底到顶依次是[1, 2, 4]。内层循环结束因为p为NULL。进入if语句弹出栈顶节点4打印4p转向节点4的右孩子也就是NULL。回到外层循环判断条件p为NULL但栈不为空条件成立继续循环。再次进入内层whilep为NULL直接跳过。弹出栈顶节点2打印2p转向节点2的右孩子也就是节点5。第三轮外层循环p指向节点5。内层while节点5入栈p指向节点5的左孩子NULL。弹出节点5打印5p指向NULL。第四轮外层循环p为NULL栈不为空。弹出栈顶节点1打印1p指向节点3。第五轮外层循环p指向节点3。内层while节点3入栈p指向节点3的左孩子NULL。弹出节点3打印3p指向节点3的右孩子6。第六轮外层循环p指向节点6。内层while节点6入栈p指向NULL。弹出节点6打印6p指向NULL。第七轮外层循环p为NULL栈为空循环结束。最终输出结果为4 2 5 1 3 6完全正确。3.3 中序非递归遍历的关键技巧与易错点中序非递归遍历的代码结构很清晰就是两层循环套一个if。但越是这种看起来简单的代码越容易在细节上出问题。第一个容易踩的坑是外层while条件。这里必须是p ! NULL || !isEmpty(s)两个条件缺一不可。如果写成while(p ! NULL)处理到一半就会死循环或者漏节点。如果写成while(!isEmpty(s))初始时p指向根节点而栈为空条件可能直接不成立。我见过不少朋友把这个边界条件搞错导致代码在某种输入下就是输出不对。第二个需要注意的点是访问节点和转向右子树的顺序。弹出节点后先printf打印然后p p-rchild。这个顺序不能反过来。如果先让p p-rchild那当前节点就没机会打印了遍历顺序就变了。第三个技巧是内层while循环“当前节点非空就入栈并走向左孩子”这个模式。这个模式其实是遍历算法里的核心理解透了这个后面的后序遍历会稍微轻松一点。如果把非递归遍历比作开车内层while就是在国道上一直往左开到底遇到路就走直到没路为止pop操作就是回到上一个路口看看有没有右转的机会。4. 后序非递归遍历两种实现方案后序非递归遍历的难度要比中序高一个档次。原因很简单后序遍历的顺序是左子树、右子树、根节点。这意味着根节点必须在左右子树都处理完之后才能打印。在栈里面根节点会被“经过”两次第一次是从左子树返回第二次是从右子树返回。只有第二次经过的时候才能打印根节点。问题来了我们怎么区分当前是从左子树返回还是从右子树返回解决办法有两个方向。一是用标记法在栈里额外记录每个节点的访问状态二是用两个栈用空间换逻辑的简洁性。4.1 标记法用辅助状态记录遍历阶段标记法的核心思路是栈里存的不仅仅是节点指针还多存一个状态字段表示当前正在处理这个节点的哪个阶段。0表示“左子树还没处理完刚入栈”1表示“左子树处理完了正在处理右子树”2表示“左右子树都处理完了可以打印”。我先定义栈元素结构体typedef struct { BiTNode *node; int tag; } StackElement;对应的栈定义和操作也稍作调整这里不再重复写核心变化就是data数组的类型从BiTNode *变成StackElement。后序标记法的核心遍历代码void postOrderWithTag(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到头把沿途节点标记为0入栈 while (p ! NULL) { StackElement elem; elem.node p; elem.tag 0; push(s, elem); p p-lchild; } // 查看栈顶元素 if (!isEmpty(s)) { StackElement *top (s.data[s.top]); // 如果从左子树返回标记为0则转向右子树标记改为1 if (top-tag 0) { top-tag 1; p top-node-rchild; } else { // tag为1说明左右子树都处理完了出栈并打印 printf(%d , top-node-data); pop(s); p NULL; } } } printf(\n); }这段代码的关键在于当tag为0时遇到栈顶节点不弹出只是把tag改为1然后尝试走入右子树。这样就保证了根节点在栈里多待了一轮。当右子树处理完之后回到这个节点时tag已经是1了这时才弹出打印。4.2 两个栈实现后序遍历相比标记法两个栈的实现思路更巧妙且代码更好写。我们先回忆一下后序的顺序是左、右、根。如果反过来看就是根、右、左。那根、右、左这个顺序恰恰是“先序变体”——先访问根再访问右子树最后访问左子树。所以我们有这样一个思路用第一个栈按照“根、右、左”的顺序遍历把访问到的节点全部压入第二个栈。最后把第二个栈里的内容从头弹出得到的就是“左、右、根”的正序后序遍历。void postOrderTwoStacks(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); // 注意压栈顺序先压左孩子再压右孩子 // 这样弹出的时候就先弹右孩子再弹左孩子 // 保证s1弹出的顺序是根、右、左 if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } // 现在从s2中依次弹出打印的顺序为左、右、根 while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); }这个方法代码逻辑上非常优雅不需要额外的状态标记也没有判断分支。缺点是空间上多用一个栈。我在实际写代码的时候也更倾向于这种方法因为逻辑好推理不容易写错。4.3 对比两种方案怎么选标记法是更通用的方案因为它可以扩展到任意需要知道节点被访问次数的场景里。两个栈的方法虽然简洁但本质上改变了思考问题的角度适用面要窄一些。从可读性角度来说两个栈实现的代码几乎不需要长篇注释一眼就能看懂在干什么。从内存效率来说标记法只用了一个栈但栈元素要多存一个int类型字段。两个栈可能需要用到二倍的内存控件虽然在大多数场景下根本不是问题。如果是在面试中遇到这道题我建议优先用两个栈的方法因为代码简洁、逻辑清晰、不容易出错。如果是自己学习或者要在嵌入式这种资源受限的环境里实现那标记法更合适。4.4 后序非递归遍历的执行过程拆解我用两个栈的方法手动走一遍上面那棵树的过程。初始状态s1里压入节点1s2为空。第一步从s1弹出节点1打印内容暂存入s2再将节点1的左孩子2和右孩子3依次压入s1。注意压入顺序是先左后右所以s1栈顶是3。第二步从s1弹出节点3压入s2。节点3的左孩子为空跳过右孩子6压入s1。此时s1栈顶是6。第三步弹出节点6压入s2。节点6没有孩子。第四步此时s1弹出节点2压入s2。节点2的左孩子4和右孩子5依次压入s1先左后右所以栈顶是5。第五步弹出节点5压入s2。第六步弹出节点4压入s2。此时s1为空。s2从栈底到栈顶依次是1、3、6、2、5、4。注意这里的顺序正好和正序后序相反所以依次弹出打印为4、5、2、6、3、1与理论结果完全一致。5. 常见问题与排查技巧实录非递归遍历代码看起来不长但真调试起来还是有不少容易卡住的点。我把自己踩过的坑和平时答疑时遇到的高频问题整理出来按问题现象和解决办法对照着写。5.1 输出结果完全不对或者死循环如果你发现输出完全不是自己预期的那样甚至连打印都没有大概率是外层while循环的条件写错了。检查一下是不是漏掉了p ! NULL这个条件或者把逻辑或写成了逻辑与。这种情况我在调试的时候一般会先在代码里加入调试输出在每次入栈、出栈时打印当前节点值和栈的变化情况。看到栈的变化过程问题基本一眼就能定位。5.2 后序遍历时某个节点提前打印了这种现象很典型。比如中序输出是对的后序却把根节点打印在中间而不是最后。问题基本出在标记法的tag状态没有正确流转。检查一下是不是在tag为0的时候就把节点弹出了正确的做法是tag为0的时候只改tag并转向右子树不能弹出节点。如果用两个栈的方法根节点不可能提前打印因为根节点一定是最后被打包进s2的所以它必然是s2的栈底最后一个弹出。5.3 栈满了怎么办如果设定的MAX_SIZE太小而树的节点数量超过了这个限制push的时候就会输出“栈已满无法入栈”。这种情况下有两种解决办法。一是把MAX_SIZE调大比如从1000改成100000简单粗暴。二是改成动态扩容的栈或者直接用链式栈。我个人在做算法题的时候倾向于直接把数组开大一点因为节点数量一般不会超过十万1e5的数组在现代编译器上毫无压力。5.4 树是空树时怎么办空树是一个非常容易忽略的边界条件。如果你的代码在root为NULL的时候直接崩了那肯定是忘了在最开头加判空逻辑。中序代码里root为NULL时p初始就为NULL同时栈为空外层while条件不成立直接结束不会崩。但两个栈的方法中一开始就把root压入s1所以必须要提前判空。if (root NULL) { return; }这段代码必须有。5.5 野指针问题C语言的经典难题野指针。在非递归遍历中野指针最容易出现在创建节点和释放节点的时候。创建节点时malloc之后一定要检查返回的指针是否为NULL。释放节点时一定要先把子节点处理完再释放当前节点否则会造成访问已释放内存的问题。BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; }另外malloc出来的节点一定要记得初始化lchild和rchild为NULL否则在判断孩子是否存在时会读到随机值导致程序行为诡异。5.6 二叉树退化成链表时的表现如果二叉树退化成了一条单链表比如每个节点都只有左孩子那非递归遍历的时间复杂度仍然是O(n)空间复杂度是O(n)。但如果是递归实现这个场景就非常容易爆栈。我实测过递归中序遍历一个10万层深的单链树基本上直接段错误。非递归版本用数组栈大概在1000万层以上才会碰到栈容量问题1000万以内的深度完全没压力。这也是为什么在一些极端数据结构下非递归遍历几乎是唯一选择。6. 一个通用的五步解题法学完中序和后序的非递归遍历我总结了一套通用的解题思路适配前序、中序、后序三种非递归遍历。这是一个方法论层面的总结希望帮你看清楚本质。第一步先把遍历顺序用文字写出来。前序是“根左右”中序是“左根右”后序是“左右根”。第二步想一想在这个顺序里哪些节点需要暂时存起来等后面再处理。一般来说只要某个子树的根节点不是优先打印它就需要放到栈里等待。中序和后序里根节点都不会被优先打印所以都需要压栈。第三步决定栈里需要额外存储什么信息。如果只存节点指针就够那是中序这种简单的场景。如果需要区分左右子树是否处理完就需要额外存tag标记或者用两个栈来规避。第四步写出“往左走到头、沿途入栈”的骨架代码。中序、后序的最外层逻辑基本一致变化的只是出栈之后打印的时机和转向右子树的方式。第五步根据不同的顺序调整打印时机。中序是弹出时打印后序是右子树处理完后打印。这套分析法对学习其他树的遍历也有帮助比如线索二叉树、N叉树遍历本质上还是在问什么时候打印什么时候转向需要什么额外的状态信息。7. 优化与扩展不只是写对还要写得好代码写对的下一步是写得好。有两个优化方向值得花时间琢磨。第一个优化方向是把内存分配降到最低。在嵌入式开发和系统编程里malloc和free都是有代价的频繁调用会造成内存碎片。如果树是预先构建好且大小已知的可以直接在栈区声明一个固定大小的节点指针数组完全避免动态分配。第二个优化方向是模板化。树节点的data类型不一定是int可能是char、字符串、自定义结构体。你可以把typedef改成泛型类型用void*指向数据然后用宏定义或者函数指针来实现通用容器。这种做法在大型项目里比较常见但纯C语言里会牺牲一些类型安全需要自己权衡。第三个扩展点是层级遍历。非递归遍历并不局限于栈用队列实现的层序遍历也是面试常客。层序遍历的顺序是一层一层从左到右用队列保存当前层的节点然后依次处理。理解了中序和后序的栈式遍历队列版层序遍历本质上是同一个思路——用数据结构来模拟“下一个该访问谁”的调度逻辑。我在处理实际问题的时候还有一个习惯用一个公共的打印函数或者统一的遍历接口把不同遍历方式的结果输出成同样的格式。调试的时候切换遍历方式快得多不用每个函数里都重写一遍打印逻辑。8. 完整代码汇总最后贴上完整代码直接用GCC编译就能跑。代码里我不再分段拆解保持一个完整的可直接运行的文件。#include stdio.h #include stdlib.h #define MAX_SIZE 1000 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; } BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; } void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { while (p ! NULL) { push(s, p); p p-lchild; } if (!isEmpty(s)) { p pop(s); printf(%d , p-data); p p-rchild; } } printf(\n); } void postOrder(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); } int main() { BiTree root createTree(); printf(中序遍历结果: ); inOrder(root); printf(后序遍历结果: ); postOrder(root); return 0; }这个版本的代码可以编译后直接运行。如果你在操作系统里跑注意把控制台编码调成UTF-8避免中文字符串乱码。9. 从遍历到更深层的理解掌握了中序和后序的非递归遍历你其实已经掌握了树这种数据结构里最核心的一类操作。树的遍历并不是孤立的它和递归、栈、队列、状态机这些知识点紧密相关。比如非递归遍历里“标记状态”的思想后续在学习图的深度优先和广度优先搜索时还会再次遇到。DFS的栈实现、BFS的队列实现本质上是同一套逻辑在不同的数据结构上的应用。如果你准备继续深挖建议在纸上多画几棵树手动模拟五次以上的遍历过程。很多人学不透遍历的原因不是代码难而是脑子里对“当前代码执行到哪一步、栈里存了哪些节点”没有一个直观的画面。把每一个入栈、出栈、转向的动作在纸上画出来一遍不够画三遍三遍不够画五遍画到能闭着眼睛说出每一步为止。这个过程很像学骑自行车理论说得再多不如真的蹬两圈。我个人的体会是非递归遍历不是一个可以靠死记硬背通过的题目它需要你在纸面上把节点状态的变化过程彻底过一遍。等你想通了“栈顶节点的tag说明什么”“什么时候该转向右子树”这两个问题后序遍历就不再是拦路虎。再顺手对比一下前序、中序、后序三种遍历在栈结构上的差别你会发现它们都是在回答同一个问题下一步该访问谁。 
长河君 · 2026/9/10 3:38:22 · 阅读 1.2k C语言实现二叉树中序后序非递归遍历，栈模拟与标记法详解
直接看标题就知道这题没少折腾人。作为数据结构课的经典算法实操二叉树的中序、后序非递归遍历用C语言实现几乎是每一个学计算机的人绕不过去的坎。递归版本三行代码写完但一到非递归很多朋友就卡住了特别是后序硬是想不明白那个“第二次经过节点”怎么判断。这篇文章我用C语言把这俩遍历给你彻底讲透。不绕弯子直接讲栈模拟的思路、节点状态标记以及我在调试过程中踩过的坑。适合正在学数据结构的本科生、准备考研或面试刷算法的人也适合那些学完就忘、想一次性看明白的朋友。1. 既然递归能解决为什么还要用非递归先回答一个问得最多的问题递归它不香吗中序递归十行代码后序递归也就十行为什么要费劲去手工模拟栈答案取决于应用场景。递归本质上是使用系统调用栈每次函数调用都会发生压栈、跳转、返回、弹栈这一整套动作而且栈帧里还要保存局部变量、参数和返回地址。当二叉树深度比较大的时候递归版本很容易把调用栈撑爆。我在实际开发里没少被这种问题坑过Linux线程默认栈大小只有8MB如果树退化成一个长链深度到十万、百万级递归基本就game over了。非递归遍历把“栈”从系统调用栈换成了程序员自己管理的数据结构内存分配可控不会出现不可预期的爆栈。更重要的是非递归的每个步骤都是显式的不像递归那样把逻辑藏在函数调用里。在某些对性能要求苛刻的场景比如嵌入式开发、实时系统里少一次函数调用少一层栈帧就是实打实的性能收益。再有就是面试和考试。非递归遍历是面试官非常喜欢考察的点因为它能直接检验你是否真正理解了遍历的本质而不只是会背递归模板。能不能用自己的话讲清楚中序和后序的入栈、出栈时机基本上决定了这道题能不能拿满分。理解非递归遍历的前提是搞清楚递归版本到底做了什么。中序递归的顺序是先往左走到底打印再往右走。后序递归的顺序是先往左走到底再往右走到底最后打印。我们非递归要做的事情就是用一个显式栈把递归版本的隐式逻辑给复刻出来。2. 准备工作栈结构、节点定义与辅助函数既然是C语言实现准备工作就得做得扎实。C语言没有现成的泛型栈容器不像C里面有std::stack可以直接用所以一切从零开始。2.1 二叉树节点的结构体定义二叉树的节点结构体定义没有什么争议常见的形式是这样的typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;这里我用的数据域是int类型方便测试和调试。如果你需要存储其他类型替换data的类型即可。在真正的实战代码中data字段可能会是一个结构体、字符串甚至是一个用户自定义类型但遍历逻辑是完全一样的。2.2 栈结构的设计栈的结构有两种方案。一种是固定数组栈简单高效适合节点数量已知或可预估的情况。另一种是链式栈动态分配内存不受初始容量限制代码稍微复杂一点。我在实际操作中更推荐数组栈理由很简单性能好代码直观调试时也能直接看整个栈的内容。固定大小取一个足够大的值就行比如1000个节点。但如果你的二叉树可能非常大那就考虑链式栈避免栈溢出的问题。数组栈的定义如下#define MAX_SIZE 1000 typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; }这里有一个细节需要特别注意栈顶指针top的初始值。我习惯把top初始化为-1这样入栈时先加一再存数据出栈时先取数据再减一。数组下标从0开始存第一个元素逻辑上非常清晰。2.3 测试用二叉树为了验证代码我定义了这样一棵二叉树1 / \ 2 3 / \ \ 4 5 6中序遍历的结果应该是4 2 5 1 3 6。 后序遍历的结果应该是4 5 2 6 3 1。建树的核心代码大概是这样的BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; }后序遍历时3号节点的左孩子为空右孩子是6号节点。这种“一边为空另一边非空”的结构正好用来验证后序遍历的细节有没有写对。3. 中序非递归遍历的完整实现中序非递归遍历的思路相对好理解。说是“中序”规则就是先处理左子树再处理当前节点最后处理右子树。那么用栈模拟时核心思想就是“沿着左子树一直往下走一路把节点都压入栈中直到左子树为空然后弹出栈顶节点访问再转向右子树继续这个过程”。3.1 中序非递归遍历的代码中序非递归遍历的典型代码如下void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到头沿途节点全部入栈 while (p ! NULL) { push(s, p); p p-lchild; } // 此时p为空弹出栈顶元素并访问 if (!isEmpty(s)) { p pop(s); printf(%d , p-data); // 转向右子树 p p-rchild; } } printf(\n); }3.2 逐步拆解执行过程我拿上面定义好的二叉树来走一遍流程帮你直观感受代码的运行逻辑。第一次进入外层while循环时p指向根节点1。内层while循环开始节点1入栈p指向节点2节点2入栈p指向节点4节点4入栈p指向NULL。此时栈从底到顶依次是[1, 2, 4]。内层循环结束因为p为NULL。进入if语句弹出栈顶节点4打印4p转向节点4的右孩子也就是NULL。回到外层循环判断条件p为NULL但栈不为空条件成立继续循环。再次进入内层whilep为NULL直接跳过。弹出栈顶节点2打印2p转向节点2的右孩子也就是节点5。第三轮外层循环p指向节点5。内层while节点5入栈p指向节点5的左孩子NULL。弹出节点5打印5p指向NULL。第四轮外层循环p为NULL栈不为空。弹出栈顶节点1打印1p指向节点3。第五轮外层循环p指向节点3。内层while节点3入栈p指向节点3的左孩子NULL。弹出节点3打印3p指向节点3的右孩子6。第六轮外层循环p指向节点6。内层while节点6入栈p指向NULL。弹出节点6打印6p指向NULL。第七轮外层循环p为NULL栈为空循环结束。最终输出结果为4 2 5 1 3 6完全正确。3.3 中序非递归遍历的关键技巧与易错点中序非递归遍历的代码结构很清晰就是两层循环套一个if。但越是这种看起来简单的代码越容易在细节上出问题。第一个容易踩的坑是外层while条件。这里必须是p ! NULL || !isEmpty(s)两个条件缺一不可。如果写成while(p ! NULL)处理到一半就会死循环或者漏节点。如果写成while(!isEmpty(s))初始时p指向根节点而栈为空条件可能直接不成立。我见过不少朋友把这个边界条件搞错导致代码在某种输入下就是输出不对。第二个需要注意的点是访问节点和转向右子树的顺序。弹出节点后先printf打印然后p p-rchild。这个顺序不能反过来。如果先让p p-rchild那当前节点就没机会打印了遍历顺序就变了。第三个技巧是内层while循环“当前节点非空就入栈并走向左孩子”这个模式。这个模式其实是遍历算法里的核心理解透了这个后面的后序遍历会稍微轻松一点。如果把非递归遍历比作开车内层while就是在国道上一直往左开到底遇到路就走直到没路为止pop操作就是回到上一个路口看看有没有右转的机会。4. 后序非递归遍历两种实现方案后序非递归遍历的难度要比中序高一个档次。原因很简单后序遍历的顺序是左子树、右子树、根节点。这意味着根节点必须在左右子树都处理完之后才能打印。在栈里面根节点会被“经过”两次第一次是从左子树返回第二次是从右子树返回。只有第二次经过的时候才能打印根节点。问题来了我们怎么区分当前是从左子树返回还是从右子树返回解决办法有两个方向。一是用标记法在栈里额外记录每个节点的访问状态二是用两个栈用空间换逻辑的简洁性。4.1 标记法用辅助状态记录遍历阶段标记法的核心思路是栈里存的不仅仅是节点指针还多存一个状态字段表示当前正在处理这个节点的哪个阶段。0表示“左子树还没处理完刚入栈”1表示“左子树处理完了正在处理右子树”2表示“左右子树都处理完了可以打印”。我先定义栈元素结构体typedef struct { BiTNode *node; int tag; } StackElement;对应的栈定义和操作也稍作调整这里不再重复写核心变化就是data数组的类型从BiTNode *变成StackElement。后序标记法的核心遍历代码void postOrderWithTag(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { // 一直向左走到头把沿途节点标记为0入栈 while (p ! NULL) { StackElement elem; elem.node p; elem.tag 0; push(s, elem); p p-lchild; } // 查看栈顶元素 if (!isEmpty(s)) { StackElement *top (s.data[s.top]); // 如果从左子树返回标记为0则转向右子树标记改为1 if (top-tag 0) { top-tag 1; p top-node-rchild; } else { // tag为1说明左右子树都处理完了出栈并打印 printf(%d , top-node-data); pop(s); p NULL; } } } printf(\n); }这段代码的关键在于当tag为0时遇到栈顶节点不弹出只是把tag改为1然后尝试走入右子树。这样就保证了根节点在栈里多待了一轮。当右子树处理完之后回到这个节点时tag已经是1了这时才弹出打印。4.2 两个栈实现后序遍历相比标记法两个栈的实现思路更巧妙且代码更好写。我们先回忆一下后序的顺序是左、右、根。如果反过来看就是根、右、左。那根、右、左这个顺序恰恰是“先序变体”——先访问根再访问右子树最后访问左子树。所以我们有这样一个思路用第一个栈按照“根、右、左”的顺序遍历把访问到的节点全部压入第二个栈。最后把第二个栈里的内容从头弹出得到的就是“左、右、根”的正序后序遍历。void postOrderTwoStacks(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); // 注意压栈顺序先压左孩子再压右孩子 // 这样弹出的时候就先弹右孩子再弹左孩子 // 保证s1弹出的顺序是根、右、左 if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } // 现在从s2中依次弹出打印的顺序为左、右、根 while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); }这个方法代码逻辑上非常优雅不需要额外的状态标记也没有判断分支。缺点是空间上多用一个栈。我在实际写代码的时候也更倾向于这种方法因为逻辑好推理不容易写错。4.3 对比两种方案怎么选标记法是更通用的方案因为它可以扩展到任意需要知道节点被访问次数的场景里。两个栈的方法虽然简洁但本质上改变了思考问题的角度适用面要窄一些。从可读性角度来说两个栈实现的代码几乎不需要长篇注释一眼就能看懂在干什么。从内存效率来说标记法只用了一个栈但栈元素要多存一个int类型字段。两个栈可能需要用到二倍的内存控件虽然在大多数场景下根本不是问题。如果是在面试中遇到这道题我建议优先用两个栈的方法因为代码简洁、逻辑清晰、不容易出错。如果是自己学习或者要在嵌入式这种资源受限的环境里实现那标记法更合适。4.4 后序非递归遍历的执行过程拆解我用两个栈的方法手动走一遍上面那棵树的过程。初始状态s1里压入节点1s2为空。第一步从s1弹出节点1打印内容暂存入s2再将节点1的左孩子2和右孩子3依次压入s1。注意压入顺序是先左后右所以s1栈顶是3。第二步从s1弹出节点3压入s2。节点3的左孩子为空跳过右孩子6压入s1。此时s1栈顶是6。第三步弹出节点6压入s2。节点6没有孩子。第四步此时s1弹出节点2压入s2。节点2的左孩子4和右孩子5依次压入s1先左后右所以栈顶是5。第五步弹出节点5压入s2。第六步弹出节点4压入s2。此时s1为空。s2从栈底到栈顶依次是1、3、6、2、5、4。注意这里的顺序正好和正序后序相反所以依次弹出打印为4、5、2、6、3、1与理论结果完全一致。5. 常见问题与排查技巧实录非递归遍历代码看起来不长但真调试起来还是有不少容易卡住的点。我把自己踩过的坑和平时答疑时遇到的高频问题整理出来按问题现象和解决办法对照着写。5.1 输出结果完全不对或者死循环如果你发现输出完全不是自己预期的那样甚至连打印都没有大概率是外层while循环的条件写错了。检查一下是不是漏掉了p ! NULL这个条件或者把逻辑或写成了逻辑与。这种情况我在调试的时候一般会先在代码里加入调试输出在每次入栈、出栈时打印当前节点值和栈的变化情况。看到栈的变化过程问题基本一眼就能定位。5.2 后序遍历时某个节点提前打印了这种现象很典型。比如中序输出是对的后序却把根节点打印在中间而不是最后。问题基本出在标记法的tag状态没有正确流转。检查一下是不是在tag为0的时候就把节点弹出了正确的做法是tag为0的时候只改tag并转向右子树不能弹出节点。如果用两个栈的方法根节点不可能提前打印因为根节点一定是最后被打包进s2的所以它必然是s2的栈底最后一个弹出。5.3 栈满了怎么办如果设定的MAX_SIZE太小而树的节点数量超过了这个限制push的时候就会输出“栈已满无法入栈”。这种情况下有两种解决办法。一是把MAX_SIZE调大比如从1000改成100000简单粗暴。二是改成动态扩容的栈或者直接用链式栈。我个人在做算法题的时候倾向于直接把数组开大一点因为节点数量一般不会超过十万1e5的数组在现代编译器上毫无压力。5.4 树是空树时怎么办空树是一个非常容易忽略的边界条件。如果你的代码在root为NULL的时候直接崩了那肯定是忘了在最开头加判空逻辑。中序代码里root为NULL时p初始就为NULL同时栈为空外层while条件不成立直接结束不会崩。但两个栈的方法中一开始就把root压入s1所以必须要提前判空。if (root NULL) { return; }这段代码必须有。5.5 野指针问题C语言的经典难题野指针。在非递归遍历中野指针最容易出现在创建节点和释放节点的时候。创建节点时malloc之后一定要检查返回的指针是否为NULL。释放节点时一定要先把子节点处理完再释放当前节点否则会造成访问已释放内存的问题。BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; }另外malloc出来的节点一定要记得初始化lchild和rchild为NULL否则在判断孩子是否存在时会读到随机值导致程序行为诡异。5.6 二叉树退化成链表时的表现如果二叉树退化成了一条单链表比如每个节点都只有左孩子那非递归遍历的时间复杂度仍然是O(n)空间复杂度是O(n)。但如果是递归实现这个场景就非常容易爆栈。我实测过递归中序遍历一个10万层深的单链树基本上直接段错误。非递归版本用数组栈大概在1000万层以上才会碰到栈容量问题1000万以内的深度完全没压力。这也是为什么在一些极端数据结构下非递归遍历几乎是唯一选择。6. 一个通用的五步解题法学完中序和后序的非递归遍历我总结了一套通用的解题思路适配前序、中序、后序三种非递归遍历。这是一个方法论层面的总结希望帮你看清楚本质。第一步先把遍历顺序用文字写出来。前序是“根左右”中序是“左根右”后序是“左右根”。第二步想一想在这个顺序里哪些节点需要暂时存起来等后面再处理。一般来说只要某个子树的根节点不是优先打印它就需要放到栈里等待。中序和后序里根节点都不会被优先打印所以都需要压栈。第三步决定栈里需要额外存储什么信息。如果只存节点指针就够那是中序这种简单的场景。如果需要区分左右子树是否处理完就需要额外存tag标记或者用两个栈来规避。第四步写出“往左走到头、沿途入栈”的骨架代码。中序、后序的最外层逻辑基本一致变化的只是出栈之后打印的时机和转向右子树的方式。第五步根据不同的顺序调整打印时机。中序是弹出时打印后序是右子树处理完后打印。这套分析法对学习其他树的遍历也有帮助比如线索二叉树、N叉树遍历本质上还是在问什么时候打印什么时候转向需要什么额外的状态信息。7. 优化与扩展不只是写对还要写得好代码写对的下一步是写得好。有两个优化方向值得花时间琢磨。第一个优化方向是把内存分配降到最低。在嵌入式开发和系统编程里malloc和free都是有代价的频繁调用会造成内存碎片。如果树是预先构建好且大小已知的可以直接在栈区声明一个固定大小的节点指针数组完全避免动态分配。第二个优化方向是模板化。树节点的data类型不一定是int可能是char、字符串、自定义结构体。你可以把typedef改成泛型类型用void*指向数据然后用宏定义或者函数指针来实现通用容器。这种做法在大型项目里比较常见但纯C语言里会牺牲一些类型安全需要自己权衡。第三个扩展点是层级遍历。非递归遍历并不局限于栈用队列实现的层序遍历也是面试常客。层序遍历的顺序是一层一层从左到右用队列保存当前层的节点然后依次处理。理解了中序和后序的栈式遍历队列版层序遍历本质上是同一个思路——用数据结构来模拟“下一个该访问谁”的调度逻辑。我在处理实际问题的时候还有一个习惯用一个公共的打印函数或者统一的遍历接口把不同遍历方式的结果输出成同样的格式。调试的时候切换遍历方式快得多不用每个函数里都重写一遍打印逻辑。8. 完整代码汇总最后贴上完整代码直接用GCC编译就能跑。代码里我不再分段拆解保持一个完整的可直接运行的文件。#include stdio.h #include stdlib.h #define MAX_SIZE 1000 typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTNode *data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } int isFull(Stack *s) { return s-top MAX_SIZE - 1; } void push(Stack *s, BiTNode *node) { if (isFull(s)) { printf(栈已满无法入栈\n); return; } s-data[(s-top)] node; } BiTNode *pop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[(s-top)--]; } BiTNode *getTop(Stack *s) { if (isEmpty(s)) { return NULL; } return s-data[s-top]; } BiTNode *createNode(int data) { BiTNode *node (BiTNode *)malloc(sizeof(BiTNode)); if (node NULL) { printf(内存分配失败\n); exit(1); } node-data data; node-lchild NULL; node-rchild NULL; return node; } BiTree createTree() { BiTNode *node1 createNode(1); BiTNode *node2 createNode(2); BiTNode *node3 createNode(3); BiTNode *node4 createNode(4); BiTNode *node5 createNode(5); BiTNode *node6 createNode(6); node1-lchild node2; node1-rchild node3; node2-lchild node4; node2-rchild node5; node3-rchild node6; return node1; } void inOrder(BiTree root) { Stack s; initStack(s); BiTNode *p root; while (p ! NULL || !isEmpty(s)) { while (p ! NULL) { push(s, p); p p-lchild; } if (!isEmpty(s)) { p pop(s); printf(%d , p-data); p p-rchild; } } printf(\n); } void postOrder(BiTree root) { if (root NULL) { return; } Stack s1, s2; initStack(s1); initStack(s2); push(s1, root); while (!isEmpty(s1)) { BiTNode *p pop(s1); push(s2, p); if (p-lchild ! NULL) { push(s1, p-lchild); } if (p-rchild ! NULL) { push(s1, p-rchild); } } while (!isEmpty(s2)) { BiTNode *p pop(s2); printf(%d , p-data); } printf(\n); } int main() { BiTree root createTree(); printf(中序遍历结果: ); inOrder(root); printf(后序遍历结果: ); postOrder(root); return 0; }这个版本的代码可以编译后直接运行。如果你在操作系统里跑注意把控制台编码调成UTF-8避免中文字符串乱码。9. 从遍历到更深层的理解掌握了中序和后序的非递归遍历你其实已经掌握了树这种数据结构里最核心的一类操作。树的遍历并不是孤立的它和递归、栈、队列、状态机这些知识点紧密相关。比如非递归遍历里“标记状态”的思想后续在学习图的深度优先和广度优先搜索时还会再次遇到。DFS的栈实现、BFS的队列实现本质上是同一套逻辑在不同的数据结构上的应用。如果你准备继续深挖建议在纸上多画几棵树手动模拟五次以上的遍历过程。很多人学不透遍历的原因不是代码难而是脑子里对“当前代码执行到哪一步、栈里存了哪些节点”没有一个直观的画面。把每一个入栈、出栈、转向的动作在纸上画出来一遍不够画三遍三遍不够画五遍画到能闭着眼睛说出每一步为止。这个过程很像学骑自行车理论说得再多不如真的蹬两圈。我个人的体会是非递归遍历不是一个可以靠死记硬背通过的题目它需要你在纸面上把节点状态的变化过程彻底过一遍。等你想通了“栈顶节点的tag说明什么”“什么时候该转向右子树”这两个问题后序遍历就不再是拦路虎。再顺手对比一下前序、中序、后序三种遍历在栈结构上的差别你会发现它们都是在回答同一个问题下一步该访问谁。