1. 简介
二叉树是一种层次结构，其中每个节点最多有两个子节点。 本文将介绍如何计算二叉树的层数以及节点数量。我们还将探讨层数与节点数量之间的关系。
2. 二叉树的层数定义
在二叉树中，每个节点包含三个部分：一个数据域用于存储值，两个子节点指针分别指向左子节点和右子节点：
class TreeNode {
int data;
TreeNode left;
TreeNode right;
}
最顶层的节点称为根节点（root）。节点的层数定义为该节点与根节点之间的边数。 因此，根节点的层数为 0。如果它有子节点，那么这些子节点的层数为 1。
二叉树的层数是所有节点中最大的层数数值。 例如，我们可以用 5 个节点构建一个层数为 2 的二叉树：
3. 层数与节点数量的计算
要计算二叉树的层数和节点数量，可以采用层序遍历的方式。 我们从根节点开始（层数 0），逐层访问所有节点。
例如，上面图示的遍历顺序是：1、2、3、4、5。
层序遍历本质上是一种广度优先搜索（BFS）策略。我们可以使用队列（Queue）来保证遍历顺序。队列中每个元素包含两个值：当前节点及其层数：
class LevelNode {
TreeNode node;
int level;
}
通过遍历过程，我们可以记录最大层数值，并使用计数器统计节点总数：
public class TreeLevelAndNodeCounter {
public static int[] countTreeLevelAndNodes(TreeNode root) {
if (root == null) return new int[]{0, 0};
int level = 0;
int total = 0;
Queue<LevelNode> queue = new LinkedList<>();
queue.offer(new LevelNode(root, 0));
while (!queue.isEmpty()) {
LevelNode e = queue.poll();
level = Math.max(level, e.level);
total++;
if (e.node.left != null) {
queue.offer(new LevelNode(e.node.left, e.level + 1));
}
if (e.node.right != null) {
queue.offer(new LevelNode(e.node.right, e.level + 1));
}
}
return new int[]{level, total};
}
}
在这个算法中，我们从根节点开始，将其与层数 0 一起加入队列。然后通过循环逐层遍历节点。每访问一个节点，就将其子节点加入队列，并将层数加 1。遍历过程中记录最大层数，最终得到整棵树的层数和节点总数。
如果二叉树有 n 个节点，该算法的时间复杂度为 O(n)，因为我们每个节点只访问一次。
4. 最小与最大节点数
我们可以通过上述算法计算出任意二叉树的节点数和层数。除此之外，我们还可以通过理论分析得出层数为 n 的二叉树的最小和最大节点数。
4.1 最小节点数
要构建一个层数为 n 的二叉树，至少需要 n + 1 个节点。这是因为每一层至少有一个节点。
✅ 定理 1：设
T是层数为n的二叉树，则T至少包含n + 1个节点。
例如，一个层数为 3 的最小节点结构如下：
这种结构看起来像一个链表。
4.2 最大节点数
要构造一个层数为 n 且节点数最多的二叉树，必须满足：
- 每个内部节点都有两个子节点
- 所有叶子节点都在第
n层
这种结构称为“满二叉树”。
✅ 定理 2：设
T是层数为n的二叉树，则T最多包含2^{n+1} - 1个节点。
例如，当 n = 2 时：
- 第 0 层：1 个节点（根）
- 第 1 层：2 个节点
- 第 2 层：4 个节点
总节点数为 1 + 2 + 4 = 7 = 2^3 - 1
对应的结构如下：
5. 数学归纳法证明最大节点数
我们也可以使用数学归纳法来证明定理 2。
基础情况（n = 0）
当层数为 0 时，只有一个根节点，此时节点数为 1。而 2^{0+1} - 1 = 1，符合公式。
归纳假设
假设层数为 k 的二叉树最多有 2^{k+1} - 1 个节点。
归纳步骤
考虑层数为 k+1 的二叉树，其左右子树层数均为 k。根据归纳假设，左右子树最多各包含 2^{k+1} - 1 个节点。加上根节点，总节点数为：
(2^{k+1} - 1) + (2^{k+1} - 1) + 1 = 2^{k+2} - 1
因此，归纳成立，定理得证。
结构示意图如下：
6. 总结
本文介绍了如何通过层序遍历计算二叉树的层数和节点数量，并通过理论分析给出了层数为 n 的二叉树的最小和最大节点数。
- ✅ 最小节点数：
n + 1 - ✅ 最大节点数：
2^{n+1} - 1 - ✅ 使用归纳法证明了最大节点数的正确性
这些结论对于理解二叉树的结构和性能优化具有重要意义。