外观
13 - 二叉树遍历:从组织架构到表达式执行
前置阅读:11 - 递归、调用栈与问题缩减、05 - 栈与队列的解题模型。
后续阅读:14 - 二叉搜索树与有序索引。图结构中的重复访问与环见17 - 图的 DFS 与 BFS。
摘要
读取层级结构时,有时需要先处理父节点,有时必须等子节点计算完,有时则要按层输出。遍历顺序取决于这些依赖关系。
本文先解释二叉树的节点模型,再给出深度优先和层序遍历的递归、队列实现,最后讨论显式栈、序列化和边界验证。前序、中序和后序描述的是:在左右子树之前、中间还是之后处理当前节点。
1. 深度优先遍历
二叉树中,每个节点最多有两个子节点,分别称为左子节点和右子节点。最上面的节点是根节点;没有子节点的节点是叶子节点;以某个节点为根、包含它及其所有后代的部分叫作子树。左右位置是结构的一部分,只有左孩子和只有右孩子是不同的树。
下面的 Node 保存一个整数值,以及左右子节点的引用;null 表示该位置没有节点。本文假设输入是有限的树:没有环,也没有被多个父节点共享的子节点,遍历期间结构不变。组织架构和目录可以用树表示,但一个父节点可能有多个孩子,不能直接套用这里的二叉节点模型。
java
static class Node {
int value;
Node left;
Node right;
}java
static void preorder(Node node) {
if (node == null) return;
visit(node); // 前序:先处理当前节点
preorder(node.left);
preorder(node.right);
}以上是需放入 Java 类中的局部片段;visit(node) 表示调用方定义的处理动作,例如输出节点值,它的实现未在片段中提供。
**深度优先遍历(DFS)**先沿一个分支向下处理,完成后再返回处理其他分支。递归能够这样组织遍历,是因为左右子树本身仍是树,可以调用同一个方法处理。遇到 null 返回,是递归的终止条件。
每次调用都依次处理左子树和右子树,改变当前节点的处理位置,就得到三种顺序:
| 顺序 | 处理顺序 | 适用场景与原因 |
|---|---|---|
| 前序 | 当前节点、左子树、右子树 | 复制结构或序列化时先记录父节点,再处理孩子;恢复结构还需要第 6 节的信息 |
| 中序 | 左子树、当前节点、右子树 | 二叉搜索树(BST)要求左侧键更小、右侧键更大,因此中序可得到有序序列;普通二叉树没有这一保证 |
| 后序 | 左子树、右子树、当前节点 | 父节点依赖子树结果时,先完成子问题,例如汇总目录大小或计算表达式树的运算结果 |
表达式树用内部节点表示运算符、叶子表示操作数。计算一个二元运算前,必须先得到左右操作数,所以适合后序处理。目录大小也遵循先汇总孩子、再计算父节点的依赖关系,但目录通常是多叉树,需要遍历所有孩子。
2. 层序遍历
**广度优先遍历(BFS)**先处理离根较近的节点,再处理更远的节点。在树上按层进行 BFS,就是层序遍历:根为第一层,它的孩子为第二层,以此类推。
队列按先进先出的顺序取出节点。处理一个节点时把孩子放到队尾,当前层剩余节点就会先于下一层节点被取出。下面仍是局部方法,使用第 1 节的 Node;其中 var 是 Java 10 起支持的局部变量类型推断语法。
java
static java.util.List<java.util.List<Integer>> levels(Node root) {
var result = new java.util.ArrayList<java.util.List<Integer>>();
if (root == null) return result;
var queue = new java.util.ArrayDeque<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
var level = new java.util.ArrayList<Integer>(size);
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.value);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}每轮外层循环开始时,队列里只有当前层的节点。先把数量保存为 size,内层循环只取出这批节点;期间加入的孩子留给下一轮。若把循环边界写成每次重新读取 queue.size(),队列长度会随出队、入队而变化,可能混入下一层,也可能提前结束当前层。
空树返回空列表。只把非空孩子入队,也避免了向不允许存放 null 的 ArrayDeque 添加空引用。
3. 后序计算树高
java
static int height(Node node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}这里按根到最深叶子路径上的节点数定义树高:空树为 0,叶子为 1。另一些资料按边数定义高度,比较结果前要先统一约定。此局部方法使用第 1 节的 Node。
当前节点的高度是较高子树的高度加 1。左右递归调用都返回后,才能计算 Math.max 并得到父节点答案,因此这是后序计算;不需要先把后序序列保存到列表中。
4. 完整可运行示例:前中后序与层序
下面的完整类对应文件名 TreeTraversalDemo.java,包含 main 入口。N 是第 1 节节点模型的简写:v 为值,l、r 为左右孩子。三个 DFS 方法把访问结果追加到非空列表 o,调用方若想独立收集下一次结果,需要清空列表或传入新列表。
java
import java.util.*;
/**
* 可运行示例:二叉树遍历:从组织架构到表达式执行。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TreeTraversalDemo {
static class N {
int v;
N l, r;
N(int v) {
this.v = v;
}
}
static void pre(N n, List<Integer> o) {
if (n == null) return;
// 前序在进入节点时处理,适合复制或序列化结构。
o.add(n.v);
pre(n.l, o);
pre(n.r, o);
}
static void in(N n, List<Integer> o) {
if (n == null) return;
in(n.l, o);
// 中序在左右子树之间处理;BST 的中序结果有序。
o.add(n.v);
in(n.r, o);
}
static void post(N n, List<Integer> o) {
if (n == null) return;
post(n.l, o);
post(n.r, o);
// 后序先得到两个子问题答案,再处理父节点。
o.add(n.v);
}
static List<List<Integer>> level(N root) {
List<List<Integer>> out = new ArrayList<>();
if (root == null) return out;
Deque<N> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> row = new ArrayList<>();
// 当前队列长度就是本层宽度,必须在加入下一层前固定。
for (int n = q.size(); n > 0; n--) {
N x = q.poll();
row.add(x.v);
if (x.l != null) q.offer(x.l);
if (x.r != null) q.offer(x.r);
}
out.add(row);
}
return out;
}
// 运行入口:演示根为 2、左右孩子分别为 1 和 3 的树。
public static void main(String[] args) {
N r = new N(2);
r.l = new N(1);
r.r = new N(3);
List<Integer> o = new ArrayList<>();
pre(r, o);
System.out.println(o);
o.clear();
in(r, o);
System.out.println(o);
o.clear();
post(r, o);
System.out.println(o);
System.out.println(level(r));
}
}同一棵树的四种视角
对根 2、左子 1、右子 3,按代码手工推演,四行预期输出依次为:
text
[2, 1, 3]
[1, 2, 3]
[1, 3, 2]
[[2], [1, 3]]前序先输出 2;中序在左子树结束后输出 2;后序等两个子树都结束才输出 2。层序则把 2 单独放在第一层,1 和 3 放在第二层。以上是预期输出,不是运行记录。
设节点数为 n、树高为 h、最大一层的节点数为 w。在输入满足树模型、每个节点的处理耗时为常数时,这些遍历各访问每个节点一次,时间为 O(n);这里的 O 表示随规模增长的上界量级,忽略常数倍。
递归 DFS 同时保留的是一条根到当前节点的调用路径,辅助空间为 O(h)。BFS 队列可能同时含有当前层剩余节点和下一层已入队节点,但规模仍为 O(w)。这两项都不包括保存结果的空间;完整示例的遍历结果还需要 O(n) 空间。第 3 节的树高计算不保存结果列表。
main 只演示三节点树,没有覆盖边界输入。建议另测空树、单节点、只有左或右子树、完全二叉树(除最后一层外各层填满,最后一层从左向右填充)和退化成单链的树。
5. 递归与迭代
递归由运行时调用栈保存“返回后继续做什么”。树退化成单链时,高度随节点数增长,嵌套调用过深可能导致栈溢出。显式栈则把待处理节点及进度放进程序控制的数据结构,适合深度不可控或需要暂停恢复的遍历,但仍需要保存状态,也不能消除内存限制。
以前序为例:先把根入栈,每次出栈后处理节点,再依次压入右孩子和左孩子。因为栈后进先出,左孩子会先被处理。中序则先沿左侧入栈,走到空位置后出栈处理节点,再进入其右子树。
后序要等两个孩子都处理完,不能在首次出栈时立即处理父节点。常见办法包括保存“节点 + 访问阶段”、使用双栈,或记录上一次访问节点。访问阶段表示当前节点的左右子树处理到了哪一步;显式状态机就是把这些进度变成可读写的数据。不同办法的空间成本也不同,双栈方案可能保存 O(n) 个节点,不能一概套用递归 DFS 的 O(h) 空间结论。
若要暂停、限速、分页或跨请求恢复,显式状态通常更容易保存。但跨请求保存时还需稳定的节点标识,并约定树发生变化后如何恢复;保存一组内存引用并不等于完成了持久化。本文只说明迭代思路,未提供迭代实现。
6. 序列化不是只输出遍历结果
序列化是把树转成可保存或传输的数据,反序列化是从这些数据恢复树。遍历的节点值只描述访问顺序,不一定描述结构。例如前序 [1, 2] 既可能来自根 1、左孩子 2,也可能来自根 1、右孩子 2。
要唯一恢复任意二叉树,必须补充结构信息。一种方式是在前序中保存空节点标记:上面两棵树分别为 [1, 2, #, #, #] 和 [1, #, 2, #, #],其中 # 表示空位置,协议必须区分它与合法节点值。另一种方式是组合前序与中序等信息;按键(Key)匹配节点时,要明确键是否唯一,重复值会影响恢复的唯一性。
BST 可利用左小右大的有序不变量减少部分信息,但仍需约定重复 Key 的处理策略,编码与解码双方必须一致。
工程中的树序列化还应定义版本、深度上限、恶意输入和反序列化资源限制,避免一份极深数据触发栈溢出或内存膨胀。
7. 验证与排障
- 对随机小树做差分测试,即比较递归与迭代实现的结果,检查节点顺序是否一致。
- 检查每个节点是否恰好访问一次。值可能重复,应按节点身份核对,不能只比较不同值的数量。
- 使用退化单链树检查深度风险,记录输入规模和运行环境;不要把某次溢出深度当成通用上限。
- BFS 内存异常时记录最大层宽和队列峰值,而不只记录节点总数。
- 若输入可能共享节点或成环,就要按图处理,并用访问集合
visited记录已访问节点;是否按节点身份还是业务键去重,需要符合输入语义。
本节列出验证方法,未表示这些测试已经执行。图中可能存在多条路径和环,重复访问控制见文末的图遍历文章。
8. 容易踩的坑
- 把循环中不断变化的
queue.size()当成本层固定宽度,破坏分层边界。 - 向
ArrayDeque加入null,而不是跳过空孩子。 - 把普通二叉树的中序结果也当成有序结果,忽略 BST 的条件。
- 将有共享节点或环的图当成树,既可能重复处理,也可能无法终止。
- 只关注遍历辅助空间,忽略结果列表和节点处理动作本身的成本。
9. 总结
先判断父节点是否依赖子树结果,再决定处理时机;需要逐层推进时使用 BFS。
- 前中后序描述当前节点的处理时机。
- BFS 适合寻找最浅层目标和保留层级;在无权图中,配合重复访问控制,可求按边数计算的最短距离。
- 深度不可控时考虑显式栈,同时评估状态和结果所需内存;恢复树结构时还要保存足够的序列化信息。
下一篇:二叉搜索树与有序索引。若节点可能被重复到达,转到图的 DFS 与 BFS。