第 7 章 · 树

树是「无环的连通图」,它同时是计算机的结构之王(文件系统、DOM、AST、决策树,数据结构课第 5 章的实现,本章的数学)。树的可爱之处在于:结论异常丰富且多数可手证——n 个顶点恰有 n−1 条边、任意两点路径唯一、有根树的计数是卡特兰数。本章把这些性质配齐证明,并处理树的计数与遍历的数学面。

7.1 树的等价刻画:一性质定乾坤

无向树(n ≥ 1 顶点)的以下说法互相等价(任一可作定义):

连通且无环;
任意两顶点间恰有一条简单路径;
连通且恰有 n−1 条边;
无环且恰有 n−1 条边;
加任一条边恰成一个环,去任一条边则不连通(极小连通、极大无环)。

「恰有 n−1 条边」的归纳证明值得走一遍(第 4 章方法论的练习):删去一个叶顶点(度 1),剩下 n−1 个顶点的子图仍连通无环(还是树),由归纳假设有 n−2 条边,加回被删的那条,共 n−1 条。∎

森林 = 不相交的树的并;k 棵树的森林恰有 n−k 条边。这个「边数 = 顶点数 − 连通分量数」的公式在数据结构课第 11 章并查集的实现验证里会用到。

7.2 有根树:层次与术语

给树指定一个根,全树的顶点获得「辈分」:父、子、祖先/后代、叶子(无子)、内点、层(根为第 0 层)、高度(最深层的层数)。关键性质:

m 叉树的边数与顶点关系:满 m 叉树(每个内点恰 m 个子)有 i 个内点则恰 (m−1)i + 1 个顶点(每次「出生」一个内点带来 m 个孩子,净增 m−1);
高度下界:n 个顶点的 m 叉树高 ≥ ⌈log_m n⌉(每层至多 m^h 个顶点,倒过来推出)。这个下界是「平衡树为什么快」(数据结构课第 5 章的 O(log n))的数学本质:高 = 比较次数,满树最矮;
满二叉树的叶与内点:n₀ = n₂ + 1(叶数 = 度 2 的内点数 + 1,握手定理一行推出,考试高频)。

7.3 树的遍历:三种顺序的定义与互推

前序(根左右)、中序(左根右)、后序(左右根),层序(BFS)。数学侧的两个经典事实:

遍历序列的还原:前序 + 中序唯一确定一棵二叉树(前序第一个是根,中序里根左边是左子树,递归);后序 + 中序同理。前序 + 后序不唯一(单孩子的树分不清左右);这是「需要中序」的根本原因,表达式树(编译器课第 5 章)靠它还原表达式;
表达式树:叶是操作数、内点是运算符。前序 = 前缀表达式(波兰式),后序 = 后缀表达式(逆波兰式,数据结构课第 3 章的计算器),中序(加括号)= 中缀。「一种树、三种序列、三种记法」的三位一体。

7.4 树的计数:卡特兰数登场

n 个顶点的标号树(顶点有名字)有多少棵?Cayley 公式:n^(n−2) 棵(3 个顶点 3 棵、4 个顶点 16 棵, Prufer 序列可证,考试若出会给提示)。n 个顶点的不同构无标号树数量增长慢得多(n = 10 时 106 种),OEIS A000055。

n 个结点的二叉树形态数 = 卡特兰数 Cₙ = C(2n,n)/(n+1):1, 1, 2, 5, 14, 42, 132……它的推导是组合数学(第 5 章)的招牌表演:n 个内点的二叉树,递归分左右子树,得递推 Cₙ = Σ CᵢCₙ₋₁₋ᵢ,解出闭式(生成函数法,第 10 章的主角预告)。卡特兰数还数:n 对括号的合法匹配、出栈序列数(数据结构课第 3 章「栈的混合进出」)、凸多边形三角剖分——同一个递推结构在四个领域现身,这是数学「殊途同归」之美的标准展品。

7.5 生成树与最小生成树

生成树:包含图全部顶点的树形子图。存在性:图连通 ⟺ 有生成树。最小生成树(MST):边权和最小的生成树,数据结构课第 6 章的 Prim/Kruskal 在此补数学:两者都依赖切分定理(任一「横切」图顶点集的割中,权最小的横切边必属于某棵 MST),Kruskal 的「不成环就收」正是对切分定理的贪心兑现(第 4 章交换论证的图论版)。

MST 的两个工程投影:网络布线(最少光缆连通)、聚类分析(层次聚类的树状图)。唯一性:MST 唯一 ⟺ 边权两两不同(相同权时可以有多棵,考试爱出反例)。

常见错误

树的边数记成 n。是 n−1(连通无环的代价);算 MST 权重时多算一条边全错。
二叉树叶/内点公式用反。n₀ = n₂ + 1(叶子多一个);验证手段:画 n=1(1 叶 0 内)、n=3(2 叶 1 内)的小树。
卡特兰数硬背数列不懂递推。递推 Cₙ = Σ CᵢCₙ₋₁₋ᵢ 才是可迁移的;背到 42 用得完,懂递推才算会。
「前序+后序可还原树」。不成立(单孩子歧义);面试经典陷阱。

练习

证明:树中至少有两个叶顶点(取最长路径的端点,反证:若端点有别的邻点,路径可延长或出现环)。
手算:满 m 叉树有 81 个叶、m = 3,求内点数与总顶点数(用 n = (m−1)i + 1 反推)。
动手:写程序生成 n = 4 的全部 16 棵标号树(枚举 n^(n−2) = 16 的 Prufer 序列,解码成树),验证 Cayley 公式;顺便体会 Prufer 编码与树的「一一对应」。
思考:卡特兰数出现在「括号匹配、出栈序列、二叉树、三角剖分」四个问题。挑两个,构造它们之间的显式双射(第 1 章的双射思想),证明「数量相等」不是巧合。