二叉树

二叉树把"比较"变成"二分"，让查找、插入、删除都沿着树的高度走，达到 O(log n)。它解决的痛点：线性结构里找一个元素最坏要遍历全部；树结构把数据按大小或层级组织，每走一步排除一半可能。设想在 100 万个有序数据里找目标：顺序查找平均 50 万步，而一棵平衡二叉树只需约 20 步（log₂ 100 万 ≈ 20）。堆、平衡树、B+ 树、Trie 都是二叉树的变体，理解二叉树是理解所有树形结构的地基。

提示

二叉树的一切性质都从"每个节点最多两个孩子"推出：深度为 h 的树最多有 2^h-1 个节点；n 个节点的树高度至少为 ⌈log₂(n+1)⌉。高度决定操作代价，所以树的优化主线永远是"压低高度"。

基本概念

二叉树是每个节点最多两个子树的树结构，三个术语决定了树的样子：

术语	定义	例子
根节点	没有父节点的节点	家族谱系的开山鼻祖
叶子节点	没有子节点的节点	谱系里没有后代的人
深度/高度	根到节点的边数 / 树的最大深度	3 层树高度为 2

两种特殊形态：

• 满二叉树：每层都填满，节点数恰好 2^h-1，是"最省高度"的形态
• 完全二叉树：除最后一层外都填满，最后一层从左往右连续——这个"从左往右"的性质让它可以不用指针、直接用数组存储（下标 i 的节点，左孩子 2i+1，右孩子 2i+2），堆就是用数组存完全二叉树的典型。

遍历方式

遍历是处理树的基本动作，按访问根的时机分为三种深度优先遍历，加上一种广度优先遍历：

方式	访问顺序	典型用途
前序遍历	根 → 左 → 右	复制树、序列化
中序遍历	左 → 根 → 右	二叉搜索树升序输出
后序遍历	左 → 右 → 根	计算子树属性（如树高）
层序遍历	逐层从左到右	最短路径类问题（BFS）

以一棵 1(左:2, 右:3) 的小树为例，三种深度优先的结果：前序 1 2 3，中序 2 1 3，后序 2 3 1——中序遍历对二叉搜索树的特殊意义在于它会输出有序序列。

递归实现最直观，迭代版用显式栈避免递归深度过深：

递归遍历

void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);  // 访问根
    preorder(root.left);           // 左子树
    preorder(root.right);          // 右子树
}

迭代遍历（前序）

void preorder(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

递归与迭代怎么选

递归栈深度等于树高，树退化为链表时（深度 n）会栈溢出；迭代版用显式栈可控。算法题两种都要会，工程代码更倾向迭代；层序遍历用队列，每轮处理一层节点，天然适合 BFS 类问题。

二叉搜索树

二叉搜索树（BST）在二叉树基础上加一条约束：左子树所有节点 < 根 < 右子树所有节点。查找时从根出发，目标值小于当前节点走左子树，大于走右子树，每步排除一半：

// 二叉搜索树查找：每层只走一个方向，代价 = 树高
TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}

插入与查找同路：从根往下找空位，新节点挂在叶子位置。删除分三种情况：

情况	处理
叶子节点	直接摘除
只有一个孩子	用孩子顶替自己
有两个孩子	用中序后继（右子树最左节点）顶替自己

退化问题

BST 的 O(log n) 建立在不退化的前提下。按有序序列插入（1,2,3,4,5），树会退化成一条链表，查找回到 O(n)——这正是"二叉树"和"二叉搜索树"名字里都带"搜索"的代价。解决方式是让树保持平衡。

平衡树

平衡树解决"退化"问题：在插入删除后自动调整形状，让树高始终保持在 O(log n)。

类型	平衡策略	代价
AVL 树	严格保证左右子树高度差 ≤ 1，失衡时旋转	平衡最严，但旋转频繁
红黑树	放宽为"最长路径 ≤ 2 倍最短路径"	平衡稍松，但插入删除的旋转更少

AVL 用四种旋转（左旋、右旋、左右、右左）恢复平衡；红黑树用颜色约束（根黑、红节点不能有红孩子、每条路径黑节点数相同）近似平衡。两者都保证 O(log n)，红黑树因插入删除的调整成本更低成为工程首选——Java 的 TreeMap、HashMap 的树化兜底都用红黑树。

应用形态

二叉树的知识点在工程中几乎都以变体形态出现：

变体	加在二叉树上的约束	典型应用
堆	父节点大于（大顶堆）或小于（小顶堆）所有子节点	优先队列、Top-K 问题
B+ 树	多叉 + 叶子链表 + 非叶子只存索引	数据库 索引 的默认结构
Trie	按字符分叉的多叉树	前缀匹配、自动补全
表达式树	叶子是操作数，内部节点是运算符	表达式求值、编译原理 的语法树

表达式树是最直观的"树即语义"的例子：表达式 a + b * c 中，乘号节点挂在加号的右子树里，嵌套结构直接反映运算优先级——先算 b * c 再加 a。编译器解析源码后构建的语法树正是这种结构，树建好后就不再需要看原始文本。

B+ 树与数据库的关联最直接：索引树的高度决定了磁盘 IO 次数，B+ 树用"多叉压低高度 + 叶子串成链表支持范围扫描"两个设计，让千万级数据的索引树高度只有 3-4 层，详见 索引。

与哈希表的取舍

维度	二叉树（平衡）	哈希表
单点查找	O(log n) 稳定	O(1) 平均，最坏 O(n)
有序遍历	✅ 中序遍历即有序	❌ 完全无序
范围查询	✅ 天然支持	❌ 不支持
最值	O(log n)	O(n) 扫描

树赢在有序性，哈希赢在速度：只需要"按键取value"，选哈希表；需要"按顺序取"或"取区间"，必须选树。复杂度总览见 数据结构。