树、生成树与递归结构
图论里有一种结构特别干净：它把所有需要相连的点连起来，却不留下任何绕圈的余地。这就是树。
本章默认讨论有限简单无向图。若一个图既连通又没有回路，我们就称它为树。这个定义很短，但它同时抓住了两件事：连通保证所有顶点属于同一个整体；无回路保证连接没有多余绕路。
树不是因为画得像植物才叫树。它的数学特征是“连通”和“无回路”。根、父节点、子节点这些层级语言要等我们指定一个根以后才出现。
树的定义
一个无向图 是树，意思是 连通且无回路。这里的“回路”指从某个顶点出发，沿不同的边走若干步，又回到原顶点，并且中间没有重复顶点的闭合路径。
这个定义里两个条件都不能少。只有“无回路”不够：两个互不相连的小树放在一起没有回路，但整体不是树，因为它不连通。只有“连通”也不够：三角形连通，却有回路，所以也不是树。
如果一个图没有回路，但不一定连通，它叫森林。森林的每一个连通分量都是一棵树。这个名字很贴切：很多棵互不相连的树放在一起，就是森林。
从最小连接直觉看树
树可以理解为一种“刚好够用”的连接结构。它没有缺边，因为缺边会导致不连通；它也没有多边，因为一旦某些点之间能绕圈，就说明至少有一条边不是维持连通所必需的。
这给出一个很实用的判断直觉：
- 若图断成几块，它还没有连成树。
- 若图里有回路，它已经比树多了连接。
- 若图连通且无回路，它正好是一棵树。
下面的交互让你开关边，观察这些条件怎样同时变化。
例题：判断一个图是不是树
设图 有顶点集 ，边集为
判断 是否为树。
先数顶点和边。这个图有 个顶点和 条边。若它是树，边数应当是顶点数减 ，所以边数没有立刻排除它。
再看连通性。从 可以到 和 ；从 可以到 和 。因此每个顶点都能从 到达，图是连通的。
最后看是否有回路。顶点 都只通过一条边接入其余部分，不可能参与回路；剩下的结构也没有闭合路线。因此图无回路。
图连通且无回路，所以 是一棵树。
只数出边数等于顶点数减 ，还不能单独断定一个图是树。图还必须连通，或者必须无回路。边数条件通常要和另一个结构条件一起使用。
树的等价刻画
树有多个等价刻画。它们看起来是在说不同事情，其实都描述同一种“刚好连接”的状态。
设 是一个有 个顶点的有限简单无向图。下面这些说法等价：
- 连通且无回路。
- 中任意两个不同顶点之间恰好有一条简单路径。
- 连通，并且有 条边。
- 无回路，并且有 条边。
- 在 中删去任意一条边都会使图不连通。
- 在 中加入任意一条原来没有的边都会产生一个回路。
为什么任意两点之间只有一条路径
树中任意两点之间至少有一条路径，因为树连通。关键是“至多一条”。
如果两个顶点之间有两条不同的简单路径，那么从第一条路径走过去，再沿第二条路径回来，就能在图中找到一个回路。树没有回路，所以这种情况不可能发生。于是树中任意两点之间恰好有一条简单路径。
反过来，如果一个图中任意两点之间恰好有一条简单路径，那么它一定连通；若它有回路，回路上任取两个不同顶点，就能沿回路的两个方向得到两条不同路径。这与“恰好一条”矛盾。因此它无回路，也就是树。
为什么树有 条边
树的边数公式很适合用归纳法理解。
当 时，只有一个顶点，没有边，边数是 。
当 时，树至少有一个叶子。删去一个叶子和它唯一相连的边，剩下的图仍然是一棵有 个顶点的树。若较小的树有 条边，那么原树就多一条边，共有
条边。
这个证明也解释了一个重要直觉：树可以从叶子一层一层剥掉，最后剩下一个顶点。反过来，也可以从一个顶点开始，每次加一个新顶点和一条新边，逐步长成一棵树。
证明树的边数公式时，叶子是很自然的归纳入口。很多关于树的证明都会用“删去一个叶子”把问题缩小。
加边成环，删边断开
树中任意两点之间本来就有唯一简单路径。如果在两个不相邻的顶点之间新加一条边，新边加上原来的唯一简单路径，就组成一个回路。
另一方面，树中任意一条边都在维持连通。若删去边 ，从 到 的唯一简单路径被切断，而树中没有第二条绕路，所以图会分成两部分。
这就是树的极小性：它是连通图中不能再删边的结构，也是无回路图中不能再随便加边的结构。
叶子、根树与二叉树
树不是只有“连通无回路”这一种看法。根据使用场景，我们会给树添加更多语言：叶子、根、父子关系、层级、左右子树。它们帮助我们把树用于递归、搜索和数据结构。
叶子和内部顶点
在一棵至少有两个顶点的树中，度数为 的顶点叫叶子。度数大于 的顶点通常叫内部顶点。一个顶点的度，就是与它相连的边数。
每棵有至少两个顶点的有限树至少有两个叶子。一个简洁的理由是：取树中一条最长简单路径。路径的两个端点不能再向外连接新的顶点，否则路径还能延长；它们也不能连回路径中其他顶点，否则会形成回路。因此这两个端点都是叶子。
这个结论很常用。它告诉我们，有限树总有可以剥离的末端，因此很多关于树的证明可以从叶子入手。
根树
给一棵树指定一个特殊顶点作为根，就得到根树。根让原本无方向的树有了层级：离根更近的顶点在上层，离根更远的顶点在下层。
在根树中，若边连接两个相邻层级的顶点，则离根较近的顶点叫父节点，离根较远的顶点叫子节点。一个顶点的深度是它到根的距离，也就是从根到它的唯一路径上的边数。
根树的好处是把“相连”变成“从上到下展开”。目录结构、组织结构、语法分析树、递归调用树，都依赖这种层级视角。
二叉树
二叉树是一种根树，每个节点最多有两个孩子。若区分两个孩子的位置，就可以说左孩子和右孩子；由左孩子开始的子树叫左子树，由右孩子开始的子树叫右子树。
二叉树在计算机科学中很常见，但在本章先抓住一个数学事实：二叉树仍然是树，它没有回路，两个节点之间仍然只有一条简单路径。它多出来的是根和孩子顺序，这些附加结构让递归定义和搜索过程更容易表达。
“每个节点最多两个孩子”不是“每个节点恰好两个孩子”。叶子没有孩子，某些内部节点也可能只有一个孩子。
生成树
设 是一个连通无向图。若 是 的一个子图，满足：
- 包含 的所有顶点；
- 是一棵树；
那么 叫作 的生成树。
“生成”强调顶点没有丢失；“树”强调选出的边连通且无回路。生成树不是另画一批顶点，而是在原图的边中挑出一部分，刚好把所有顶点连成一棵树。
连通图一定有生成树
只要 连通，就能从 中得到生成树。一个直接方法是：如果图中有回路，就从这个回路中删去一条边。删去这条边不会破坏连通性，因为回路上的两个端点之间还有另一条路可走。
不断重复这个操作。有限图的边数每次减少，所以过程会停止。停止时，图仍然连通，但没有回路，于是得到一棵生成树。
从连通图 开始。若它已经没有回路，那么它本身就是一棵生成树。
若存在回路，选回路上的一条边删去。回路其余边仍然提供绕行路线，所以图不会因此断开。
重复删去回路边。因为图是有限的，边数不能无限减少，过程一定停下。
停下时的子图连通且无回路，并且从未删除顶点，所以它包含原图所有顶点，是 的生成树。
带权图中的最小连接直觉
如果每条边有成本、长度或代价，我们常常希望找一棵总权重尽可能小的生成树。这就是最小生成树问题的入口。本课程暂不展开算法细节，但先记住建模含义：它要保留所有顶点，并用尽量低的总代价保持整体连通。
下面的交互让你在带权图中选择边。选边时要同时避免两种错误：还没连到所有顶点，或者已经形成回路。
最小生成树的“最小”不是顶点最少。生成树必须包含所有顶点，所以顶点数固定。真正被比较的是选中边的总权重。
BFS 与 DFS 生成搜索树
搜索算法也会产生树。给一个连通图和一个起点，从起点出发访问所有可达顶点；每当第一次发现一个新顶点，就记录“是谁把它发现的”。这些发现边组成一棵树，叫搜索树。
常见的两种搜索方式是广度优先搜索和深度优先搜索。
广度优先搜索先访问距离起点为 的顶点，再访问距离起点为 的顶点，依此类推。它像水波一样按层扩散，通常用队列记录待处理顶点。
深度优先搜索会沿着一条分支尽量往前走，走不下去再回退。它像沿着一条路探到底，再回到岔路口，通常用递归或栈实现。
下面的动画把同一张图交给两种搜索方式。注意观察：搜索顺序不同，生成的搜索树也可能不同；但只要原图连通，从同一个起点出发最终都会覆盖所有顶点。
搜索树为什么是树
搜索过程中，每个非起点顶点第一次被发现时，只会记录一条发现边，连接它和之前已经访问过的顶点。起点没有父节点。
若共有 个顶点被访问，那么发现边共有 条：每个非起点顶点贡献一条。所有被访问顶点又都能沿父节点一路回到起点，所以发现边构成的子图连通。连通且有 条边，因此它是一棵树。
BFS 和 DFS 的输出不只是“访问顺序”。把每个顶点的第一次来源记录下来，就得到一棵搜索树。这棵树解释了从起点到每个顶点的发现路径。
BFS 和最短边数路径
在无权图中，BFS 搜索树还有一个重要性质：从起点到每个顶点的树上路径长度，等于原图中从起点到该顶点的最少边数。
原因是 BFS 按层推进。一个顶点第一次被发现时，所有更短距离的可能顶点已经处理过；若存在更短路径，它应当更早被发现。因此 BFS 很适合处理“最少经过几条边能到达”的问题。
DFS 不保证这个性质。DFS 可能先沿一条很深的分支走下去，即使图中存在更短路线，也可能稍后才发现。
递归结构中的树
树和递归关系非常近。递归过程把一个对象分解成更小对象；这些分解关系自然形成从根向下展开的树。
例如，计算一个递归定义的值时，最上层问题是根；它调用的较小问题是子节点；无法再分解的情况是叶子，也就是基本情形。
递归定义的树
一棵二叉树可以递归地定义：
- 空结构是一棵二叉树；
- 若 和 是二叉树，再加上一个根节点，并把 和 分别放在根的左右两侧，就得到一棵二叉树。
这个定义不是绕圈。它把复杂对象分解成更小的同类对象，直到遇到空结构或叶子。许多递归证明也按同样方式组织：先证明基本情形，再假设较小子树满足性质，最后证明整棵树满足性质。
递归调用树
递归算法的运行也可以画成树。以斐波那契递归为例：
若直接递归计算 ，根节点是 ；它分成 和 ；这些节点继续分解，直到遇到 和 。整棵调用树显示了计算如何展开，也显示了重复子问题为什么会出现。
递归调用树不一定是原问题的数据结构本身。它描述的是“计算过程怎样分叉”。一个线性递归过程可能产生一条链；一个双分支递归过程可能产生一棵很大的二叉树。
用树做结构归纳
普通数学归纳按整数大小前进；结构归纳按对象的生成方式前进。若一个对象是递归定义的，证明它的性质时常用结构归纳。
例如要证明“每棵非空有限二叉树中，边数等于顶点数减 ”，可以这样做：
基本情形是一棵只有根节点的树。它有 个顶点和 条边，所以边数等于顶点数减 。
归纳假设是：左子树和右子树若非空，都满足边数等于顶点数减 。
组合整棵树时，新根会通过一条边连接每个非空子树的根。顶点数是新根加上各子树顶点数；边数是各子树边数加上这些连接边。
对每个非空子树代入归纳假设后，整棵树的边数正好比顶点数少 。因此性质对递归构造出的所有有限非空二叉树成立。
常见误区与证明习惯
树的概念简单，但很容易在判定时漏条件。下面这些误区需要主动避开。
误区一：看起来分叉就是树
有些图画出来像分叉结构，但如果存在回路，就不是树。也有些图每个局部都像树枝，但整体断成几块，也不是树。
判断树时要回到定义：连通、无回路。若题目给了顶点数和边数，也要确认它们和连通性或无回路条件配合使用。
误区二：根树和树混在一起
无根树没有天然的父节点、子节点和深度。只有选定根以后，这些词才有意义。同一棵树选不同的根，会得到不同的父子关系和不同的深度。
误区三：生成树丢掉了顶点
生成树可以删边，不能删顶点。若子图只覆盖了原图的一部分顶点，它可能是一棵树，但不是原图的生成树。
误区四：DFS 树一定给最短路径
DFS 生成树记录的是深度优先的发现过程，不保证从起点到每个点的路径最短。无权图中想找最少边数路径，通常使用 BFS。
树的题目常常可以从两个方向下手：要么证明“连通且无回路”，要么证明“连通且边数为 ”。选哪一种，取决于题目给了哪些信息。
章末练习
- 一个简单无向图有 个顶点和 条边，并且连通。它一定是树吗？
- 一个简单无向图有 个顶点和 条边，但不连通。它可能是树吗？
- 证明：若 是一棵有至少两个顶点的树，则 至少有两个叶子。
- 在一个连通图中，任选一个回路并删去回路上的一条边。为什么删边后图仍然连通？
- 在一棵根树中，根为 。若顶点 的深度为 ，它到根的唯一路径有多少条边？若换一个根， 的深度一定还等于 吗？
- 解释为什么 BFS 生成树在无权图中能给出从起点到各顶点的最少边数路径，而 DFS 生成树一般不能。
- 设一个带权连通图有 个顶点。任意一棵生成树必须有多少条边？“最小生成树”最小的是边数还是总权重？
- 把“文件夹包含子文件夹，子文件夹继续包含子文件夹或文件”看成递归结构。哪些对象对应树中的内部顶点，哪些对象对应叶子？