深入解析：三种二叉树非递归遍历方法及其代码实现
温馨提示：
本文最后更新于 2025年07月20日，已超过 5 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。
📖 引言
在数据结构与算法的学习中，二叉树遍历是基础中的基础。尽管递归实现简洁易懂，但在面试和工程中，非递归（迭代）遍历往往更受青睐。本篇文章面向学生初学者，深入解析三种二叉树非递归遍历（前序、中序、后序），附上最新权威资料与代码示例，帮助你从原理到实战彻底掌握！
前序遍历（Pre‑Order）
原理概述
前序遍历的访问顺序是：根 → 左 → 右。
在非递归实现中，我们利用栈（LIFO）模拟递归时的“系统调用栈”。
- 将根节点入栈
- 弹出栈顶节点
cur，处理它（打印或其它操作） - 若
cur.right存在，则先压入栈 - 若
cur.left存在，则再压入栈 - 重复步骤 2–4 直至栈空 :contentReference[oaicite:0]{index=0}
public static void preOrderUnRecur(Node head) {
if (head == null) return;
Stack<Node> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
Node cur = stack.pop(); // 弹出并处理
System.out.print(cur.value + " ");
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
}
}
`
中序遍历（In‑Order）
原理概述
中序遍历的访问顺序是：左 → 根 → 右。
迭代实现思路：
- 从根节点出发，不断将左子节点入栈，直至遇到
null - 弹出栈顶节点
cur，处理它 - 若
cur.right存在，则转向其右子树，重复步骤 1 - 直至栈空且当前节点为
null(维基百科)
public static void inOrderUnRecur(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
System.out.print(cur.value + " ");
cur = cur.right;
}
}
}
后序遍历（Post‑Order）
原理概述
后序遍历的访问顺序是：左 → 右 → 根。
一种常用迭代方法是借助两个栈：
- 将根节点推入“遍历栈” S1
- 从 S1 弹出节点
cur，推入“收集栈” S2 - 若
cur.left存在，推入 S1；若cur.right存在，也推入 S1 - 重复步骤 2–3 直至 S1 为空
- 最后依次从 S2 弹出，即为后序遍历顺序 (CSDN)
public static void posOrderUnRecur(Node head) {
if (head == null) return;
Stack<Node> s1 = new Stack<>(), s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()) {
Node cur = s1.pop();
s2.push(cur);
if (cur.left != null) s1.push(cur.left);
if (cur.right != null) s1.push(cur.right);
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
参考链接
- CSDN 原文（详尽图解与 Java 代码）
https://blog.csdn.net/zzzzzhxxx/article/details/133669283 (CSDN) - 维基百科 “树的遍历” 条目
https://zh.wikipedia.org/wiki/树的遍历 (维基百科)
正文到此结束
- 本文标签： 非递归遍历二叉树 先序遍历 中序遍历
- 本文链接： https://code.itptg.com/article/75
- 版权声明： 本文由老魏原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
