第四章 树、二叉搜索树与堆

---

1. 为什么树结构重要

当数据关系不再只是前后顺序，而是呈现“一个节点下面挂多个子节点”的层次结构时，线性结构就不够用了。树结构能自然表达：

1. 文件目录。
2. 组织架构。
3. 表达式语法树。
4. 数据库索引。
5. 搜索决策过程。

树之所以在计算机系统里极其重要，是因为它同时兼顾了两点：

1. 能表达层次关系。
2. 能在合适约束下支持高效查找、插入和最值维护。

2. 树的基本术语

在这棵树中：

1. 8 是根节点。
2. 3 和 10 是 8 的子节点。
3. 1、6、14 是叶子节点。
4. 从根到某个节点的边数称为该节点深度。
5. 从某个节点到其最深叶子的最长路径，可用于定义高度。

这些术语不是为了背诵，而是为了后续准确讨论遍历、平衡、堆序性质和搜索路径。

3. 树的遍历：理解递归结构的第一步

3.1 Go 中的二叉树节点定义

3.2 前序与中序遍历

4. 二叉搜索树：利用有序性做查找

4.1 BST 查找与插入

4.2 删除为什么更难

5. BST 为什么会退化

6. 堆：不是有序树，而是“局部有序”的完全二叉树

6.1 堆为什么常用数组表示

7. 用 Go 实现一个最小堆

7.1 为什么堆插入和删除是 O(log n)

8. 树结构之间的分工

9. 本章小结

10. 继续深入