你打开公司组织架构图：从 CEO 往下，每一层都是「谁向谁汇报」的关系。把这种层层汇报画出来，就是一棵「树」。这页我们把它拆开看。

中心是树的总称，外围每一支是一个组成要素；从最基础元素，到特殊节点，再到关系。

前面看了树的组成元素，但要严谨回答「什么是一棵树」，得靠递归——翻开一本书的目录：章下面有小节，小节下面还有小节，结构自己套着自己。

链表是线、图是网、树是分支——三者都靠指针串联,但拓扑约束层层递进。

DFS 像在迷宫里只带一根蜡烛：一直往前走，没路了才退回一步换条岔道。

BFS 按层推进，靠队列记住「下一层要访问的节点」。

同一棵树两种遍历的路径差异

同一棵树用递归跑 DFS、用队列跑 BFS，看两种思路在代码里如何落地。

DFS 把『访问当前节点』与『对孩子递归』拆开写；BFS 用 popleft/append 保证先入先出，于是按层处理。

DFS 三种走法的区别，就在于「什么时候访问根节点」。前序遍历最直白：到了某个节点，先办它的事，再走左边，最后走右边。

前序遍历先把根摆出来，再往左、右递归。中序只是把根挪到中间——左、根、右。但这一挪，在二叉搜索树上就变了：所有值会按从小到大自动输出。

中序遍历把根放中间，前序把根放最前面。后序反过来——把根放到最后：左右子树全处理完，才碰根。这种顺序有什么用？最直接的就是释放整棵树。

同一棵树三种遍历的节点输出序列

每个内部节点是一个决策问题

从根节点出发,每个判断节点根据条件分支,叶子节点就是最终决策。

上一张我们用「天气+心情+钱」三个问题把买咖啡分成是和否。但问题是——三个特征先问哪个？为什么「天气」排在最前面？这一步的判断标准，就是决策树的核心。

决策树在二维特征空间中做一次分裂，产生的边界是什么形状？

上一页我们用了买咖啡这样的现成决策树。但现实中,九宫格、华容道、魔方这类问题,摆在你面前的只是一个混乱局面——树在哪里?答案是:树要我们自己造。这叫「隐式搜索」。

回溯算法的精髓：选路→碰壁→退回→再选，反复循环直到找到目标。

用全排列示例展示回溯四要素：终止、剪枝、做选择、撤销。这是 Python 回溯的标准模板。

高亮行对应回溯四步：判定终止（L9）、剪枝跳过（L15）、做选择（L19）、递归（L20）、撤销选择（L21）。这就是决策树的深度优先遍历。

上一节回溯在隐式树上穷举，每层分若干支、层层叠加，听上去很自然。可一旦把分支数和深度乘起来，节点数就开始按指数级飙升——这是个没法忽视的代价。

翻电话簿找'王'姓你不会从头翻到尾——A 到 Z 的顺序让你直接跳到后半。搜索树里的剪枝就是这种'提前跳步'：判断某分支不会产出答案或最优解，就不再向下扩展。

剪枝让我们跳过不该走的分支，但还有一类浪费——同一个子树被反复算。比如递归求每个节点子树大小时，左右子树会被反复访问。记忆化搜索用一个「备忘录」存算过的结果，下次直接抄。

加了一行缓存，时间从指数降到线性——真的就改一行？

• ✓树的本质是递归结构：每棵子树仍是树
• ✓DFS与BFS同为O(n)，但适用场景不同
• ✓前/中/后序决定根节点访问时机
• ✓回溯是带约束的DFS，剪枝与记忆化能提速
• ✓决策树把递归分裂落到特征空间，形成分类边界

先想再看答案。三个问题分别对应回顾、应用与边界，难度递进。