（a）树
吃透四种遍历、重构与递归套路，边界 case 一次理清
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
（a）树
吃透四种遍历、重构与递归套路，边界 case 一次理清
动机
你维护一个有 100 万条记录的通讯录。用数组存，插入一人要移动大量元素；用链表存，查找一人要遍历到尾。能否兼顾查找效率与动态更新？树正是为解决这一矛盾而诞生的。
总经理是根、部门是中间节点、员工是叶子；上下级汇报关系对应边
应用
前面看了树长什么样、为什么非树不可。这一页反过来：它到底用在哪？你日常用的文件系统、数据库、编辑器，背后都有树的身影。
公司组织、家谱、图书分类这类天然有上下级、包含关系的事，都适合用树建模
有根树
上一页我们认识了树——任意两节点间恰有一条路径的连通图。但树上没有「方向」。实际应用中,我们常需要从某个特定节点出发,往下走、往下查。这就需要给树一个起点。
始祖=根,子孙=后代分支,每个人有唯一父辈,可向上追溯单线祖先
有序树
有序树：定义、要点与典型应用
路径+环路
上一页我们给树加上了「有序」约束。本页回到树作为图本身的结构——拆解两个核心特征：任意两顶点之间路径唯一、整棵树不存在环路。这两条性质恰好是把树和「普通图」划清界限的标准。
任意两站只一条线串起来，没有环线绕回原地
连通+无环
上一节我们看到，环就是绕回起点的路径，树里不允许出现这种东西。再加一条要求：任意两个顶点之间都得有路可走。这两条合起来，就是树的「定义式」。
岛=顶点、桥=边。n 个岛用 n−1 座桥时，每岛可达且无绕回
深度+层次
上一节我们看到，树是连通且无环的图。但光有「形状」还不够——我们还要说清每个节点离根有多远，这就是深度。
楼层号即节点深度，同楼层的房间即同层节点
本节要点
- ✓树是n点n-1边的极简连通图
- ✓连通+无环 ⇔ 树 ⇔ 任意两点路径唯一
- ✓删任一边断连，加任一边成环
- ✓有根树才谈深度，有序树才能唯一编码
课后思考
三道开放题，先独立思考，再对照参考答案理清思路。
参考答案缺连通则退化成森林（不连通），缺无环则路径不唯一。两者共同保证 n 节点恰好 n−1 条边，这是树的本质特征。
参考答案左右子节点天然区分，可引入二叉、满、完全等形态；许多遍历与检索算法只在这种结构下成立。
参考答案森林是多棵有根树的并集，每棵仍是有根树。可把『森林』作为整体概念，仍保留深度、子树等定义。