直接看标题就知道，这题没少折腾人。作为数据结构课的经典算法实操，二叉树的中序、后序非递归遍历用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，打印4，p转向节点4的右孩子，也就是NULL。回到外层循环判断条件：p为NULL，但栈不为空，条件成立，继续循环。
再次进入内层while，p为NULL，直接跳过。弹出栈顶节点2，打印2，p转向节点2的右孩子，也就是节点5。
第三轮外层循环：p指向节点5。内层while：节点5入栈，p指向节点5的左孩子NULL。弹出节点5，打印5，p指向NULL。
第四轮外层循环：p为NULL，栈不为空。弹出栈顶节点1，打印1，p指向节点3。
第五轮外层循环：p指向节点3。内层while：节点3入栈，p指向节点3的左孩子NULL。弹出节点3，打印3，p指向节点3的右孩子6。
第六轮外层循环：p指向节点6。内层while：节点6入栈，p指向NULL。弹出节点6，打印6，p指向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里压入节点1，s2为空。
第一步，从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说明什么”“什么时候该转向右子树”这两个问题，后序遍历就不再是拦路虎。再顺手对比一下前序、中序、后序三种遍历在栈结构上的差别，你会发现它们都是在回答同一个问题：下一步该访问谁。
