数据结构与算法 / 系统课时
二叉树遍历
二叉树遍历
二叉树遍历解决的是“按照什么顺序访问每个节点”的问题。本课将用同一棵树对比前序、中序、后序和层序遍历,并分别实现递归与迭代版本,使你能够根据任务需要选择合适的访问顺序。
学习目标
- 准确判断四种遍历的节点访问顺序。
- 理解递归调用栈与显式栈、队列之间的对应关系。
- 使用 Java 编写并验证完整的二叉树遍历程序。
深度优先与广度优先的关系
二叉树遍历
├── 深度优先遍历
│ ├── 前序:根 → 左 → 右
│ ├── 中序:左 → 根 → 右
│ └── 后序:左 → 右 → 根
└── 广度优先遍历
└── 层序:按层从左到右
为目录任务选择访问顺序
遍历是多数树算法的基础。复制目录结构常用前序遍历,因为要先处理父节点;计算目录占用空间常用后序遍历,因为要先汇总子节点;二叉搜索树按中序遍历会得到有序序列;按层打印树、计算最短层数或执行广度优先搜索则需要层序遍历。
四种遍历都会访问每个节点一次,差异不在“是否访问”,而在“何时处理根节点”以及使用什么辅助结构。理解这一点后,递归和迭代实现就不再是互不相关的代码模板。
什么时候访问根节点
以前序、中序和后序为代表的深度优先遍历,会沿一条分支尽量向下,再回退处理其他分支。递归版本由 JVM 调用栈保存返回位置;迭代版本则显式使用 Deque<Node> 保存尚未处理的节点。
| 遍历方式 | 访问顺序 | 典型用途 | 额外空间 |
|---|---|---|---|
| 前序 | 根、左、右 | 复制树结构、序列化 | |
| 中序 | 左、根、右 | 输出二叉搜索树有序结果 | |
| 后序 | 左、右、根 | 删除树、汇总子树结果 | 递归 ,下方两栈实现 |
| 层序 | 从上到下、每层从左到右 | 最短层数、按层处理 |
其中, 是树高, 是树的最大宽度。非空树的访问时间为 Θ(n)。表中辅助空间不含保存全部节点的返回列表,返回列表另需 Θ(n)。按边数计高度时,n 节点单链树的高度为 n−1,深度优先逻辑栈为 O(h+1)。层序队列可同时含当前层剩余节点和下一层已入队节点,峰值不超过 2w,且处理完上一层时会出现一整层,因此为 Θ(w)。
调用栈如何映射到容器
递归遍历的关键是把“处理根节点”的语句放在不同位置:前序放在递归左子树之前,中序放在左右子树之间,后序放在递归右子树之后。
迭代前序需要先压入右孩子、再压入左孩子,因为栈是后进先出;迭代中序要持续压入左链,栈顶节点弹出后再转向其右子树;迭代后序可以使用两个栈,第一栈产生“根、右、左”顺序,再由第二栈反转成“左、右、根”;层序遍历使用队列,节点出队时将左右孩子依次入队。
空树返回空结果。示例要求输入为有效二叉树,每个非根节点只由一处孩子引用到达,且无环。遍历期间应保持结构不变。
Java 对照实现
将以下代码保存为 BinaryTreeTraversalDemo.java。程序对同一棵树执行递归前序、中序、后序,以及对应的迭代实现和层序遍历。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class BinaryTreeTraversalDemo {
static class Node {
final int value;
Node left;
Node right;
Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
Node root = buildTree();
System.out.println("递归前序: " + preorderRecursive(root));
System.out.println("迭代前序: " + preorderIterative(root));
System.out.println("递归中序: " + inorderRecursive(root));
System.out.println("迭代中序: " + inorderIterative(root));
System.out.println("递归后序: " + postorderRecursive(root));
System.out.println("迭代后序: " + postorderIterative(root));
System.out.println("层序遍历: " + levelOrder(root));
}
private static Node buildTree() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
return root;
}
static List<Integer> preorderRecursive(Node root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private static void preorder(Node node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.value);
preorder(node.left, result);
preorder(node.right, result);
}
static List<Integer> inorderRecursive(Node root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private static void inorder(Node node, List<Integer> result) {
if (node == null) {
return;
}
inorder(node.left, result);
result.add(node.value);
inorder(node.right, result);
}
static List<Integer> postorderRecursive(Node root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private static void postorder(Node node, List<Integer> result) {
if (node == null) {
return;
}
postorder(node.left, result);
postorder(node.right, result);
result.add(node.value);
}
static List<Integer> preorderIterative(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.value);
// 先压右孩子,保证左孩子先出栈。
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
static List<Integer> inorderIterative(Node root) {
List<Integer> result = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.value);
current = current.right;
}
return result;
}
static List<Integer> postorderIterative(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<Node> first = new ArrayDeque<>();
Deque<Node> second = new ArrayDeque<>();
first.push(root);
while (!first.isEmpty()) {
Node node = first.pop();
second.push(node);
// 第二个栈反转访问顺序,最终得到左、右、根。
if (node.left != null) {
first.push(node.left);
}
if (node.right != null) {
first.push(node.right);
}
}
while (!second.isEmpty()) {
result.add(second.pop().value);
}
return result;
}
static List<Integer> levelOrder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
result.add(node.value);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return result;
}
}运行命令:
javac -encoding UTF-8 BinaryTreeTraversalDemo.java
java BinaryTreeTraversalDemo比较递归和迭代的输出
递归前序: [1, 2, 4, 5, 3, 6]
迭代前序: [1, 2, 4, 5, 3, 6]
递归中序: [4, 2, 5, 1, 3, 6]
迭代中序: [4, 2, 5, 1, 3, 6]
递归后序: [4, 5, 2, 6, 3, 1]
迭代后序: [4, 5, 2, 6, 3, 1]
层序遍历: [1, 2, 3, 4, 5, 6]递归与迭代版本输出一致,说明两种实现遵守了相同的访问规则。实际执行环境中的 Java 版本提示可能不同,但上述程序输出内容和顺序不变。
两栈后序的空间代价
两栈实现的第二个栈会收集整棵树的节点,即使树高很小,栈仍可能保存 n 个节点。因此该实现的额外空间为 O(n),不含返回列表。递归后序沿当前根到叶路径展开,递归调用栈的空间才是 O(h)。
- 使用
ArrayDeque实现显式栈与队列。空节点应在入栈和入队前过滤。 - 调试遍历顺序时,先画出 5~7 个节点的小树,并在每次处理节点时记录结果列表。
- 深树可用迭代实现避免递归栈溢出。若结构来自不可信输入,仍需单独检查环、共享节点与资源上限,换成显式栈不会消除这些问题。
- 只需要消费节点而不需要保存全部结果时,可以把
result.add(...)替换为业务处理函数,降低额外内存占用。
识别漏访和顺序错误
前序迭代中若先压左孩子再压右孩子,右孩子会先出栈,结果将变成“根、右、左”。修复方法是牢记栈的后进先出特性,按“右后处理、先压入;左先处理、后压入”的顺序操作。
中序迭代常见问题是只判断 current != null,当左链走到末尾后循环会提前结束。正确条件是 current != null || !stack.isEmpty(),这样才能继续弹出祖先节点并访问右子树。
层序遍历若用栈代替队列,会退化成深度优先访问。应使用 offer 入队、poll 出队,并保持左孩子先于右孩子入队。
用空树、链形树和非对称树验证
- 修改示例,使层序遍历按二维列表返回每一层,例如
[[1], [2, 3], [4, 5, 6]]。验收条件是层数、每层节点数量和从左到右顺序都正确。 - 使用单个栈实现后序遍历,不得使用第二个栈。可以增加
lastVisited指针,验收条件是输出仍为[4, 5, 2, 6, 3, 1]。 - 为四种遍历补充空树和只有一个节点的测试。验收条件是空树返回空列表,单节点树四种结果都只包含该节点。
按访问时机复核遍历
- 深度优先遍历的差异取决于根节点在左、右子树处理过程中的位置。
- 递归调用栈可以被显式栈替代,层序遍历则依赖先进先出的队列。
- 四种遍历时间均为 Θ(n)。空间要分开记输出与工作容器,两栈后序单独占线性空间。
从遍历过渡到搜索
下一课将学习“二叉搜索树查找”,利用左子树较小、右子树较大的有序不变式,把遍历范围从整棵树缩小到一条搜索路径。