1. 概述
在本教程中，我们将讨论树结构中两个常见概念：阶（Order）和度（Degree）。
我们会分别定义这两个概念，通过示例说明它们的含义，并讲解如何计算一棵树的度，以及相关算法的时间复杂度。
2. 树的阶（Order）
2.1 定义
树的阶（Order）指的是树中任意节点所能拥有的最大子节点数。换句话说，如果一棵树的阶为 N，那么该树中所有节点的子节点数量都不能超过 N。
例如，B-树（B-Tree）中经常使用“阶”这个概念。当我们说一个 B-树是阶为 N 的树时，意味着它的每个节点最多可以有 N 个子节点。
2.2 示例
二叉搜索树（Binary Search Tree）是一种阶为 2 的树，因为每个节点最多有两个子节点：
B-树（B-Tree）中，若阶为 3，则每个节点最多可以有 3 个子节点：
3. 树的度（Degree）
3.1 定义
树的度是指树中某个节点的最大子节点数。更具体地说，树的度是整棵树中所有节点的度中的最大值。
节点的度定义为其拥有的子节点数量。因此，要得到一棵树的度，我们需要遍历整棵树，计算每个节点的度，然后取最大值。
3.2 算法实现
我们可以使用深度优先搜索（DFS）来遍历整棵树，并递归地计算每个节点的度：
algorithm ComputeDegree(node, children)
// INPUT
// node = a node in the tree
// children = a map associating each node with its children
// OUTPUT
// The maximum degree found in the tree rooted at node
degree <- length(children[node])
for child in children[node]:
degree <- MAX(degree, ComputeDegree(child, children))
return degree
Java 实现示例：
public class TreeDegreeCalculator {
public static int computeDegree(int node, Map<Integer, List<Integer>> children) {
int maxDegree = children.getOrDefault(node, Collections.emptyList()).size();
for (int child : children.getOrDefault(node, Collections.emptyList())) {
maxDegree = Math.max(maxDegree, computeDegree(child, children));
}
return maxDegree;
}
}
3.3 时间复杂度分析
- 时间复杂度为 **O(N + M)**，其中
N是节点数，M是边数。 - 因为树中边数
M = N - 1，所以也可以简化为 **O(N)**。 - 我们每个节点和边都只访问一次，这与 DFS 遍历的时间复杂度一致。
4. 总结
| 概念 | 含义 | 计算方式 |
|---|---|---|
| 阶（Order） | 节点最多可拥有的子节点数 | 由树结构定义决定（如 B-Tree 阶为 N） |
| 度（Degree） | 整棵树中节点度的最大值 | 遍历所有节点，取最大子节点数 |
✅ 小贴士：
- “阶”是结构定义，通常用于 B-树、B+ 树等数据结构。
- “度”是统计性质，通常用于分析树的形态，比如判断是否为二叉树等。
⚠️ 踩坑提醒：
- 不要混淆“阶”和“度”，它们虽然都涉及子节点数量，但一个是限制条件，一个是实际统计结果。
- 在实际编程中，尤其在树结构的构建和验证阶段，这两个概念可能会导致逻辑错误，务必区分清楚。