05 树与图 — 层次与网络

李永乐式比喻：

• 树 = 一家公司的组织架构。CEO 下面有 VP，VP 下面有总监。每个员工只有一个直接上级（父节点）。
• 二叉搜索树 = 按字母排序的电话本。每次翻到中间，目标在左半本还是右半本？
• 图 = 地铁线路图。站与站之间有多条线相连，可以从任意站到任意站（多对多）。

---

名词映射

英文	中文	本质	比喻
Tree	树	一对多层次结构	公司架构
Binary Search Tree	二叉搜索树	左 < 父 < 右	翻电话本
Root	根节点	树的起点	CEO
Leaf	叶子节点	无子节点的节点	一线员工
Height	树的高度	根到最远叶子的层数	公司有几层管理
Traversal	遍历	按规则访问每个节点	挨个找所有人谈话
Graph	图	多对多网络结构	地铁线路图
Vertex/Edge	顶点/边	节点/连接	地铁站/铁轨

---

二叉搜索树结构

---

BST 查找流程

---

遍历方式

遍历方式	顺序	输出（上图为例子）	比喻
前序（Pre-order）	根 -> 左 -> 右	50,30,20,15,25,40,70,60,80	先说部门再往下
中序（In-order）	左 -> 根 -> 右	15,20,25,30,40,50,60,70,80	升序排序的结果！
后序（Post-order）	左 -> 右 -> 根	15,25,20,40,30,60,80,70,50	先下属再汇报

---

企业场景

• 数据库索引：MySQL B+ 树 -- 范围查询、排序的基石
• 文件系统：目录结构就是树
• 路由协议：Dijkstra 最短路径算法（图）
• 社交网络：好友关系图、推荐算法

---

AI 协作

AI 生成：
  - BST 的插入/查找/删除（三种情况）-- ~60 行
  - 树的三种遍历（递归 + 迭代）-- ~30 行
  - LeetCode 94 中序、102 层序、98 验证 BST

人类决策：
  - 需要排序的数据 -> 树，只需键值查找 -> 哈希表
  - BST 可能退化为链表 -> 需要平衡树（AVL/红黑树）
  - 图中用 DFS 还是 BFS？路径最短用 BFS，是否存在用 DFS