二叉树的概念与存储 ​

前面我们学习了链表——每个节点有一个后继。如果把这个限制放宽，允许每个节点有两个后继，就得到了二叉树。

二叉树是最基础也最重要的树形数据结构。红黑树、AVL 树、B 树、堆——这些高级结构本质上都是二叉树的变体或扩展。掌握二叉树，是理解这些复杂结构的前提。

二叉树的定义 ​

二叉树有一个递归定义：

二叉树要么是空树，要么由一个根节点和两棵互不相交的二叉树（左子树和右子树）组成。

用图来理解：

       A          ← 根节点
      / \
     B   C        ← A 的左子树根节点 B，右子树根节点 C
    / \   \
   D   E   F      ← 叶子节点（没有子节点）

关键特征：

1. 每个节点最多有两个子节点
2. 子节点有左右之分，顺序不能颠倒
3. 即使只有一个子节点，也要明确是左子节点还是右子节点

这个递归定义非常重要——它直接导致了二叉树的很多操作都可以用递归实现。

基本术语 ​

学习二叉树，需要掌握以下术语：

深度和高度是两个容易混淆的概念：

层级    深度    节点
 1       0       A        ← 根节点深度为 0
        / \
 2       1      B   C     ← 深度为 1
        / \      \
 3       2     D   E   F  ← 深度为 2

树的高度 = 2（从根到最远叶子的边数）

• 深度 (Depth)：从根到该节点的边数（根的深度为 0）
• 高度 (Height)：从该节点到最远叶子的边数（叶子高度为 0）
• 层 (Level)：深度 + 1（根在第 1 层）

注意：有些教材定义深度从 1 开始，这里采用从 0 开始的定义，与大多数算法书籍一致。

特殊二叉树类型 ​

满二叉树 (Perfect Binary Tree) ​

每一层都被完全填满的二叉树。

       1           层 1：1 个节点
      / \
     2   3         层 2：2 个节点
    / \ / \
   4  5 6  7       层 3：4 个节点

满二叉树的性质：

• 第 k 层有 $2^{k-1}$ 个节点
• 深度为 h 的满二叉树有 $2^{h+1} - 1$ 个节点
• 叶子节点全部在最后一层

完全二叉树 (Complete Binary Tree) ​

除了最后一层，每层都是满的，且最后一层的节点从左到右连续排列。

完全二叉树 ✓           非完全二叉树 ✗
       1                      1
      / \                    / \
     2   3                  2   3
    / \                        / \
   4   5                      4   5
                           （最后一层不是从左到右连续）

完全二叉树的重要性：

• 堆就是用完全二叉树实现的
• 可以用数组高效存储，无需指针

平衡二叉树 (Balanced Binary Tree) ​

任意节点的左右子树高度差不超过 1。

平衡 ✓                不平衡 ✗
       1                   1
      / \                   \
     2   3                   2
    /                         \
   4                           3
                                \
                                 4

平衡二叉树保证了树的高度为 $O(\log n)$，从而保证了操作的效率。AVL 树、红黑树都是平衡二叉树的实现。

二叉搜索树 (Binary Search Tree, BST) ​

满足以下性质的二叉树：

• 左子树所有节点的值 < 根节点的值
• 右子树所有节点的值 > 根节点的值
• 左右子树也是二叉搜索树

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

BST 的特点是中序遍历得到有序序列。我们将在后续章节详细介绍。

节点定义 ​

在 JavaScript 中，我们用类来定义二叉树节点：

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;      // 节点值
        this.left = left;    // 左子节点
        this.right = right;  // 右子节点
    }
}

这个定义非常简洁：一个值，两个指针。

构建一棵树：

// 手动构建示例树
//        1
//       / \
//      2   3
//     / \
//    4   5

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

从数组构建（层序）：

LeetCode 中经常用数组表示二叉树，需要转换：

function buildTree(arr) {
    if (!arr || arr.length === 0 || arr[0] === null) return null;
    
    const root = new TreeNode(arr[0]);
    const queue = [root];
    let i = 1;
    
    while (queue.length > 0 && i < arr.length) {
        const node = queue.shift();
        
        // 左子节点
        if (i < arr.length && arr[i] !== null) {
            node.left = new TreeNode(arr[i]);
            queue.push(node.left);
        }
        i++;
        
        // 右子节点
        if (i < arr.length && arr[i] !== null) {
            node.right = new TreeNode(arr[i]);
            queue.push(node.right);
        }
        i++;
    }
    
    return root;
}

// 使用示例
const tree = buildTree([1, 2, 3, 4, 5, null, 6]);
//        1
//       / \
//      2   3
//     / \   \
//    4   5   6

存储方式 ​

二叉树有两种存储方式，各有适用场景。

链式存储（链表形式） ​

每个节点存储值和两个指针，这是最常用的方式。

内存中的表示：

┌─────────────────┐
│  val: 1         │
│  left: ───────────────┐
│  right: ──────────────│──────┐
└─────────────────┘     │      │
                        ↓      │
                ┌───────────┐  │
                │  val: 2   │  │
                │  left: ─────────→ TreeNode(4)
                │  right: ────────→ TreeNode(5)
                └───────────┘  │
                               ↓
                       ┌───────────┐
                       │  val: 3   │
                       │  left: null
                       │  right: null
                       └───────────┘

优点：

• 结构直观，操作灵活
• 插入和删除只需修改指针
• 不需要连续内存空间

缺点：

• 每个节点需要额外空间存储指针
• 无法通过索引直接访问节点

数组存储（顺序存储） ​

对于完全二叉树，可以用数组存储，通过索引计算父子关系。

索引关系（0-based）：

树形表示：                数组表示：
       1[0]              index: 0  1  2  3  4  5
      /    \             value: 1  2  3  4  5  6
   2[1]    3[2]
   /  \    /
 4[3] 5[4] 6[5]

验证索引关系：
- 节点 2（索引 1）的父节点：(1-1)/2 = 0 → 节点 1 ✓
- 节点 1（索引 0）的左子：2*0+1 = 1 → 节点 2 ✓
- 节点 1（索引 0）的右子：2*0+2 = 2 → 节点 3 ✓

为什么这个公式成立？

完全二叉树的每一层节点数是固定的（除了最后一层）：

• 第 1 层：1 个节点（索引 0）
• 第 2 层：2 个节点（索引 1, 2）
• 第 3 层：4 个节点（索引 3, 4, 5, 6）
• ...

对于索引为 i 的节点：

• 它的左子节点在下一层的第 1 个位置 → 2i + 1
• 它的右子节点紧随其后 → 2i + 2
• 反过来，知道子节点索引 j，父节点就是 (j - 1) / 2

优点：

• 空间利用率高，无需存储指针
• 可以通过索引快速访问任意节点

缺点：

• 只适合完全二叉树
• 非完全二叉树会浪费大量空间
• 插入删除可能需要移动大量元素

适用场景：堆是数组存储的典型应用，后续章节会详细介绍。

二叉树的数学性质 ​

掌握这些性质有助于分析算法复杂度：

性质 1：第 i 层最多有 $2^{i-1}$ 个节点（i ≥ 1）

性质 2：深度为 k 的二叉树最多有 $2^{k+1} - 1$ 个节点

性质 3：对于任意二叉树，设叶子节点数为 $n_0$，度为 2 的节点数为 $n_2$，则：

$$n_0 = n_2 + 1$$

证明：设度为 1 的节点数为 $n_1$，总节点数 $n = n_0 + n_1 + n_2$。

总边数 = 总节点数 - 1（因为除根外每个节点有一条入边）

总边数 = $n_1 + 2n_2$（每个度为 k 的节点贡献 k 条出边）

因此：$n - 1 = n_1 + 2n_2$

代入 $n = n_0 + n_1 + n_2$：

$n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$

$n_0 = n_2 + 1$ ✓

性质 4：有 n 个节点的完全二叉树的高度为 $\lfloor \log_2 n \rfloor$

这意味着完全二叉树的操作（如堆的插入删除）复杂度是 $O(\log n)$。

二叉树 vs 链表 ​

链表可以看作特殊的二叉树——每个节点只有一个子节点：

链表：1 → 2 → 3 → 4

等价于退化的二叉树：
    1
     \
      2
       \
        3
         \
          4

这种退化情况是二叉搜索树的最坏情况，高度变成 O(n)，失去了树结构的优势。

但好消息是，链表的很多技巧可以迁移到二叉树：

• 递归思想：链表的递归遍历 → 二叉树的递归遍历
• 虚拟节点：链表的 dummy head → 二叉树中有时也有用
• 快慢指针：在某些树问题中有变体应用

本章小结 ​

1. 二叉树的定义：递归定义——空树，或根 + 左子树 + 右子树
2. 基本术语：根、叶子、父、子、深度、高度、层
3. 特殊类型：满二叉树、完全二叉树、平衡二叉树、BST
4. 存储方式：链式存储（通用）、数组存储（完全二叉树）
5. 数学性质：$n_0 = n_2 + 1$，完全二叉树高度 $O(\log n)$

下一章我们将学习二叉树的遍历方法——前序、中序、后序遍历。遍历是二叉树最核心的操作，几乎所有树问题都建立在遍历的基础上。