🌳 二叉树

init

动手试试：插入几个值。然后逐个试试各种遍历——前序、中序、后序、层序——看树下方的访问顺序依次亮起来。

为什么它重要

树是分层数据的天然结构：文件系统、HTML 文档、组织架构图、决策树。二叉树是二叉搜索树、堆以及表达式解析的根基。

核心思想

想象一棵家谱树，只不过每个人最多有两个孩子（左和右）。从单独一位根祖先开始。

这就是二叉树。 每个节点最多有两个孩子。

树解锁了组织数据的新方式：

• 层级：天然适合表达父子关系
• 递归：每一棵子树本身也是一棵树——问题能漂亮地分解
• 多条路径：不像线性结构，树会分叉

不同的遍历以不同的顺序访问节点：

• 前序：先处理节点，再处理孩子（序列化）
• 中序：左孩子、节点、右孩子（在 BST 中即为有序顺序）
• 后序：先处理孩子，再处理节点（删除）
• 层序：借助队列逐层处理（BFS）

要点回顾

• 每个节点最多有 2 个孩子（左和右）
• 高度决定效率——平衡时是 O(log n)，不平衡时可能退化为 O(n)
• 四种遍历顺序：前序、中序、后序、层序
• 二叉搜索树、堆、表达式树的根基

再深入一些

完全二叉树会先填满每一层再开始下一层（最后一层可以不填满）。满二叉树中每个节点要么有 0 个孩子，要么有 2 个孩子。完美二叉树则既完全又满。这些区分对堆的实现（要求完全）和树的平衡很重要。

"第 k 层最多 2ᵏ 个节点"这个公式可由归纳法导出：第 0 层只有一个节点（根）；每一层最多是上一层的两倍。把从第 0 层到高度 h 的几何级数求和，得到树中最多 2^(h+1) − 1 个节点。反过来推：一棵有 n 个节点的平衡树，其高度为 ⌊log₂ n⌋。

实战中的树

• 文件系统。 目录构成一棵树（有些符号链接会把它变成一个 DAG）。find / 不过就是一次树遍历。
• DOM 树。 每个 HTML 文档都是一棵树；CSS 选择器和 DOM 查询都是遍历套路。getElementById 则是在其上叠加的一层 哈希表，把查找变成 O(1)。
• 图形与机器人中的场景图。 机器人的 URDF（统一机器人描述格式）是一棵由关节连接各连杆的树；计算一只手在世界坐标系下的位姿，就是一连串从叶子走到根的矩阵乘法。
• 八叉树与 KD 树。 这些空间细分树支撑着碰撞检测、点云最近邻搜索（每个 SLAM 系统都在用）以及光线追踪。
• 表达式树。 每个编译器都把源代码变成一棵 AST——一棵以运算符为内部节点、以操作数为叶子的树。遍历顺序选定了你的求值策略。

数学细节

树的性质

第 k 层最多节点数 2ᵏ

高度为 h 的树最多节点数 2ʰ⁺¹ − 1

n 个节点时的最小高度 ⌊log₂ n⌋

最大高度（退化情形） n − 1

遍历时间

O(n) —— 每个节点恰好被访问一次

空间

递归遍历 调用栈上 O(h)

迭代式（BFS） O(w)，其中 w 是最宽那一层的宽度

实现

二叉树节点

struct TreeNode<T> {
    data: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

// In-order traversal (recursive)
fn inorder(node: Option<&Box<TreeNode<T>>>) {
    if let Some(n) = node {
        inorder(n.left.as_ref());
        process(n.data);
        inorder(n.right.as_ref());
    }
}

遍历顺序

• 前序：节点 -> 左 -> 右
• 中序：左 -> 节点 -> 右
• 后序：左 -> 右 -> 节点
• 层序：借助队列的 BFS

练习

三道题目，每道传授一种不同的递归形状：

• 最大深度 —— 简单 · 朴素的两行递归（1 + max(left, right)）；每场树相关面试的开场热身
• 层序遍历 —— 中等 · 树与队列的相遇；用"先记下当前层大小"的技巧来恢复层次的 BFS
• 二叉树的直径 —— 中等 · "一次递归返回两个值"套路——返回高度，顺带（副作用）记录最优值

→ 浏览全部练习题