10.2 树的遍历与表达式树

第 10.1 节描述了树的形状。算法经常需要处理每个顶点，例如列出文件夹、打印组织架构、计算公式或序列化数据。但“访问每个顶点”还不是完整指令，因为同一棵树可以产生许多访问顺序。

遍历是一条按照规定顺序恰好访问每个顶点一次的规则。本节将建立三种深度优先遍历，再用它们读取和计算表达式树。

为什么子结点顺序很重要

遍历顺序需要有序根树。回顾上一节：有序树规定了每个顶点的子结点从左到右的顺序。考虑下面的树：

$A$ 是根。只要算法从左到右处理子结点，$B$ 就会先于 $C$。在 $B$ 下方，$D$ 先于 $E$。这棵树是二叉树，所以 $F$ 位于 $C$ 的右侧这一点也会影响中序遍历。

如果子结点顺序没有规定，那么 $B,C$ 和 $C,B$ 都可以。确定性的遍历既需要树结构，也需要子结点顺序。

递归思维天然适合树

第 7 章通过规模更小的同类结构定义递归结构。根树恰好具有这种形态：

1. 它有一个根； 2. 每个子结点又是一个更小子树的根。

以 $v$ 为根的子树包含 $v$ 以及 $v$ 的全部后代。遍历算法会处理根，并递归处理各个子树。不同遍历之间的区别在于：什么时候处理根。

访问一个顶点是指在该顶点执行所需操作，例如输出标签或累加数值，而不是仅仅沿边经过它。

前序遍历：先根后子树

前序遍历先访问顶点，再从左到右遍历它的各个子树。

PREORDER(v)
    访问 v
    对 v 的每个子结点 c，从左到右执行
        PREORDER(c)

基本情况是叶子：访问叶子后直接停止，因为它没有子树。

对于示例树，

路线从 $A$ 开始，完整处理 $B$ 的子树后才进入 $C$ 的子树。当前对象必须先于内部内容处理时，前序遍历很自然，例如先输出文件夹名称，再列出其中的文件。

后序遍历：先子树后根

后序遍历先从左到右递归访问全部子树，最后访问当前顶点。

POSTORDER(v)
    对 v 的每个子结点 c，从左到右执行
        POSTORDER(c)
    访问 v

对同一棵树，

每个子结点都先于父结点出现。当父结点结果依赖已完成的子结点结果时，后序遍历很有用，例如先测量全部文件大小，再计算文件夹总大小。

中序遍历：位于两棵二叉子树之间

中序遍历专门针对二叉树定义：

1. 遍历左子树； 2. 访问根； 3. 遍历右子树。

INORDER(v)
    若 v 有左子结点
        INORDER(v.left)
    访问 v
    若 v 有右子结点
        INORDER(v.right)

对于示例树，

$C$ 没有左子结点，所以先访问 $C$，再访问它的右子结点 $F$。若一个顶点有三个或更多有序子结点，父结点没有唯一的“中间位置”，因此中序遍历不能自然地推广到这种情况。

每个顶点只访问一次

每种遍历都会恰好访问 $n$ 个顶点各一次，并以固定次数检查每条子边。因此，它的步数为

递归调用还要记住尚未完成的祖先。同一时刻每层至多有一个活跃调用，所以同时活跃的调用数与树高 $h$ 成正比：

平衡良好的树高度可能很小，而链状树有 $h=n-1$。两种情况下都要访问 $n$ 个顶点，但链状树需要更深的递归调用序列。

选择前序、后序或中序遍历，再直接点击树上的顶点预测访问序列。正确选择会点亮当前递归路线；错误选择则指出必须先完成哪棵子树或哪个父结点。完成后可以动画回放自己的最终序列。

表达式树为公式赋予结构

算术表达式包含数值和运算符。表达式树是一棵二叉树，其中

• 每个叶子存放一个操作数，例如数字或变量；
• 每个内部顶点存放一个二元运算符，例如 $+,-,\times$ 或 $\div$；
• 左、右子树分别表示运算符的左、右输入。

考虑表达式

根是 $\times$。根的左子树表示 $3+5$，右子树表示 $10-4$：

树结构无需依赖运算优先级约定就能记录分组。交换减法顶点的两个子结点会把 $10-4$ 变成 $4-10$，因此左右位置不能丢失。

三种遍历产生三种表达式记法

把不同遍历顺序应用到表达式树上，会得到三种常见表达式格式。

中缀记法

中序遍历把运算符放在两个输入之间。为了保留子树边界，必须恢复括号：

这种格式称为中缀记法，因为运算符位于操作数中间。

前缀记法

前序遍历把每个运算符放在两个操作数子表达式之前：

这称为前缀记法。如果每个运算符的输入个数已知，就不需要括号，因为可以根据顺序重建树。

后缀记法

后序遍历把每个运算符放在两个操作数子表达式之后：

这称为后缀记法。同样，固定的运算符输入个数使括号可以省略。

计算表达式树

表达式求值遵循与后序遍历相同的依赖：先计算子结点，再把父运算符作用到子结点结果上。

递归定义 $\operatorname{eval}(v)$：

其中 $L,R$ 分别是左、右子结点。

对于示例，先计算下面两棵子树：

再计算根：

完整依赖流水线为

除法还带来一个重要边界情况：计算 $a\div b$ 之前，算法必须检查 $b\ne0$。树形合法，并不保证它表示的算术表达式有定义。

通过分配运算符与叶子值来建造一棵两层表达式树。锻造炉会同步更新完整括号中缀、前缀、后缀与自底向上求值。交换子树会显示操作数顺序的影响，除以零则会主动中止求值流水线。

本节检查表

• 遍历定义了可重复的单次访问顺序。
• 前序遍历在子树之前访问父结点。
• 后序遍历在父结点之前访问子树。
• 中序遍历是“左子树、父结点、右子树”，只适用于二叉树。
• 三种遍历访问 $n$ 个顶点都需要 $\Theta(n)$ 时间。
• 表达式树的叶子是操作数，内部顶点是运算符。
• 前序、中序、后序分别产生前缀、中缀、后缀记法。
• 求值必须自底向上，并保留左右操作数位置。

现在，我们已经能处理给定的树。第 10.3 节会让树边承担新的任务：左右分支变成前缀编码中的比特，符号频数则决定哪些叶子应当更浅、哪些可以更深。