线性结构每个元素只有一个「下家」，但真实世界充满一对多：公司组织架构、文件目录、家谱、DOM 树……本章的主角——树（Tree）——就是描述层级关系的数学结构 🌳。
🌲 树的「黑话」词典
一棵树 = 一个根节点 + 若干互不相交的子树。必背术语速查：
- 根（root）：没有父节点的那个节点 👑；
- 叶（leaf）：没有孩子的节点 🍃；
- 内部节点：有孩子的节点；
- 深度（depth）：从根走到它的距离（根深度为 0）；
- 高度（height）：树中最深叶子的深度——衡量一棵树「有多高」；
- 祖先/后代：沿父指针能走到的所有节点（你的爸爸的爸爸是你的祖先 👴）。
书里有个漂亮的结论：一棵有 n 个节点的树恰好有 n-1 条边（每个节点除了根，都恰好贡献一条来自父节点的边）。
🗂️ 树怎么存进内存？
三种经典方案：
- 父指针数组：每个节点只存「我爸是谁」。找爸爸 O(1)，但找孩子要全表扫描 ❌；
- 孩子链表：每个节点存一个孩子列表（用上一章的链表！积木复用 🧱）；
- 左孩子-右兄弟（first-child / next-sibling）：每个节点两个指针——指向第一个孩子、指向下一个兄弟。任意棵树，都能装进二叉树的形状，这是本章最惊艳的技巧 ✨。
🚶 遍历：把树「串」成一行
- 先序遍历（preorder）：先访问根，再递归遍历各子树 → 适合「目录树打印」（先打目录名，再进子目录）；
- 后序遍历（postorder）：先递归处理所有子树，最后访问根 → 适合「计算目录总大小」（必须先知道每个子目录多大）📁；
- 书里的经典例题：Disk Space 查询——整个文件系统占多少空间？后序遍历，子目录的大小汇总到父目录，一个递归搞定。
🌿 二叉树：树中的特种兵
每个节点最多两个孩子（左、右）——限制更严，用处更大。
两个必背性质：
- 高度 h 的二叉树最多有 2^(h+1) - 1 个节点；
- 反过来，n 个节点的二叉树高度至少为 ⌊log₂ n⌋——「矮」是可以被数学保证的，这句话是第 10 章所有平衡树的伏笔 📌。
四种遍历一次说清（先/中/后说的是根被访问的时机）：
先序：根 → 左 → 右 中序：左 → 根 → 右
后序：左 → 右 → 根 层序：一层一层从左到右
⚠️ 层序遍历是特殊的：它不用递归，用队列（FIFO）——第 5 章的积木又出现了！先/中/后序用栈（递归调用栈）完成。
🎯 本章通关清单
- [ ] 给一棵树，标出每个节点的深度，并算出树的高度
- [ ] 画出「左孩子-右兄弟」表示法的转换结果
- [ ] 对一棵二叉树，手写先序、中序、后序、层序四个序列
- [ ] 解释为什么「算目录总大小」要用后序遍历
树的世界刚打开。下一章给树加一条规则，它就变成查询利器——堆 ⛰️