线性结构（数组、链表）的局限在于：它们只有”一维”的先后关系。

但很多现实问题天然是”层次”的——目录结构、组织架构、表达式、决策过程。这时候就需要树。

而二叉树，是所有树结构里最基础、也最重要的一种。

什么是二叉树

二叉树：每个节点最多有两个子节点（左子节点和右子节点）。

几个必须记住的术语：

  • 根节点：最顶层的节点
  • 叶子节点：没有子节点的节点
  • 深度：从根到该节点的边数
  • 高度：从该节点到最远叶子的边数

递归遍历三板斧

处理树的几乎所有问题，都离不开遍历。二叉树有三种经典的深度优先遍历，区别只在于访问根节点的时机：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 前序遍历：根 → 左 → 右
void preorder(TreeNode node) {
    if (node == null) return;
    visit(node);          // 先访问根
    preorder(node.left);
    preorder(node.right);
}

// 中序遍历：左 → 根 → 右
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    visit(node);          // 中间访问根
    inorder(node.right);
}

// 后序遍历：左 → 右 → 根
void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    visit(node);          // 最后访问根
}

看出来了吗？三种遍历的代码结构一模一样，只是 visit(node) 的位置不同。

这三种遍历各有用途：

  • 前序：适合”先处理父节点，再处理子节点”的场景，比如复制一棵树、序列化
  • 中序：二叉搜索树的中序遍历，结果是有序的（这是最经典的性质）
  • 后序：适合”先处理完子节点，再处理父节点”的场景，比如删除一棵树、计算子树的高度

递归为什么适合处理树

递归和树是天生一对，因为树本身就是递归定义的：一棵树 = 一个根节点 + 左子树 + 右子树，而左右子树本身又是树。

所以很多树的问题，都可以用一句话描述解法：

先处理根，再递归处理左右子树。

写树的递归代码，关键是确定”当前节点”要做什么，然后相信递归会帮你处理子树。别试图在脑子里展开整个递归过程，那样会晕。

二叉搜索树（BST）

普通的二叉树没什么规律，查找只能一个个遍历。二叉搜索树加了一条规则：

左子树所有节点 < 根 < 右子树所有节点。

有了这条规则，查找就变成”二分”了：

1
2
3
4
TreeNode search(TreeNode node, int key) {
    if (node == null || node.val == key) return node;
    return key < node.val ? search(node.left, key) : search(node.right, key);
}

每次比较都能排除一半，所以平衡的 BST 查找是 O(log n)。

BST 的增删查都是 O(log n)（平衡情况下），这就是为什么它比链表（O(n)）快得多。

BST 的致命弱点

BST 有个致命问题：如果插入的数据是有序的（比如 1, 2, 3, 4, 5），它会退化成一条链表，查找又变回 O(n)。

为了解决这个问题，才有了各种”自平衡”的树：

  • AVL 树：严格平衡，插入删除旋转次数多，适合读多写少
  • 红黑树：弱平衡，性能更均衡，Java 的 TreeMap、HashMap 的红黑树都是它
  • B+ 树：多叉平衡树，适合磁盘存储，MySQL 索引就是它

所以你看，数据结构是一步步演进出来的：二叉树 → 二叉搜索树 → 平衡树 → B+ 树，每一步都在解决上一步的痛点。

小结

  • 二叉树：树结构的地基，每个节点最多两个子节点
  • 三种遍历：前序、中序、后序，区别只在”访问根的时机”
  • 递归是处理树的核心武器，因为树天然是递归结构
  • 二叉搜索树靠”左小右大”实现 O(log n) 查找，但有退化风险
  • 平衡树（红黑树、B+ 树）是解决退化问题的演进

下一篇讲堆——它其实是”用数组实现的完全二叉树”。