有根树与祖先关系

形式陈述 ​

有根树是二元组 $(T,r)$，其中 $T=(V,E)$ 是一棵树，$r\in V$ 是指定的根。对任意 $v\ne r$，从 $r$ 到 $v$ 的唯一简单路径上紧邻 $v$ 的顶点称为 $v$ 的父亲，记为 $\mathrm{parent}(v)$；其余与 $v$ 相邻且父亲为 $v$ 的顶点称为 $v$ 的孩子。

若顶点 $u$ 位于从 $r$ 到 $v$ 的唯一简单路径上，则称 $u$ 是 $v$ 的祖先，记作 $u{⪯}_{r}v$；此时 $v$ 是 $u$ 的后代。允许 $u=v$ 时得到自反祖先关系；要求 $u\ne v$ 时称真祖先。顶点深度为

$${\mathrm{depth}}_r(v)={\mathrm{dist}}_T(r,v).$$

由 $v$ 及其全部后代诱导的子树称为以 $v$ 为根的子树。

祖先关系 ${⪯}_r$ 是 $V$ 上的偏序。任意顶点的祖先集合沿根路径全序排列；因此两个顶点的公共祖先若非空，也按深度全序排列，并具有唯一最深元素。

直觉 ​

无根树只告诉我们哪些顶点相连；选定根以后，每条边才获得“向上/向下”的方向。父亲、深度、子树和祖先都依赖这个选择，而不是树本身固有的标签。

根把树变成一套层级坐标系。沿父指针反复上跳必在有限步内到达根；沿孩子边向下则不会回到先前节点。树的无环性保证这种层级没有矛盾，连通性保证每个顶点都有唯一根路径。

例子与边界 ​

设边为

$$\{1,2\},\{1,3\},\{2,4\},\{2,5\}.$$

取根 $1$ 时，$1$ 是所有顶点的祖先，$2$ 是 $4,5$ 的父亲，$\mathrm{depth}(4)=2$。若改取根 $4$，则 $2$ 成为 $1$ 的父亲，原先的祖先关系随之改变。

在一般有向无环图中，一个节点可能有多个父亲，两个节点也可能有多个互不比较的最低公共祖先；树中唯一根路径提供的结论不再成立。根树还不自动带孩子次序：若需要“第一个孩子”或括号序列编码，必须额外指定有序根树结构。

推论与应用 ​

根到任意顶点的简单路径唯一，来自树的等价刻画公理库树的等价刻画Characterizations of trees有限简单无向图是树，等价于刚好连通、刚好无环或任意两点间存在唯一简单路径。中“连通且无环”等价于“两点间恰有一条简单路径”。父节点、深度和祖先关系都建立在这条唯一性上。

树公理库树Tree连通且无圈的无向图，等价地任意两点间有唯一简单路径。的唯一简单路径性质保证父亲和祖先定义良好。祖先偏序直接定义最近公共祖先公理库最近公共祖先Lowest common ancestor · LCA有根树中同时为两个顶点祖先且深度最大的唯一顶点及其查询问题。与 Level Ancestor 查询；深度和子树区间支撑 Euler Tour、重链剖分与树上动态规划。

把父亲函数视为从非根顶点到顶点的映射，可用二进制倍增预计算 $2^k$ 级祖先。对子树做深度优先遍历时，进入与离开时间形成区间，从而把许多树查询转为数组区间问题。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, §1.5.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapters 20 and 22.
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001, §4.1.