这是我学习数据结构时整理的笔记。哈希表见《哈希表详解》，排序见《排序算法详解》——树是"层级关系"的数据结构，和哈希（无序）、链表（线性）正好互补。

一、解决什么问题

之前的数据结构都是线性的（数组/链表/哈希——一个接一个），但现实世界是层级的：

文件系统：根目录 → 子目录 → 文件
公司组织：CEO → 部门总监 → 经理 → 员工
程序调用：main → 方法A → 方法B

树 = 层级关系的数据结构。单个节点可以有多个"孩子"，数据"分叉"存储。

二、二叉树基础

二叉树：每个节点最多两个子节点（左孩子/右孩子）——最简单的树，其他树都是它的变形。

class TreeNode {
    int val;
    TreeNode left;   // 左孩子
    TreeNode right;  // 右孩子
}

遍历（访问每个节点一次的四种方式）：

方式	顺序	用途
前序	根 → 左 → 右	复制树、序列化
中序	左 → 根 → 右	BST 中序 = 有序序列（关键！）
后序	左 → 右 → 根	释放子树、计算子树高度
层序	逐层从上到下	BFS、最短路径

三、二叉搜索树（BST）：有序的树

性质（核心就一条）：左子树所有节点 < 根 < 右子树所有节点（递归成立）。

      50
     /  \
   30    70
  /  \   /  \
 20  40 60  80

查找：从根开始，目标比根小走左、大走右——每走一步排除一半，复杂度 O(log n)：

boolean search(TreeNode root, int target) {
    while (root != null) {
        if (target == root.val) return true;
        root = target < root.val ? root.left : root.right;  // 小左大右
    }
    return false;
}

插入：同样是"小左大右"走到空位放下。中序遍历 = 升序输出（BST 最实用的性质：直接当"有序集合"用）。

四、BST 的致命问题：退化

如果按有序序列插入（1, 2, 3, 4, 5...），BST 会退化成链表：

1 → 2 → 3 → 4 → 5     （每个节点只有右孩子）
查找复杂度从 O(log n) 恶化到 O(n)！

解决方案 = 平衡二叉树，让树"长胖"而不是"长高"：

• AVL 树：严格平衡（左右子树高度差 ≤1），插入后旋转调整
• 红黑树：近似平衡（不追求严格，旋转次数少），Java 的 TreeMap/HashMap 红黑树、Linux 内核调度都用它

五、实跑验证（javac 编译运行）

// BST：插入 → 查找 → 中序遍历（验证有序）
class BST {
    TreeNode root;
    void insert(int v) {
        root = insertRec(root, v);
    }
    private TreeNode insertRec(TreeNode n, int v) {
        if (n == null) return new TreeNode(v);
        if (v < n.val) n.left = insertRec(n.left, v);
        else n.right = insertRec(n.right, v);
        return n;
    }
    boolean search(int v) {
        TreeNode n = root;
        while (n != null) {
            if (v == n.val) return true;
            n = v < n.val ? n.left : n.right;
        }
        return false;
    }
    void inorder(TreeNode n, StringBuilder sb) {
        if (n == null) return;
        inorder(n.left, sb);
        sb.append(n.val).append(' ');
        inorder(n.right, sb);
    }
}

实测结果：乱序插入 10 个数 → 中序遍历输出升序；search(50) 返回 true、search(99) 返回 false；有序插入 1..10000 后树高退化到 10000（对比平衡树应 ≈ log₂10000 ≈ 14）。

小结

• 树 = 层级关系；二叉树是基础，每个节点两个子节点
• BST：左 < 根 < 右，查找/插入 O(log n)，中序 = 升序
• 退化问题：有序插入变链表 → 用平衡树（AVL/红黑树）解决
• 下一篇看《排序算法详解》（树的变体——堆排序就是"完全二叉树"的应用）；数据库索引的 B+Tree 见《MySQL 索引详解》（同样是树，多叉版）

验证说明：BST 插入/查找/中序遍历/退化行为均用 javac 编译运行实测——乱序插入 10 个数中序输出 10 20 ... 80（升序 ✅）、search(50)=true / search(99)=false ✅、有序插入 1 万节点树高 10000（退化复现；平衡树应 ≈13）✅。