树、生成树与递归结构

上一章我们已经会问：两个顶点之间有没有路径？整张图是不是连通？现在把条件再收紧一点：如果图是连通的，但任何地方都不能绕一圈回来，它会变成什么样？

答案是树。

树第一次看很像一个普通定义——“连通且无回路”。真正值得花时间的，是这八个字会自动带出一整串结论：两点之间的路径唯一；有 $n$ 个顶点时恰好有 $n-1$ 条边；删一条边就断开，加一条边就成环；一定能找到叶子，把叶子摘掉以后还剩一棵更小的树。

这些结论又解释了树为什么同时出现在网络连接、图搜索和递归程序里。图论把它看成“没有冗余的连接”，算法把它看成“第一次发现顶点留下的骨架”，递归则把它看成“一个对象怎样由更小对象组成”。本章会把这三种视角连起来。

---

从连通且无回路认识树

无回路的无向图叫森林；连通的森林叫树。换句话说，一棵树是连通且无回路的无向图。森林可能由几个连通分量组成，而每个分量本身都是一棵树。

这里最容易漏掉的是：两个条件必须同时成立。

• 两个互不相连的分支都没有回路，但整体不连通，所以它们合起来是森林，不是一棵树。
• 三角形里的任意两点都能互相到达，但三条边围成回路，所以它连通却不是树。
• 单个顶点构成一棵树。它连通，也没有回路，只是边数为 $0$。

树可以理解成“刚好够用”的连接。边再少一点，某些顶点就失去联系；边再多一点，某些顶点之间就出现绕行路线。这不是额外规定，而是定义推出来的结果。

树的六种常用刻画

设 $G$ 是有 $n$ 个顶点的有限简单无向图。下面的说法彼此等价：

1. $G$ 连通且无回路。
2. 任意两个不同顶点之间恰好有一条简单路径。
3. $G$ 连通，并且有 $n-1$ 条边。
4. $G$ 无回路，并且有 $n-1$ 条边。
5. $G$ 连通，而且删去任意一条边都会使图断开。
6. $$ 无回路，而且在任意两个原本不相邻的顶点之间加边都会产生回路。

不用死背这张清单。我们把几条关键推理走一遍，它们就会自然地连起来。

为什么两点之间的路径唯一

树连通，所以任意两个顶点 $u,v$ 之间至少有一条路径。难点在“至多一条”。

假设 $u$ 到 $v$ 有两条不同的简单路径。两条路径从 $u$ 出发后，总会在某处第一次分开，并在后面某处重新会合。沿第一条分支走过去，再沿第二条分支反向回来，就得到一个回路。这和树无回路矛盾。因此两点之间只能有一条简单路径。

反方向也一样有力。如果图中任意两点之间恰好有一条简单路径，那么它当然连通。若图里存在回路，取回路上的两个不同顶点，沿回路顺时针和逆时针各走一次，就得到两条不同的简单路径，又与唯一性矛盾。所以图无回路，因而是一棵树。

这个性质是后面很多证明的发动机。看到“树”以后，你可以放心地说“从 $u$ 到 $v$ 的唯一路径”，不用再为它是否存在、是否还有第二条而额外证明。

加边为什么成环，删边为什么断开

在树中选两个不相邻顶点 $u,v$。它们之间已经有唯一简单路径。现在加入新边 $uv$，新边和原来的路径恰好围成一个回路。

反过来，若删掉树中的边 $uv$，原来从 $u$ 到 $v$ 的唯一路径被截断。要是删边后两点仍然连通，就存在另一条从 $u$ 到 $v$ 的路径；在删边前，这条路径和边 $uv$ 会组成回路。树中没有这样的绕路，所以删边一定使图分成两个连通分量。

交互：四个条件怎样一起变化

下面的工具允许你开关边。先选“不连通”预设，再逐条补边；然后选“树”预设并随便加一条候选边。观察连通性、回路、边数和唯一路径怎样联动。

例题：边数看起来对，够不够

设图 $G$ 的顶点集和边集分别为

$$V=\{a,b,c,d,e\},$$ $$E=\{ab,ac,bd,be\}.$$

判断 $G$ 是否为树。

---

边数、叶子与森林计数

树的边数公式是

$$|E|=|V|-1.$$

这条公式常被当作树的“身份证”。但公式本身并不神秘：树可以从末端一层层剥掉，每剥掉一个新顶点，恰好同时剥掉一条边。

为什么有限树一定有叶子

在一棵至少有两个顶点的树里，度为 $1$ 的顶点叫叶子。其余度大于 $1$ 的顶点叫内部顶点。

要证明树至少有两个叶子，可以取一条最长简单路径，记它的两个端点为 $u$ 和 $v$。看端点 $u$：

• 它已经通过一条边接在路径上。
• 若它还连接一个不在路径中的顶点，原路径就能再延长一步，与“最长”矛盾。
• 若它还连接路径中的另一个顶点，就会和路径的一段围成回路，也不可能。

所以 $u$ 的度只能是 $1$。同理，另一个端点 $v$ 也是叶子。于是每棵至少有两个顶点的有限树至少有两个叶子。

用删叶子证明边数公式

我们对顶点数 $n$ 归纳。

当 $n=1$ 时，树只有一个顶点和 $0$ 条边，确有 $0=1-1$。

现在假设每棵有 $n$ 个顶点的树都有 $n-1$ 条边。取一棵有 $n+1$ 个顶点的树 $T$。它有叶子 $v$。删掉 $v$ 和它唯一关联的边后，剩余图仍然连通，也不可能突然产生回路，所以剩余图是一棵有 $$ 个顶点的树。按归纳假设，它有 条边。把 和那条边接回去，边数增加 ，得到

$$|E(T)|=(n-1)+1=n=(n+1)-1.$$

这个证明里最值得记住的不是最后一行计算，而是“删叶子—对小树使用归纳假设—把叶子接回去”的思考方式。以后证明树的性质，先问一句：删掉一个叶子后，题目的结构是否仍然保留？

森林的边数

树的公式还能直接推广到森林。若森林有 $n$ 个顶点、$c$ 个连通分量，第 $i$ 个分量有 $n_i$ 个顶点，那么每个分量是一棵树，有 $n_i-1$ 条边。因此

$$|E|=\sum_{i=1}^{c}(n_i-1) =\sum_{i=1}^{c}n_i-c =n-c.$$

所以森林满足

$$|E|=|V|-c.$$

当 $c=1$ 时，森林连通，公式就退化为树的 $|E|=|V|-1$。这也给了我们一个很实用的动态直觉：从 $n$ 个孤立顶点开始时有 $c=n$；每加入一条连接两个不同分量的边，边数加 $$、分量数减 。要把 个分量合成一个，正好需要 次。

边数条件怎样补上缺失的信息

现在可以把前面的两条边数刻画补严密。

若图无回路，它就是森林。森林有 $n$ 个顶点、$c$ 个分量时有 $n-c$ 条边；如果题目又给出边数为 $n-1$，比较两式便得到 $c=1$，所以图连通，是树。

若图连通，可以从任意顶点开始，每次沿一条边第一次接入一个尚未到达的顶点。除起点外，其余 $n-1$ 个顶点都需要一次这样的首次接入，所以连通图至少有 $n-1$ 条边。如果一个连通图恰有 $n-1$ 条边却还含回路，删去回路上一条边后仍然连通，只剩 $n-2$ 条边，与刚才的下界矛盾。因此它无回路，也是树。

顺便还能得到一个小结论：树的任何连通子图仍是树。子图不可能凭空产生原树中没有的回路；它若又连通，就符合树的定义。

叶子数还能告诉我们什么

设一棵至少有两个顶点的树有 $L$ 个叶子。由握手定理和 $|E|=|V|-1$，

$$\sum_{v\in V}\deg(v)=2|E|=2|V|-2.$$

把叶子的度数 $1$ 单独拆出来并整理，可以得到

$$L=2+\sum_{\deg(v)\ge 2}\bigl(\deg(v)-2\bigr).$$

这条式子把“分叉”与“末端”联系起来：度为 $2$ 的内部顶点只是把一条路延长，不增加右边的和；度为 $3$ 的顶点多贡献一个叶子名额；度数越大的分叉，最终就需要更多叶子把分支收住。它也再次说明 $L\ge 2$。

---

生成树：从复杂网络中抽出骨架

现在回到一般连通图。它可能有很多回路、很多备用路线。我们能不能只保留一部分边，同时不丢任何顶点，并让剩余结构变成树？

可以。这样的子图叫生成树。

设 $G=(V,E)$ 是连通无向图。如果子图 $T=(V,E_T)$ 满足 $E_T\subseteq E$，并且 是一棵树，那么 是 的生成树。这里“生成”强调保留原图的全部顶点；允许删边，不允许漏顶点。

连通图一定存在生成树

有两种构造思路很值得掌握。它们一个从“边太多”出发做减法，一个从“边还没有”出发做加法。

删回路边

从整个连通图 $G$ 开始。如果图中有回路，就选回路上的任意一条边删掉。为什么删完仍然连通？因为这条边的两个端点还能沿回路的其余部分互相到达；原来使用这条边的路线，都可以换成这段绕行路线。

不断重复。图是有限的，每次又确实少一条边，所以过程一定会停止。停止时没有回路，而整个过程中连通性和全部顶点都保留下来，最终得到生成树。

连接不同分量

也可以只保留全部顶点，先不选任何边。此时每个顶点是一棵单点树，整体是一片有 $|V|$ 个分量的森林。

只要森林还没连成一个分量，就利用原图的连通性，找一条连接两个不同分量的原图边，把它加入森林。连接不同分量不会形成回路，因为加边前两个端点之间根本没有路径。每加一条边，分量数减少 $1$。做 $|V|-1$ 次后只剩一个分量，得到生成树。

这两种构造也证明了两条对偶的判断原则：

• 连通图不断删掉“回路中的冗余边”，最终留下树。
• 无回路图不断加入“跨分量的连接边”，最终扩成树。

生成树通常不唯一

只要原图有回路，就能在那个回路里选择不同的边删除，往往得到不同生成树。更准确地说：一个连通图的生成树唯一，当且仅当原图本身就是树。

如果原图是树，它已经只有 $n-1$ 条边，删任何边都会断开，所以唯一生成树就是它自己。如果原图不是树，它含有回路。先取一棵生成树 $T$；回路中至少有一条边 $e$ 不在 $T$ 中。把 $e$ 加入 $T$ 会形成唯一回路，再从这个回路中删掉另一条树边，便得到一棵与 $T$ 不同的生成树。

不连通图怎么办

不连通图没有生成树，因为任何保留全部顶点的子图仍无法跨越原图中本来不存在的连接。不过我们可以在每个连通分量里各取一棵生成树，合起来得到生成森林。

若图有 $n$ 个顶点和 $c$ 个连通分量，那么任何生成森林都有

$$n-c$$

条边。这个数字不依赖具体选了哪一棵树，只取决于顶点数和分量数。

带权图里的选择

如果每条边还带有铺设费用、距离或延迟，生成树解决“保持全部顶点连通”的可行性，最小生成树则在所有生成树中比较总权重：

$$w(T)=\sum_{e\in E(T)}w(e).$$

所有生成树都有同样多的边，都是 $n-1$ 条；“最小”指总权重最小，不是边数更少。下面的交互允许你自己选择带权边。先做出任意生成树，再尝试降低总权重，会比直接背算法更容易理解约束。

---

根树：把无向连接变成层次

一棵无根树没有天然的上、下方向。任选一个顶点 $r$ 作为根以后，树的唯一路径会自动给出层次。

对任意非根顶点 $v$，从根 $r$ 到 $v$ 的唯一路径上，紧挨着 $v$ 且更靠近根的顶点叫 $v$ 的父节点；$v$ 是它的子节点。根到 $v$ 的路径长度叫 $v$ 的深度，记作

$$\operatorname{depth}(v)=d(r,v).$$

根的深度为 $0$。深度相同的顶点处在同一层。一个顶点连同它的全部后代构成以该顶点为根的子树。

同一棵无根树换一个根，边并没有变化，但父子关系、深度、祖先和后代都会变化。所以“顶点 $v$ 的度为 $3$”是无根图本身的事实；“顶点 $v$ 有两个孩子”则依赖根的位置。非根顶点的孩子数通常是它的度减 $1$，因为还有一条边连向父节点；根的孩子数等于根的度。

高度、祖先与后代

若顶点 $u$ 位于根到 $v$ 的唯一路径上，就说 $u$ 是 $v$ 的祖先，$v$ 是 $u$ 的后代。通常把顶点自己也算作自己的祖先和后代；若题目要求“真祖先”，才排除自己。

根树的高度是所有顶点深度的最大值：

$$h(T)=\max_{v\in V(T)}\operatorname{depth}(v).$$

高度看的是最深叶子离根多远。它不是顶点数，也不是叶子数。相同的无根树选不同根，高度可能不同。

二叉树还多了什么结构

二叉树是一种根树，每个顶点最多有两个孩子。如果还区分两个孩子的位置，就有左孩子、右孩子，以及左子树、右子树。这个“左右顺序”是额外结构，不能从无向图的画法随便猜。

“最多两个”不等于“恰好两个”。叶子有零个孩子，有些内部节点只有一个孩子。若每个内部节点都恰好有两个孩子，我们会特别称它为满分支二叉树。后面做结构归纳时，这个区别会直接改变构造规则。

---

遍历与搜索树

遍历一棵根树，就是按某种规则访问全部顶点。树本身没有规定唯一访问顺序；顺序来自你选择的策略，以及同层顶点或兄弟节点之间约定的先后次序。

广度优先：按层访问

广度优先搜索先访问根，再访问深度为 $1$ 的所有顶点，然后访问深度为 $2$ 的所有顶点，依此类推。实现时使用队列：先进入队列的顶点先展开。

如果根是 $r$，它的孩子按从左到右记为 $a,b,c$，那么 $a,b,c$ 会先后入队。处理 $a$ 时把 $a$ 的孩子放到队尾，但它们会排在还未处理的 $b,c$ 后面，因此访问自然按层推进。

深度优先：沿一支走到底

深度优先搜索从根出发，选择一个尚未访问的孩子继续向下；没有孩子可走时退回父节点，再尝试下一条分支。它可以用递归实现，也可以显式使用栈。

对有序二叉树，深度优先又常分成三种顺序：

• 前序：先访问根，再前序遍历左子树，最后前序遍历右子树。
• 中序：先中序遍历左子树，再访问根，最后中序遍历右子树。
• 后序：先后序遍历左子树，再后序遍历右子树，最后访问根。

“前、中、后”说的是根相对两棵子树出现的位置。它们不是三种不同的树，而是同一棵有序二叉树的三种读取方式。对一般根树没有天然的“中序”，因为一个节点可能有三个以上孩子，也没有唯一的“左、右”夹住根。

一般图怎样产生搜索树

对一张可能有回路的连通图，从起点开始做 BFS 或 DFS。每当第一次发现新顶点 $v$ 时，记录把它带进来的那条边，并把发现它的顶点记作父节点。所有这样的“首次发现边”组成搜索树。

为什么它一定是树？

1. 起点没有父边，每个其他顶点恰有一条父边。因此访问 $n$ 个顶点时记录了 $n-1$ 条边。
2. 每个顶点沿父节点不断回退，最终都能回到起点，所以这些边构成的子图连通。
3. 连通且有 $n-1$ 条边，因此它是树；也可以从“每个新顶点只用一条边接到旧结构上”直接看出不会成环。

BFS 搜索树还有距离性质：在无权图中，起点到顶点 $v$ 的树上路径长度等于原图中最少边数距离。因为 BFS 一层一层推进，一个更短的到达方式若存在，必定会让 $v$ 更早被发现。DFS 搜索树不保证最短路；它可能先沿一条很长的分支到达 $v$，后来才看见更短的原图边。

下面的交互固定按字母序检查邻接点。切换 BFS 和 DFS，留意“访问顺序”和“首次发现边”是两份相关但不同的信息。

---

递归数据类型：树为什么总和递归一起出现

递归定义不是一句“对象由对象构成”就结束了。一个完整的递归数据类型通常有两部分：

• 基本情形：先说明哪些最小对象已经属于这个类型。
• 构造情形：说明怎样用已经构造好的较小对象，拼出一个新对象。

最后还隐含一个边界：只有通过这些规则有限次构造出来的对象，才属于这个类型。这个限制排除了没有起点的无限倒推。

用递归规则定义二叉树

为了让基本情形看得见，我们定义一种叶子带标签的满分支二叉树：

• 基本情形：任意一个带标签的叶子是一棵树。
• 构造情形：若 $L$ 和 $R$ 已经是树，取一个新根，把 $L$ 作为左子树、$R$ 作为右子树，就得到一棵新树。

一棵大树的根下面仍是两棵较小的同类树；继续拆下去，最终到达叶子。这个“同一种结构在更小尺度上重复”的特点，正是递归。

函数也沿着构造规则递归

数据怎样构造，函数通常就怎样计算。对上面的二叉树，设 $\operatorname{size}(T)$ 是节点数，$\operatorname{height}(T)$ 是高度，可以递归定义为：

$$\operatorname{size}(\operatorname{leaf}(a))=1,$$ $$\operatorname{size}(\operatorname{node}(L,R)) =1+\operatorname{size}(L)+\operatorname{size}(R),$$ $$\operatorname{height}(\operatorname{leaf}(a))=0,$$ $$\operatorname{height}(\operatorname{node}(L,R)) =1+\max\{\operatorname{height}(L),\operatorname{height}(R)\}.$$

基本情形直接给值；构造情形把大对象的值写成子对象的值。遍历也是同一个模式：处理根，递归处理各子树，再把结果组合起来。调用过程自然会形成一棵树，根是最初问题，内部节点是尚需分解的子问题，叶子是不用继续调用的基本情形。

---

结构归纳：按对象的生成方式证明

普通数学归纳沿整数 $0,1,2,\ldots$ 前进；结构归纳沿递归定义的构造规则前进。它要证明的是：每一个通过这些规则生成的对象都满足性质 $P$。

证明模板与定义一一对应：

1. 对每一种基本情形证明 $P$。
2. 对每一种构造方式，假设所有组成部分都满足 $P$，再证明构造出的新对象也满足 $P$。

第二步里的假设叫结构归纳假设。它不是把待证结论凭空假定为真，而是说：如果较小组成部分已经满足性质，那么这一次合法构造会不会把性质保留下来？

例题：叶子数比内部节点数多一

对上一节递归定义的满分支二叉树，证明

$$L(T)=I(T)+1,$$

其中 $L(T)$ 表示叶子数，$I(T)$ 表示内部节点数。

这份证明之所以自然，是因为它完全顺着对象的定义走：单叶树对应基本情形，左右子树加新根对应唯一构造情形。要是硬按“树有多少个节点”做普通归纳，还得额外处理哪些节点数可能出现、怎样把树拆开，反而绕远。

结构归纳和删叶子归纳有什么区别

两者都在缩小问题，但视角不同。

• 对无根树按顶点数归纳时，我们常从现成的大树删掉一个叶子，再研究较小的树。
• 对递归数据类型做结构归纳时，我们从定义出发，把对象拆成构造它的直接子对象，并对每个子对象使用归纳假设。

有时两种证明都能做。选择标准很实际：如果题目给了清楚的递归构造规则，结构归纳通常最贴合；如果只知道对象是一棵有限无根树，删叶子或删边往往更方便。

写结构归纳时最容易漏的地方

第一，不要漏构造情形。若数据类型允许“一元节点”和“二元节点”两种构造，就要分别说明两种情况都保持性质。

第二，构造器有几个递归参数，通常就有几个归纳假设。二元节点由左右两棵子树组成，证明时需要同时假设左子树和右子树满足性质。

第三，要把待证谓词写清楚。与其模糊地说“对子树成立”，不如先写

$$P(T):\quad L(T)=I(T)+1.$$

这样基本情形要证什么、构造情形能假设什么，都不会混在一起。

---

证明路线与常见误区

树题的难点常常不是计算，而是选对入口。下面这几条路线可以直接放进解题清单。

想证明一个图是树

根据已知条件选择最省力的一组：

• 已知可达性很清楚，就证“连通且无回路”。
• 已知顶点数、边数和连通性，就证“连通且有 $n-1$ 条边”。
• 已知图是逐点生长的，就证每次把一个新顶点用一条边接到旧树上。
• 已知任意两点路线受控，就证“任意两点间恰有一条简单路径”。

想证明一个图不是树

只需打破定义中的一个条件：找出两个不连通的顶点，或者明确指出一个回路。若边数不等于 $n-1$，也可以立刻排除；但边数等于 $n-1$ 时仍需继续检查。

不要把根树语言带回无根树

没有指定根时，不能说谁是父节点、谁是子节点，也不能谈深度。同一棵树换根以后，这些关系会变化。叶子的无根定义是度为 $1$；在根树语境中，“没有孩子的节点”也常被叫叶节点。单顶点树的根没有孩子，但它的无向图度数是 $0$，所以要看题目采用哪种语境。

不要把遍历序列当成生成树

访问序列只是一列顶点，例如 $A,B,D,C$；搜索树还需要记录父边，例如 $AB,BD,AC$。同一个访问顺序未必能唯一还原父子关系。

不要把最小生成树理解成最短路径树

最小生成树让全部树边的总权重尽量小；最短路径树让根到每个顶点的树上距离分别达到原图最短距离。这是两个不同目标。一棵树可能是其中一种，却不是另一种。

---

章末练习

1. 一个简单无向图有 $9$ 个顶点、$8$ 条边，并且连通。它一定是树吗？

显示参考答案

一定是树。连通图有 $n=9$ 个顶点和 $n-1=8$ 条边，符合树的等价刻画。若它含回路，删去回路上一条边后仍连通，就会得到只有 $7$ 条边的九顶点连通图，这不可能。

2. 一个有 $9$ 个顶点、$8$ 条边的图不连通。它一定是森林吗？

显示参考答案

不是，而且它一定含有回路。如果它是森林，森林公式 $|E|=|V|-c$ 会给出 $8=9-c$，从而 $c=1$；但 $c=1$ 表示图连通，与题设矛盾。因此“不连通、九点八边、无回路”不能同时成立，这张图必然不是森林。

3. 证明：树中任意一条边都恰好把顶点集合分成两个非空部分，而且原树中跨越这两个部分的边只有被删掉的那一条。

显示参考答案

删掉树边 $e=uv$ 后图不连通。删一条边最多把一个连通分量分成两个，因此得到两个非空分量，一个含 $u$，一个含 $v$。如果原树还有另一条边跨越这两个部分，那么删掉 $e$ 后仍可借那条边从一部分走到另一部分，与它们是两个连通分量矛盾。因此原树跨越该划分的边只有 $e$。

4. 一片森林有 $20$ 个顶点和 $16$ 条边。它有多少个连通分量？

显示参考答案

森林满足 $|E|=|V|-c$。代入得到 $16=20-c$，所以 $c=4$。这片森林由四棵树组成。

5. 一棵树只有度为 $1$、$2$、$4$ 的顶点，其中有三个度为 $4$ 的顶点。它有多少个叶子？

显示参考答案

使用叶子公式

$$L=2+\sum_{\deg(v)\ge2}(\deg(v)-2).$$

度为 $2$ 的顶点贡献 ，每个度为 的顶点贡献 。所以 。度为 的顶点有多少个不影响答案。

6. 说明为什么一个连通图有唯一生成树，当且仅当它本身是一棵树。

显示参考答案

若原图是树，删去任何边都会断开，因此唯一生成树只能是原图。反过来，若连通图不是树，它含回路。取任意生成树 $T$，回路中总有一条边 $e$ 不在 $T$ 中。将 $e$ 加入 $T$ 会形成一个回路，从该回路删掉另一条属于 $T$ 的边，仍得到生成树，而且新树与 $T$ 不同。因此生成树不唯一。

7. 对一棵根树做 BFS。若顶点 $x$ 在顶点 $y$ 之前被访问，能否推出 $x$ 的深度小于 $y$？

显示参考答案

不能，只能推出 $\operatorname{depth}(x)\le \operatorname{depth}(y)$。BFS 按层访问，但同一层中可以有多个顶点，它们的先后取决于兄弟顺序或邻接表顺序。因此 $x$ 可能只是和 $y$ 同层而较早被访问。

8. 为什么对一般图做 DFS 时，不能把所有实际走过的边都放进搜索树？

显示参考答案

一般图可能有回路，DFS 会检查通向已访问顶点的边，也会在回溯时沿父边返回。若把这些边全部保留，得到的子图可能含回路或重复记录。搜索树只保留每个非起点顶点第一次被发现时的那一条父边，因此恰有 $n-1$ 条边并保持无环。

9. 对递归定义的满分支二叉树，写出“节点总数一定是奇数”的结构归纳证明。

显示参考答案

令 $P(T)$ 表示“$T$ 的节点总数是奇数”。基本情形是一棵单叶树，节点数为 $1$，是奇数。构造情形中，设 $T=\operatorname{node}(L,R)$，并假设 $L,R$ 的节点数都是奇数。整棵树的节点数是 。两个奇数之和是偶数，再加 得奇数，所以构造情形保持性质。由结构归纳，所有按规则生成的满分支二叉树都有奇数个节点。

10. 树一定是二分图吗？请给出一种染色方法。

显示参考答案

一定是。任选一个根，把深度为偶数的顶点染成蓝色，深度为奇数的顶点染成橙色。树中的每条边连接父子两个相邻层级，两个端点深度相差 $1$，所以颜色不同。这给出合法的二染色，也为下一章研究二分图和图着色做好了准备。

---

接下来会用到树的地方

树不是图论里孤立的一章。下一章的几个主题都会把它当作骨架。

二分图方面，刚才的按深度奇偶染色已经证明每棵树都是二分图；做匹配时，树的叶子又常常提供最先处理的受限顶点。平面图方面，一棵连通树只有外部一个面，公式 $|E|=|V|-1$ 会成为理解欧拉公式的起点；一般连通平面图可以先取生成树，再把其余边一条条放回去，观察每次怎样增加一个面。图着色方面，根树的逐层遍历给出一种稳定的处理顺序，而“没有奇回路”会把二染色和二分图连起来。

所以我们这一章真正留下的，不只是几个关于树的公式，而是一套反复使用的办法：从复杂图里抽出生成树，用唯一路径分析连接，用删叶子缩小证明，再沿递归结构把结论从子对象传到整个对象。下一章会把这套办法带进匹配、平面图和着色。