图论中的有根树

1. 什么是有根树？

在图论中，树是一个无环的连通图。有根树就是其中选定了一个特殊顶点作为根的树。这一个选择就让其他所有节点有了清晰的"上"（朝向根）与"下"（远离根）之分，把一棵普通的树变成了一种层级结构。

一个有用的事实：含 n 个节点的树总是恰好有 n - 1 条边，且任意两个节点之间恰好存在一条路径——不多不少。

2. 关键术语

• 根：最顶端的节点；唯一没有父节点的节点。
• 父节点 / 子节点：若一条边连接 A（更接近根）与 B，则 A 是父节点，B 是子节点。
• 兄弟节点：拥有同一父节点的节点。
• 叶子：没有子节点的节点，即树的"末端"。
• 内部节点：至少有一个子节点的节点。
• 祖先 / 后代：位于通向根的路径上 / 从某节点向下的节点。
• 深度：从根到某节点的边数。根的深度为 0。
• 高度：从某节点向下到叶子的最长距离。树的高度即其根的高度。
• 子树：某节点连同其所有后代。

3. 有根树与无根树

无根树只描述哪些节点相连——没有上下之分。一旦你选定一个根，同一组边便有了方向：现在可以把边理解为从根指向外侧，于是有根树就像一种特殊的有向图。选择不同的根，会从同一棵底层树得到不同的层级结构。

4. 有根树如何表示

在代码中存储有根树有三种常见方式：

• 父节点数组：用数组保存每个节点的父节点（parent[i]）。紧凑，且非常适合"向上走到根"的操作。
• 子节点列表：每个节点保存其子节点列表，是遍历时最灵活的表示。
• 左孩子 / 右兄弟：一种二叉式编码，每个节点只用两个指针就能存储任意 n 叉树。

5. 有根树的类型

• 二叉树：每个节点最多有两个子节点，即"左"和"右"。
• 二叉搜索树 (BST)：保持有序的二叉树，平衡时查找耗时 O(log n)。
• N 叉树：节点可以有任意数量的子节点，就像文件系统的文件夹。
• 平衡树（AVL、红黑树、B 树）会自动保持较小的高度，以保证操作快速。

6. 遍历有根树

访问每个节点称为遍历，主要有两大类：

• 深度优先 (DFS)：尽量往深处走再回溯。对于二叉树，有前序、中序和后序三种方式。
• 广度优先 (BFS)：先访问同一深度的所有节点再往下，也称层序遍历。

如果这听起来很熟悉，那是因为它们正是用于一般图的相同策略。参见我们关于 BFS 与 DFS 的深入讲解。

7. 现实应用

• 文件系统：文件夹和文件构成一棵有根树，根目录位于顶端。
• HTML DOM：每个网页都是一棵由元素构成的有根树——包括你正在阅读的这一个。
• 数据库：B 树和 B+ 树驱动着让查询变快的索引。
• 编译器：源代码被解析成抽象语法树 (AST)。
• 决策树与堆：机器学习模型和优先队列都建立在有根树之上。