10.1 树的性质、根树与二叉树

第 9 章曾用分支图表示条件概率路线。那些图有一种特殊形状：路线不断分开，却不会重新汇合成环。现在，我们把这种形状作为数学对象来研究。

文件系统、组织架构、搜索过程、语法分析、网络路由、数据压缩和决策过程都会使用树。为了用统一语言讨论这些场景，我们先从最基本的组成部分开始。

顶点与边

一个独立对象或位置称为顶点。本章中的结点与顶点含义相同。我们常用 $a,b,c$ 等符号给顶点命名。

一条边连接两个不同顶点。本节中的连接没有方向，因此连接 $a$ 与 $b$ 的边可以写成无序对

顺序不重要，即 $\{a,b\}=\{b,a\}$。被一条边连接的两个顶点称为相邻顶点，也称彼此为邻居。

顶点 $v$ 的度写作 $\deg(v)$，表示接触 $v$ 的边数。例如，若 $v$ 与三个不同邻居相连，则 $\deg(v)=3$。

路径、连通与环

从 $v_0$ 到 $v_k$ 的一条路径是由不同顶点组成的序列

其中每对相邻位置上的顶点都有边相连。路径的长度是它包含的边数，在这个记号中等于 $k$。

如果任意两个顶点之间都存在路径，就称这个连接结构是连通的。连通表示没有顶点与结构的其他部分隔离。

一个环是闭合路线

其中中间顶点彼此不同。环最终回到起点，但不是沿同一条边立即折返。

现在可以给出核心定义。

> 树是一个连通、无向而且不含环的结构。

只有一个顶点而没有边的结构也算一棵树：按约定它是连通的，而且显然没有环。

两个最初例子

链 $a-b-c-d$ 是树。任意顶点都能到达其他顶点，而且没有路线闭合成环。

边集为 $\{a,b\},\{b,c\},\{c,a\}$ 的三角形不是树，因为三条边形成一个环。三个互相隔离的顶点也不是树，因为它们不连通。

在无根树中，度为 $1$ 的顶点称为叶子。至少含两个顶点的有限树至少有两个叶子。为了说明原因，选择一条长度最大的路径。如果某个端点还有路径之外的邻居，就能继续延长路径；如果这个邻居已经在路径上，又会产生环。因此，两个不同端点的度都只能是 $1$，它们都是叶子。

唯一路径性质

在树中，任意两个顶点之间恰好有一条路径。

为什么不能有两条？假设顶点 $u,v$ 之间存在两条不同路径。从 $u$ 出发，找到两条路径首次分开的地方，再继续前进到它们重新相遇的地方。两段不同路线会合成一个环，这与树不含环矛盾。

逆向结论也成立：若每对顶点之间恰好有一条路径，那么结构必然连通；它也不可能含环，因为环上的两个顶点之间会有两条路线。因此，这个结构就是树。

于是得到一个等价刻画：

逐条添加或删除边来建造连接网络。工作台会实时识别连通分量与环，标出两个选定顶点之间的唯一路线，并允许你修复断开的结构或从环中拆除一条边。

含 $n$ 个顶点的树有 $n-1$ 条边

令 $n$ 表示顶点数。每棵有限树都满足

其中 $E$ 是边集合，$|E|$ 是边的数量。

可以用第 3 章的数学归纳法证明这个公式。

1. 只有一个顶点的树有 $0=1-1$ 条边。 2. 假设每棵含 $n$ 个顶点的树都有 $n-1$ 条边。 3. 取一棵含 $n+1$ 个顶点的树，删除一个叶子以及接触它的唯一一条边。剩余结构仍是树：删除端点不会产生环，也不会切断其余任意两个顶点之间的路径。 4. 根据归纳假设，剩余树有 $n-1$ 条边。恢复被删除的边后共有 $n$ 条边，恰好等于 $(n+1)-1$。

只有边数条件还不够。一个含 $n$ 个顶点和 $n-1$ 条边的结构，可能在某个部分含有环，同时在另一处存在孤立顶点。还必须增加一个条件。下面任意一组条件都足够：

每组条件都会强制满足树定义中缺少的另一半。

若删除某条边会使连通结构变得不连通，就称这条边为桥。树中的每条边都是桥：如果删除 $\{u,v\}$ 后 $u,v$ 仍然连通，那么剩余路径与 $\{u,v\}$ 原本就会组成一个环。

因此，树是“最小连通”的：删除任意边都会破坏连通性。它也是“最大无环”的：在两个原本不相邻的顶点间增加一条边，新边与原有唯一路径会恰好形成一个环。

选择根会产生层级关系

无根树只描述对称的连接。根树会选择一个顶点作为根，再从根的角度观察其他所有顶点。

由于根到任意顶点 $v$ 都有唯一路径，所以这条路径上紧靠 $v$ 的前一个邻居是确定的。它称为 $v$ 的父结点，而 $v$ 是它的子结点。根没有父结点，其他每个顶点都恰有一个父结点。

同样的路径还定义了更多层级术语：

• 拥有相同父结点的顶点互为兄弟结点；
• $v$ 的祖先位于从根到 $v$ 的路径上；
• 若某个顶点通向根的路径经过 $v$，它就是 $v$ 的后代；
• 根树中没有子结点的顶点是叶子；
• 至少有一个子结点的顶点是内部顶点。

改变根不会改变顶点与边，却可能改变所有父子、祖先和后代关系。

深度与高度

顶点 $v$ 的深度是根到 $v$ 的唯一路径长度：

根的深度为 $0$。深度相同的顶点构成同一层。

根树的高度是所有顶点深度的最大值：

深度属于单个顶点，高度概括整棵根树。只有一个顶点的根树高度为 $0$。

在固定树中移动根，观察每条边怎样重新确定父子方向。实验室会重新计算层、祖先、后代、叶子与高度，从而区分哪些性质属于底层无根树，哪些性质依赖根的选择。

有序树与二叉树

在某些根树中，每个顶点的子结点具有规定的左右顺序，这种结构称为有序根树。即使顶点和父子边完全相同，子结点顺序不同也会得到不同的有序树。

二叉树是每个顶点最多有两个子结点的有序根树，两个位置分别称为左子结点和右子结点。一个顶点可以只有右子结点；左右表示位置，不只是数量。

两种特殊形态很常用：

• 满二叉树中的每个顶点要么没有子结点，要么恰有两个子结点；
• 完美二叉树既是满二叉树，而且所有叶子深度相同。

若一棵满二叉树有 $I$ 个内部顶点和 $L$ 个叶子，则

原因可以通过两种方式统计边。每个内部顶点贡献两条子边，因此共有 $2I$ 条边。整棵树有 $I+L$ 个顶点，所以又应有 $I+L-1$ 条边。令两种计数相等：

从而得到 $L=I+1$。

高度为 $h$ 的完美二叉树在深度 $d$ 处有 $2^d$ 个顶点。把各层相加，顶点总数为

叶子数为 $2^h$。

这些公式不适用于任意二叉树。一条很长的二叉链可能每层只有一个顶点。使用专门计数公式前，必须先检查题目是否说明“满”或“完美”。

本节检查表

• 树是连通且无环的结构。
• 树中任意两个顶点之间恰有一条路径。
• 含 $n$ 个顶点的有限树有 $n-1$ 条边。
• 删除任意树边会使它断开；增加一条缺失边会产生一个环。
• 选择根会产生父子、深度与高度关系。
• 二叉树区分左、右子结点位置。
• 满与完美是附加条件，不是二叉的同义词。

树的结构已经定义清楚。第 10.2 节将研究算法如何按照明确、可重复的顺序访问每个顶点。