关于树的易混淆概念

树的层数、高度、深度等概念是数据结构中非常重要的基础知识，但它们有时会让人感到混淆。

1. 树的基本结构

我们先来看一棵简单的二叉树：

        A
       / \
      B   C
     / \   \
    D   E   F

• A 是根节点。
• B 和 C 是 A 的子节点。
• D、E 和 F 是叶子节点（没有子节点的节点）。

2. 树的层数（Level）

定义

• 层数 是从根节点开始计数的，根节点所在的层为第 1 层。
• 每向下一层，层数加 1。

计算方式

• 第 1 层：根节点 A。
• 第 2 层：B 和 C。
• 第 3 层：D、E 和 F。

总层数

• 总层数是从根节点到最深叶子节点的层数。
• 在这棵树中，总层数为 3。

用途

• 层数常用于描述节点在树中的位置，例如“节点 E 在第 3 层”。

3. 树的高度（Height）

定义

• 高度 是从某个节点到其最远叶子节点的最长路径上的边数。
• 如果从根节点开始计算，则称为整棵树的高度。

计算方式

• 对于每个节点：
  • 叶子节点的高度为 0（因为没有子节点）。
  • 非叶子节点的高度 = 其子节点的最大高度 + 1。
• 整棵树的高度 = 根节点的高度。

例子

• 节点 F 是叶子节点，高度为 0。
• 节点 C 的高度 = 子节点 F 的高度 + 1 = 1。
• 节点 B 的高度 = 子节点 D 和 E 的最大高度 + 1 = 1。
• 节点 A 的高度 = 子节点 B 和 C 的最大高度 + 1 = 2。

因此，这棵树的高度为 2。

用途

• 树的高度常用于衡量树的平衡性或复杂度。例如，在 AVL 树中，要求左右子树的高度差不超过 1。

4. 节点的深度（Depth）

定义

• 深度 是从根节点到某个节点的路径上的边数。
• 根节点的深度为 0。

计算方式

• 根节点 A 的深度为 0。
• 节点 B 和 C 的深度为 1（从 A 到 B 或 C 的路径上有 1 条边）。
• 节点 D、E 和 F 的深度为 2。

用途

• 深度常用于描述节点在树中的纵向位置。例如，“节点 F 的深度为 2”。

5. 树的宽度（Width）

定义

• 宽度 是指树中某一层实际存在的最大节点数 。
• 它通常用来描述树的“横向扩展程度”。

注意：我们需要遍历每一层，统计每层的节点数，并取其中的最大值作为树的最大宽度。换句话说，树的宽度并不关心某一层理论上最多可以放多少节点，而是关注当前层实际有多少节点。

计算方式

• 第 1 层：只有根节点 A，宽度为 1。
• 第 2 层：有节点 B 和 C，宽度为 2。
• 第 3 层：有节点 D、E 和 F，宽度为 3。

因此，这棵树的最大宽度为 3。

用途

• 树的宽度常用于分析空间复杂度。例如，在 BFS 中，队列的空间需求取决于树的最大宽度。

6. 树的总结

7. 代码实现

计算树的高度

public int treeHeight(TreeNode root) {
    if (root == null) {
        return 0; // 空树的高度为 0
    }
    int leftHeight = treeHeight(root.left);
    int rightHeight = treeHeight(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

计算节点的深度

public int nodeDepth(TreeNode root, TreeNode target) {
    if (root == null) {
        return -1; // 目标节点不存在
    }
    if (root == target) {
        return 0; // 找到目标节点，深度为 0
    }
    int leftDepth = nodeDepth(root.left, target);
    if (leftDepth != -1) {
        return leftDepth + 1; // 在左子树中找到目标节点
    }
    int rightDepth = nodeDepth(root.right, target);
    if (rightDepth != -1) {
        return rightDepth + 1; // 在右子树中找到目标节点
    }
    return -1; // 目标节点不在树中
}

计算树的最大宽度

public int maxWidth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int maxWidth = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        maxWidth = Math.max(maxWidth, size); // 更新最大宽度

        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    return maxWidth;
}

8. 总结

• 层数：从根节点开始计数，根节点为第 1 层。
• 高度：从某个节点到最远叶子节点的最长路径上的边数。
• 深度：从根节点到某个节点的路径上的边数。
• 宽度：某一层实际的最大节点数。