企业官网建设流程全解析

二叉树的非递归遍历是个老生常谈的话题，但能一次把中序和后序讲明白的并不多。很多同学递归版本背得滚瓜烂熟，一上手非递归就卡壳，尤其后序非递归能现场写对的人更是凤毛麟角。我当年在笔试里栽过一次后序，后来把几种主流写法都捋了一遍，才发现这东西压根不难，关键是得搞懂系统栈帮我们做了什么梦，非递归只是把这件事手动做了一遍。

这篇文章就用C语言把中序和后序的非递归遍历从头到尾拆开揉碎，包含完整可运行的代码、手推过程、方案对比和常见的坑。适合正在学数据结构、准备考研或面试算法题的同学参考，保证你看完能自己从零敲出来，而不是背模板。

1. 非递归遍历的核心思路：为什么必须折腾栈

1.1 递归遍历的本质是什么

先想一个最简单的问题：递归遍历二叉树的时候，信息到底存在哪里？

看这段最常见的递归代码：

void InOrder(BiTree T) { if (T == NULL) return; InOrder(T->lchild); // 先扎进左子树 printf("%d ", T->data); // 左子树回来才访问自己 InOrder(T->rchild); // 再进右子树 }

每一层递归调用，系统都会自动把“当前执行到哪一句、当前节点是谁”压进程序运行时的调用栈。比如上面这段代码，一个节点会经历“入栈挂起→从左边回来→访问自身→再从右边回来→出栈返回”完整的过程。换句话说，递归之所以写起来爽，是因为操作系统替你把状态存好了，你只需要关心逻辑本身。

非递归遍历的本质，就是手动开辟一个栈，自己去模拟这个“挂起和恢复”的过程。理论上任何递归程序都能改成非递归，但遍历二叉树这件事比较特殊——中序和后序的访问时机很拧巴，所以改起来比前序要费心思。前序是“来一个节点就访问，然后再往下钻”，顺着一个方向走就行；中序必须等到左子树彻底空了你才知道该访问谁；后序更麻烦，左右子树都得处理完，才轮到根节点。后序之所以最难，就是因为判断“左右子树是否都搞完了”这件事在非递归里需要额外的信息。

1.2 非递归遍历的通用套路

先把结论亮出来：二叉树的非递归遍历，无论是前中后序还是层序，本质上都逃不开两种控制流。

第一种叫“一路向左”：把当前节点入栈，然后不断把左孩子入栈，直到某个节点的左孩子为空。这个过程对应着递归版里“疯狂调用左子树”的那段逻辑。

第二种叫“转向右边”：当p指向空、栈里有货的时候，弹出栈顶节点，然后让p指向它右孩子，继续新一轮的“一路向左”。

中序和后序的代码骨架都是这两步的组合，区别只在于“访问节点的时机”和“如何确认右边已经处理完”。看懂这两点，下面的代码就不是背的，而是推出来的。

2. 中序非递归遍历：从“一路向左”到“出栈访问”

2.1 中序的算法过程与手推

先写出核心代码，再看它为什么成立。

void InOrderTraversal(BiTree T) { LinkStack S; InitStack(&S); BiTree p = T; while (p || !StackEmpty(S)) { if (p) { Push(&S, p); p = p->lchild; // 一路向左，先别访问 } else { Pop(&S, &p); printf("%d ", p->data); // 左子树走到底了，访问栈顶 p = p->rchild; // 转向右子树 } } printf("\n"); }

循环条件p || !StackEmpty(S)很关键。p是当前游标，S是栈。两者有一个非空就得继续，因为栈非空代表还有节点没访问完，p非空代表还有子树没钻到底。

为了验证逻辑，我构造一棵测试树：

1 / \ 2 3 / \ \ 4 5 6

中序遍历预期结果：4 2 5 1 3 6。

手推一遍：

• 初始：p = 1，栈空。
• p非空：1入栈，p指向2。
• p非空：2入栈，p指向4。
• p非空：4入栈，p指向NULL。
• p空：弹出4并访问，p指向4的右孩子（NULL）。
• p空：弹出2并访问，p指向5。
• p非空：5入栈，p指向NULL。
• p空：弹出5并访问，p指向5的右孩子（NULL）。
• p空：弹出1并访问，p指向3。
• p非空：3入栈，p指向NULL。
• p空：弹出3并访问，p指向6。
• p非空：6入栈，p指向NULL。
• p空：弹出6并访问，p指向NULL。
• 此时p为空且栈空，循环退出。

最后输出：4 2 5 1 3 6，和递归版完全一致。

2.2 中序非递归的代码细节

栈这里我推荐用链栈，而不是顺序栈。原因有两个：第一，链栈不会受预设容量限制，二叉树退化成链状（比如所有节点只有右孩子）时高度可能非常大，顺序栈开小了直接溢出；第二，链栈的Push/Pop操作天然适合存储指针类型，逻辑也不绕。

栈节点结构可以这样定义：

typedef struct StackNode { BiTree data; // 存的是二叉树节点指针 struct StackNode *next; } StackNode, *LinkStack;

中序遍历是三种遍历里相对最温柔的，它只有一个容易错的地方：在弹栈访问后，忘记把p指向右孩子，或者把p = p->rchild写成了p = p->lchild，然后程序就陷入死循环或者无限压栈。每次弹栈后一定要把p挪到右子树，这一步是整个中序算法的“涡轮增压器”，没有它程序就原地打转。

2.3 为什么这个写法不会漏节点

有人可能会问：中序的核心是“左根右”，代码里节点是先压栈、后访问，会不会某条路径绕晕了？

其实不会。每一个节点被压进栈时，它的左子树一定还没处理完（或者即将处理），而它被弹出的时机，恰好是它的左子树“彻底走完”的那一刻。此时访问它，就严格保证了“左子树里的所有节点都先于它被访问”。然后再让p指向右子树，右子树重新进入“一路向左”的流程，右子树里最左边的节点会紧接着被弹出来——这不就是递归版中序遍历的真实执行顺序吗？

这其实也是在暗示一个通用思路：你只要在某个节点“从左子树返回来”的这个时间点访问它，得到的就是中序。所有中序非递归写法，不管长得怎么不一样，都是围绕这个时间点做文章。

3. 后序非递归遍历：三种主流方案对比与实现

3.1 双栈法：最容易写对的后序方案

后序的访问顺序是左→右→根。把它倒过来看，就是根→右→左。如果我能先实现“根→右→左”的遍历，再把结果倒序输出，得到的不就是后序吗？

“根→右→左”其实就是前序遍历的一种变体——前序是“根→左→右”，只要把压栈顺序从“先右后左”改成“先左后右”，就能得到“根→右→左”。再借助第二个栈做倒序，后序就出来了。

代码非常干净：

void PostOrderTraversal_DoubleStack(BiTree T) { LinkStack S1, S2; InitStack(&S1); InitStack(&S2); if (T == NULL) return; Push(&S1, T); while (!StackEmpty(S1)) { BiTree p; Pop(&S1, &p); Push(&S2, p); // 先存进S2，最后弹出来就是后序 if (p->lchild) Push(&S1, p->lchild); // 注意先左后右 if (p->rchild) Push(&S1, p->rchild); } while (!StackEmpty(S2)) { BiTree p; Pop(&S2, &p); printf("%d ", p->data); } printf("\n"); }

用前面的测试树手推一次：

• S1初始：1。
• 弹出1入S2，S1先压左孩子2、再压右孩子3，栈顶是3。
• 弹出3入S2，压3的左孩子（空）、右孩子6，栈顶是6。
• 弹出6入S2，栈顶是2。
• 弹出2入S2，压4和5，栈顶是5。
• 弹出5入S2，栈顶是4。
• 弹出4入S2，S1空。
• S2从栈顶依次弹出：4 5 2 6 3 1。和预期后序完全一致。

双栈法的优点就是思路直白，几乎不可能写错，非常适合面试现场快速给出答案。缺点也很明显：用了两个栈，空间复杂度翻倍。如果二叉树高度为h，最坏情况下两个栈总共可能存大约2h个节点指针，虽然很多实际场景下无所谓，但你要是处理一棵特别深的树，还是有点浪费。

3.2 单栈 + 前驱指针法：工程上最常用的写法

如果要抠空间复杂度，就要回到“怎么在单个栈里判断右子树是否已访问过”这个问题上。

后序节点的访问顺序是左→右→根。当一个节点弹出栈准备访问时，它的左子树肯定已经搞完了，这是由“一路向左”的流程保证的。关键问题是右子树到底有没有搞完？如果没搞完，就得先压回去，转向右子树；如果搞完了，才能访问。

判断右子树是否搞完，最常用的办法是记一个“上一次访问的节点”lastVisited。当一个栈顶节点的右孩子等于lastVisited，或者右孩子为空时，说明右子树已经处理完（或者压根没右子树），这时候就可以放心访问当前节点了。

void PostOrderTraversal_LastVisit(BiTree T) { LinkStack S; InitStack(&S); BiTree p = T; BiTree lastVisited = NULL; while (p || !StackEmpty(S)) { if (p) { Push(&S, p); p = p->lchild; // 一路向左，先不访问 } else { GetTop(S, &p); // 只看栈顶，不弹出 if (p->rchild && p->rchild != lastVisited) { p = p->rchild; // 右子树没处理完，转向右 } else { Pop(&S, &p); printf("%d ", p->data); lastVisited = p; // 记录刚访问的节点 p = NULL; // 关键！防止再次把当前节点压栈 } } } printf("\n"); }

这段代码里最容易忽略的是else分支里p = NULL这一步。很多初学同学写到这里忘记置空，然后循环回到if(p)的时候又把当前节点压进栈一次，于是死循环。为什么要置空？因为当前节点已经访问完了，它的左右子树也都处理完了，不能再往左走，p必须为NULL才能进入下一个“出栈判断”分支。反过来，如果右子树还没处理完，p指向右孩子，让外层循环进入if(p)分支，继续对右子树做“一路向左”。

用测试树手推一遍前几个关键步骤：

• p = 1入栈，p = 2；2入栈，p = 4；4入栈，p = NULL。
• 栈顶4，右孩子NULL，满足条件：弹出4，访问4，lastVisited = 4，p = NULL。
• 栈顶2，右孩子5不为空且不等于lastVisited，p = 5，进入外层循环。
• 5入栈，p = NULL。栈顶5，右孩子NULL，弹出5，访问5，lastVisited = 5，p = NULL。
• 栈顶2，右孩子5等于lastVisited，满足条件，弹出2访问，lastVisited = 2，p = NULL。
• 栈顶1，右孩子3不为空且不等于lastVisited，p = 3。

后续同理，最终输出4 5 2 6 3 1。

这是一个非常优雅的解法，只用一个栈加一个指针变量，空间复杂度只有O(h)，而且不存在“改标记”的开销。推荐在工程代码和考研手写代码里用这一版。

3.3 单栈 + 计数标记法：另一种思路

除了前驱指针法，还有一类“标记法”也经常被提到。思路是这样的：每个节点入栈时不是只存一个指针，而是存{节点指针, 访问计数}。计数等于0说明节点刚入栈，还没处理右子树；等到计数变成1再弹出，说明右子树已经处理完，可以输出了。

大概长这样：

typedef struct { BiTree node; int count; // 0表示未处理右子树，1表示已处理右子树 } StackElem;

入栈时节点的count置为0。出栈时如果count为0，说明这个节点的左右子树还没处理完，就把count改成1再重新入栈，并把p指向其右孩子，继续循环；如果出栈时count已经是1，就访问节点。

这种写法在逻辑上比前驱指针法更“傻”一些，但是也更容易理解：你明确地用一个计数告诉程序“我处理到哪一步了”。代价是每个节点可能要入栈出栈两次，且栈里存的元素结构体比单纯指针大。

三种方案放在一起对比：

我个人建议：如果你只能记住一种后序非递归，那就记住前驱指针法。它和双栈法互相印证，理解一个就能推出另一个；而且“记录上次访问位置”这个技巧，将来在做其他树形问题的非递归实现时也经常能派上用场。

4. 完整可运行的Demo与测试验证

4.1 从0到1搭一个可运行的程序

光有核心函数还不够，得让代码跑起来才有说服力。这里我给出一个完整的C语言Demo，包括链栈的初始化、入栈、出栈、取栈顶，以及二叉树的节点创建。所有代码都在一个文件里，拿过去就能编译运行。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct StackNode { BiTree data; struct StackNode *next; } StackNode, *LinkStack; void InitStack(LinkStack *S) { *S = NULL; } bool Push(LinkStack *S, BiTree e) { LinkStack node = (LinkStack)malloc(sizeof(StackNode)); if (node == NULL) return false; node->data = e; node->next = *S; *S = node; return true; } bool Pop(LinkStack *S, BiTree *e) { if (*S == NULL) return false; LinkStack node = *S; *e = node->data; *S = node->next; free(node); return true; } bool GetTop(LinkStack S, BiTree *e) { if (S == NULL) return false; *e = S->data; return true; } bool StackEmpty(LinkStack S) { return S == NULL; } BiTree CreateNode(int val) { BiTree node = (BiTree)malloc(sizeof(BiTNode)); if (node == NULL) return NULL; node->data = val; node->lchild = NULL; node->rchild = NULL; return node; } BiTree CreateDemoTree() { BiTree root = CreateNode(1); root->lchild = CreateNode(2); root->rchild = CreateNode(3); root->lchild->lchild = CreateNode(4); root->lchild->rchild = CreateNode(5); root->rchild->rchild = CreateNode(6); return root; }

4.2 主函数与验证逻辑

测试主函数把三种遍历结果都打印出来，然后用递归版的结果做对照。

void InOrderTraversal(BiTree T) { LinkStack S; InitStack(&S); BiTree p = T; while (p || !StackEmpty(S)) { if (p) { Push(&S, p); p = p->lchild; } else { Pop(&S, &p); printf("%d ", p->data); p = p->rchild; } } printf("\n"); } void PostOrderTraversal_DoubleStack(BiTree T) { LinkStack S1, S2; InitStack(&S1); InitStack(&S2); if (T == NULL) return; Push(&S1, T); while (!StackEmpty(S1)) { BiTree p; Pop(&S1, &p); Push(&S2, p); if (p->lchild) Push(&S1, p->lchild); if (p->rchild) Push(&S1, p->rchild); } while (!StackEmpty(S2)) { BiTree p; Pop(&S2, &p); printf("%d ", p->data); } printf("\n"); } void PostOrderTraversal_LastVisit(BiTree T) { LinkStack S; InitStack(&S); BiTree p = T; BiTree lastVisited = NULL; while (p || !StackEmpty(S)) { if (p) { Push(&S, p); p = p->lchild; } else { GetTop(S, &p); if (p->rchild && p->rchild != lastVisited) { p = p->rchild; } else { Pop(&S, &p); printf("%d ", p->data); lastVisited = p; p = NULL; } } } printf("\n"); } void InOrderRecursive(BiTree T) { if (T == NULL) return; InOrderRecursive(T->lchild); printf("%d ", T->data); InOrderRecursive(T->rchild); } void PostOrderRecursive(BiTree T) { if (T == NULL) return; PostOrderRecursive(T->lchild); PostOrderRecursive(T->rchild); printf("%d ", T->data); } int main() { BiTree T = CreateDemoTree(); printf("中序递归: "); InOrderRecursive(T); printf("\n"); printf("中序非递归: "); InOrderTraversal(T); printf("\n"); printf("后序递归: "); PostOrderRecursive(T); printf("\n"); printf("后序非递归(双栈): "); PostOrderTraversal_DoubleStack(T); printf("\n"); printf("后序非递归(前驱指针): "); PostOrderTraversal_LastVisit(T); printf("\n"); return 0; }

预期输出：

中序递归: 4 2 5 1 3 6 中序非递归: 4 2 5 1 3 6 后序递归: 4 5 2 6 3 1 后序非递归(双栈): 4 5 2 6 3 1 后序非递归(前驱指针): 4 5 2 6 3 1

建议你不光看输出，还在关键函数里加几个printf观察“谁入栈、谁出栈、p指向谁”，这样对栈的状态变化会有更直观感受。我当年就是这么把非递归搞明白的——不是背代码，而是拿着笔在纸上画栈。

4.3 测试不同形态的二叉树

用一棵只有右子树的树来测后序，是检验前驱指针法是否写错的好方法。

BiTree CreateSkewedTree() { BiTree root = CreateNode(1); root->rchild = CreateNode(2); root->rchild->rchild = CreateNode(3); return root; }

后序预期：3 2 1。如果前驱指针法里漏了p == NULL，这种右斜树会直接死循环。把这段代码加进main里跑一下，能帮你排查出最容易犯的低级错误。

5. 常见问题与排查技巧实录

5.1 死循环的三大元凶

我见过不少人在非递归遍历上栽跟头，总结下来死循环基本集中在三个原因：

第一个是在中序的else分支里写完printf之后忘记p = p->rchild，p一直停留在当前节点，程序会在if(p)和else之间反复横跳，栈里元素越堆越多，最后栈溢出或者死循环。

第二个是前驱指针法的else分支里忘记p = NULL。这个错误特别隐蔽，因为表面上看代码逻辑没问题，但运行起来就是停不下来。

第三个是把后序的转向右子树条件写错，比如写成if (p->rchild)而不判断是否等于lastVisited，导致右子树明明已经访问完了，还会再次进入右子树，形成无限往返。

遇到死循环先别急着抠代码，先打印栈顶元素和当前p值，观察循环卡在哪一步。大多数情况下，看两三轮输出就能定位问题。

5.2 如何快速验证遍历结果是否正确

非递归写完了，怎么确认是对的？最快的办法是写一个递归版做对照，像我上面Demo那样。如果两者输出一致，基本可以认为逻辑正确。

如果没有递归版做对照，也可以用两个性质来检验：

• 中序序列里，任意一个节点的左子树元素必然全部出现在它左边，右子树元素必然全部出现在它右边。
• 后序序列里，根节点必然是最后一个元素。对于任意节点，它的左子树元素和右子树元素分别连在一起，且左子树元素在右子树元素之前。

拿测试树的输出4 5 2 6 3 1来说，根1在最后，节点2的左右子树4 5在它前面，节点3的右子树6也在3的前面，这符合后序的严格定义。

5.3 一个实战小技巧：把访问动作抽象出来

前面代码里，访问节点都是直接printf。实际工程里会有更复杂的需求，比如统计节点个数、计算树的深度、把节点值收集到数组里。如果只围绕printf写，后面改需求还得动核心遍历逻辑。

建议在写遍历的时候，把“访问节点”抽象成一个函数指针或者一个独立的visit(BiTree node)函数：

void visit(BiTree node, int *counter) { (*counter)++; printf("%d ", node->data); }

这样中序、后序的非递归函数就只关心“遍历顺序”，不关心“访问到底干什么”。这个思路和设计模式里的“回调”是一个道理，在后面做二叉树的深度计算、线索化、或者序列化时都非常好用。

5.4 面试笔试中的常见变形

二叉树非递归遍历在面试里最常出现的变形有两种。第一种是“按某种遍历顺序打印第k个节点”，这种情况下你只需要在visit里加一个计数器，遍历到第k个直接返回。第二种是“判断一棵树是不是二叉搜索树”，用中序非递归遍历，检查输出序列是否严格递增即可，这比递归写法要更直观，也更容易处理“左根右”的连续性判断。

有人还会把“非递归中序”和“线索二叉树”结合起来考。线索二叉树本质上就是利用空指针记录前驱和后继，让遍历更省空间。如果你已经理解了非递归遍历为什么需要栈，再去看线索二叉树的“目标头指针”设计，会顺畅很多，因为两者的共同点都是：想办法记住“下一步该访问谁”。

这些变形题考察的都不是背代码，而是对遍历过程中“栈状态何时变化”的理解。能把中序和后序非递归的栈变化过程在纸上画出来，这些题基本就是送分题。

我个人写代码的经验是：非递归遍历一定要手推一遍完整的栈变化，不要只靠脑子想。拿一个只有三五个节点的树，把每一步的栈内容、p指针、输出内容写下来，坚持推两三次，之后不管遇到什么树的非递归问题，都能靠这套“画栈”的方法稳当地解决。这也是我调试这类代码用得最多的办法，比盯着代码发呆高效得多。