二叉树的非递归遍历是个老生常谈的话题但能一次把中序和后序讲明白的并不多。很多同学递归版本背得滚瓜烂熟一上手非递归就卡壳尤其后序非递归能现场写对的人更是凤毛麟角。我当年在笔试里栽过一次后序后来把几种主流写法都捋了一遍才发现这东西压根不难关键是得搞懂系统栈帮我们做了什么梦非递归只是把这件事手动做了一遍。这篇文章就用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入S2S1先压左孩子2、再压右孩子3栈顶是3。弹出3入S2压3的左孩子空、右孩子6栈顶是6。弹出6入S2栈顶是2。弹出2入S2压4和5栈顶是5。弹出5入S2栈顶是4。弹出4入S2S1空。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 22入栈p 44入栈p NULL。栈顶4右孩子NULL满足条件弹出4访问4lastVisited 4p NULL。栈顶2右孩子5不为空且不等于lastVisitedp 5进入外层循环。5入栈p NULL。栈顶5右孩子NULL弹出5访问5lastVisited 5p NULL。栈顶2右孩子5等于lastVisited满足条件弹出2访问lastVisited 2p NULL。栈顶1右孩子3不为空且不等于lastVisitedp 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就访问节点。这种写法在逻辑上比前驱指针法更“傻”一些但是也更容易理解你明确地用一个计数告诉程序“我处理到哪一步了”。代价是每个节点可能要入栈出栈两次且栈里存的元素结构体比单纯指针大。三种方案放在一起对比方案辅助空间代码难度节点入栈次数适用场景双栈法2个栈最低每个节点一次面试快速实现、只要正确性前驱指针法1个栈 1个指针中等每个节点两次工程代码、考研真题计数标记法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-rchildp一直停留在当前节点程序会在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指针、输出内容写下来坚持推两三次之后不管遇到什么树的非递归问题都能靠这套“画栈”的方法稳当地解决。这也是我调试这类代码用得最多的办法比盯着代码发呆高效得多。
二叉树中序后序非递归遍历：从栈原理到C语言实现
二叉树的非递归遍历是个老生常谈的话题但能一次把中序和后序讲明白的并不多。很多同学递归版本背得滚瓜烂熟一上手非递归就卡壳尤其后序非递归能现场写对的人更是凤毛麟角。我当年在笔试里栽过一次后序后来把几种主流写法都捋了一遍才发现这东西压根不难关键是得搞懂系统栈帮我们做了什么梦非递归只是把这件事手动做了一遍。这篇文章就用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入S2S1先压左孩子2、再压右孩子3栈顶是3。弹出3入S2压3的左孩子空、右孩子6栈顶是6。弹出6入S2栈顶是2。弹出2入S2压4和5栈顶是5。弹出5入S2栈顶是4。弹出4入S2S1空。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 22入栈p 44入栈p NULL。栈顶4右孩子NULL满足条件弹出4访问4lastVisited 4p NULL。栈顶2右孩子5不为空且不等于lastVisitedp 5进入外层循环。5入栈p NULL。栈顶5右孩子NULL弹出5访问5lastVisited 5p NULL。栈顶2右孩子5等于lastVisited满足条件弹出2访问lastVisited 2p NULL。栈顶1右孩子3不为空且不等于lastVisitedp 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就访问节点。这种写法在逻辑上比前驱指针法更“傻”一些但是也更容易理解你明确地用一个计数告诉程序“我处理到哪一步了”。代价是每个节点可能要入栈出栈两次且栈里存的元素结构体比单纯指针大。三种方案放在一起对比方案辅助空间代码难度节点入栈次数适用场景双栈法2个栈最低每个节点一次面试快速实现、只要正确性前驱指针法1个栈 1个指针中等每个节点两次工程代码、考研真题计数标记法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-rchildp一直停留在当前节点程序会在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指针、输出内容写下来坚持推两三次之后不管遇到什么树的非递归问题都能靠这套“画栈”的方法稳当地解决。这也是我调试这类代码用得最多的办法比盯着代码发呆高效得多。
