LGT
Learn Graph Theory Team
Expert Operations Research Engineers
目录
1. 什么是有根树？
2. 关键术语
3. 有根树与无根树
4. 如何表示
5. 有根树的类型
6. 遍历有根树
7. 现实应用
1. 什么是有根树？
在图论中，树是一个无环的连通图。有根树就是其中选定了一个特殊顶点作为根的树。这一个选择就让其他所有节点有了清晰的"上"（朝向根）与"下"（远离根）之分，把一棵普通的树变成了一种层级结构。
一个有用的事实：含 n 个节点的树总是恰好有 n - 1 条边，且任意两个节点之间恰好存在一条路径，不多不少。
2. 关键术语
根：最顶端的节点；唯一没有父节点的节点。
父节点 / 子节点：若一条边连接 A（更接近根）与 B，则 A 是父节点，B 是子节点。
兄弟节点：拥有同一父节点的节点。
叶子：没有子节点的节点，即树的"末端"。
内部节点：至少有一个子节点的节点。
祖先 / 后代：位于通向根的路径上 / 从某节点向下的节点。
深度：从根到某节点的边数。根的深度为 0。
高度：从某节点向下到叶子的最长距离。树的高度即其根的高度。
子树：某节点连同其所有后代。
3. 有根树与无根树
无根树只描述哪些节点相连，没有上下之分。一旦你选定一个根，同一组边便有了方向：现在可以把边理解为从根指向外侧，于是有根树就像一种特殊的有向图。选择不同的根，会从同一棵底层树得到不同的层级结构。
看树动起来
构建一棵有根树，观看 DFS 和 BFS 遍历逐个节点点亮。深度、高度和父子关系会一下子变得清晰。
打开可视化工具
4. 有根树如何表示
在代码中存储有根树有三种常见方式：
父节点数组：用数组保存每个节点的父节点（parent[i]）。紧凑，且非常适合"向上走到根"的操作。
子节点列表：每个节点保存其子节点列表，是遍历时最灵活的表示。
左孩子 / 右兄弟：一种二叉式编码，每个节点只用两个指针就能存储任意 n 叉树。
5. 有根树的类型
二叉树：每个节点最多有两个子节点，即"左"和"右"。
二叉搜索树 (BST)：保持有序的二叉树，平衡时查找耗时 O(log n)。
N 叉树：节点可以有任意数量的子节点，就像文件系统的文件夹。
平衡树（AVL、红黑树、B 树）会自动保持较小的高度，以保证操作快速。
6. 遍历有根树
访问每个节点称为遍历，主要有两大类：
深度优先 (DFS)：尽量往深处走再回溯。对于二叉树，有前序、中序和后序三种方式。
广度优先 (BFS)：先访问同一深度的所有节点再往下，也称层序遍历。
如果这听起来很熟悉，那是因为它们正是用于一般图的相同策略。参见我们关于 BFS 与 DFS 的深入讲解。
7. 现实应用
文件系统：文件夹和文件构成一棵有根树，根目录位于顶端。
HTML DOM：每个网页都是一棵由元素构成的有根树，包括你正在阅读的这一个。
数据库：B 树和 B+ 树驱动着让查询变快的索引。
编译器：源代码被解析成抽象语法树 (AST)。
决策树与堆：机器学习模型和优先队列都建立在有根树之上。
常见问题
有根树和无根树有什么区别？
无根树只说明哪些节点相连。有根树指定一个节点为根，从而赋予树一种带有父子关系、有明确顶端的层级结构。
树的深度和高度有什么区别？
深度是从根到某个特定节点的距离（根的深度为 0）。高度是从某节点到其最深叶子的距离；树的高度即根的高度。
有根树是有向图吗？
可以这样看待。一旦选定了根，每条边都隐式地从根指向外侧，使每个非根节点恰好有一个父节点。
含 n 个节点的树有多少条边？
恰好 n - 1 条。再添加任何一条边都会形成环，而树按定义是无环的。
相关文章
BFS 与 DFS
阅读更多 →
最小生成树
阅读更多 →
图论面试题
阅读更多 →