树

🔥 高优先级

树和图每年都是必考，这一节每个知识点都十分重要。

树的定义：先抓住结构不变量

一棵非空树有且仅有一个根结点；除根结点外，每个结点有且仅有一个父结点。从无向图角度看，树必须连通且无环，所以含 n 个结点的树恰有 n-1 条边。三句话是同一结构的不同表述：多一条边会成环，少一条边会不连通。

森林是若干棵互不相交的树组成的集合，可以为空，也可以有多个根；树则是只有一个连通分量的非空层次结构。删去一棵树的根及其关联边，剩余各子树组成森林；反过来，给森林增加一个新根并把它连接到各树根，就得到一棵树。

典型错项：把“每个结点都有唯一父结点”判对——根没有父结点；把“有 n-1 条边”单独当作树的充分条件——还必须检查连通（或等价地检查无环）；把空森林误判为一棵树。

树的基本概念

术语与计数口径

默认采用 408 常见的根为第 1 层、高度按结点层数计的口径：结点的深度是根到该结点所含的结点数，结点的高度是该结点到最深叶结点所含的结点数；因此根深度为 1、叶高度为 1。若题目明确按边数计，则两者都比这里少 1，必须先统一口径再代公式。

路径是沿相邻结点依次经过的结点序列，路径长度等于路径上的边数，而不是结点数。根到某结点路径上的上层结点称为它的祖先，下层结点称为相应祖先的子孙；具有同一父结点的结点互为兄弟。结点的度是孩子数，树的度是所有结点度的最大值。森林是零棵或多棵互不相交的树的集合，森林各树根之间原本没有边。

结点属性

• 双亲 （parent）：如果一个结点包含子结点，则该结点被称为其子结点的双亲。
• 兄弟 （sibling）：具有相同双亲结点的结点互称为兄弟结点。
• 孩子 （child）：一个结点直接连接到另一个结点，并且位于较低的层级，则该结点被称为子结点或孩子。

度

树的度 = max(结点度) = 3

• 结点的度 ：结点的孩子数量
• 树的度 ：等于树中所有结点度的最大值
• 分支结点 （非终端结点）：度大于 0 的结点
• 叶子结点 （终端结点）：度等于 0 的结点

深度

• 树的深度 （Depth）：从根结点到最远叶子结点的 结点总数 。
• 结点的深度 ：是指从根结点到该结点的结点总数。

补充

深度定义是从上往下的，高度定义是从下往上的。

按本文“根为第 1 层、高度按结点层数计”的口径，整棵非空树的高度与最大深度数值相同；单个结点的高度和深度通常不同。题目若改用边数口径，必须先统一定义再计算。

高度

• 树的高度 （Height）：从根结点到最远叶子结点的 结点总数 。
• 结点的高度 ：从该结点到其最远叶子结点的 结点总数。

注意

树的高度定义常常有两种方式，这个需要区分一下：

1. 定义一：从某节点到最远叶子节点的 结点总数 。
2. 定义二：从某节点到最远叶子节点的 边数 。

定义一在算法竞赛和教材中更加常用，408 真题也是按照这种方式考查的（2020 年第 3 题），在学习和考试中需要按照按照定义一来记忆。

路径

带权路径长度

树的带权路径长度 = 10 + 6 + 16 + 14 + 33 + 45 + 6 = 130

• 路径 ：在一棵树中，从一个结点到另一个结点所经过的所有结点，被称为这两个结点之间的路径。
• 结点的权 ：每个结点被赋予的一个数值，通常表示该结点的重要性或频率。
• 结点的带权路径长度 ：从根结点到该结点的路径长度与该结点权值的乘积。
• 树的带权路径长度 ：所有叶子结点的带权路径长度之和。

树的数量与高度性质

以下公式默认讨论含 n≥1 个结点的树，根为第 1 层。每条边都恰好对应一个非根结点的父子关系，因此所有结点的度数之和 = 边数 = n-1。

设度为 i 的结点数为 n_i，树的最大度不超过 m。由

[ \sum_{i=0}^{m}n_i=n,\qquad \sum_{i=0}^{m}i n_i=n-1 ]

相减得到叶结点数公式

[ n_0 = 1 + \sum_{i=2}^{m}(i-1)n_i. ]

注意 n_1 的系数为 0，不能把“度为 1 的结点数”直接加进叶数。这个公式按实际结点度计数，不要求每个分支结点都有 m 个孩子。

在每个结点至多有 m 个孩子的树中（m>1），第 i 层结点数上界为 m^{i-1}；高度为 h 的树结点总数上界为

[ 1+m+m^2+\cdots+m^{h-1}=\frac{m^h-1}{m-1}. ]

所以给定 n≥1 个结点时，能达到的最小高度是

[ h_{\min}=\left\lceil \log_m((m-1)n+1) \right\rceil. ]

这是“尽量填满每一层”得到的最小高度，不是任意形状的固定高度；若退化为单链，高度可达 n。边界必须单独处理：空树结点数为 0、高度记为 0，不代入上式；单结点树有 0 条边、度数之和为 0、叶数为 1、高度为 1。

典型错项闭环：n-1 是边数与度数之和，不是叶数；第 i 层的 m^{i-1} 是上界，不保证取到；由结点数求高度时，上式给的是最小高度，不能据此断言树形唯一；题目若把根记为第 0 层，层号与高度公式要同步换口径。

树的存储结构

树的 存储结构 是指在计算机中如何表示和存储树这种数据结构，这里主要了解 双亲表示法 、孩子表示法 和 孩子兄弟表示法 即可。

双亲表示法

双亲表示法 主要是使用一个数组，其中每个结点都有一个指示其双亲结点在数组中位置的索引。

#define MAXSIZE 100
typedef struct {
    int data;         // 结点数据
    int parent;       // 双亲的位置
} PTNode;

typedef struct {
    PTNode nodes[MAXSIZE];  // 结点数组
    int n;                  // 结点数
} PTree;

孩子表示法

孩子表示法 将每个结点的孩子结点排列起来，以单链表作为存储结构。然后再用一个数组与之相配合。

#define MAXSIZE 100

// 孩子结点
typedef struct ChildNode {
    int child;                   // 孩子结点在数组中的位置
    struct ChildNode* next;     // 下一个孩子
} *ChildPtr;

// 表头结构
typedef struct {
    int data;                   // 结点数据
    ChildPtr firstchild;        // 第一个孩子的指针
} CTBox;

typedef struct {
    CTBox nodes[MAXSIZE];       // 结点数组
    int n;                      // 结点数
} CTree;

孩子兄弟表示法

孩子兄弟表示法 是将树转化为 二叉树 的形式来存储。每个结点有两个指针，一个指向它的第一个孩子，另一个指向它的右兄弟。

typedef struct CSNode {
    int data;                     // 结点数据
    struct CSNode* firstchild;   // 第一个孩子
    struct CSNode* rightsib;     // 右兄弟
} CSNode, *CSTree;

森林的基本概念

森林 （Forest）是一组互不相交的树的集合。换句话说，森林由若干棵树组成，每棵树都是一个独立的层次结构，且这些树之间没有连接关系。

• 森林与树的区别 ：

• 一棵树只有一个 根结点 ，而森林可以有多个 根结点 （每棵树一个）。

• 森林可以看作是多个树的并集，树是森林的一个特例（森林中只有一棵树）。

  • 森林的深度 ：森林中所有树的最大 高度 。按本文“根为第 1 层”的口径，它等于最深树从根到最远叶结点所含的结点层数；若题目按边数计，再整体减 1。

树、森林和二叉树的转换

树转化为二叉树

• 若树的根结点有孩子，那么第一个孩子是 二叉树 的左孩子，其他的孩子结点依次作为前一个孩子结点的右孩子。
• 对每个孩子执行上述步骤。

树转化为二叉树

森林转二叉树

• 把森林中的每一棵树转换为 二叉树 。
• 第一棵二叉树不动，从第二棵二叉树开始，依次将后一棵二叉树的根作为前一棵二叉树的右孩子。其结果是一个 二叉树 。

森林转化为二叉树

树和森林的遍历

树的遍历

对于一个给定的树，通常有以下两种遍历方式：

1. 先根遍历 （类似于二叉树的前序遍历）：

• 访问树的根结点。
• 递归地 先根遍历 根的每一棵子树。

2. 后根遍历 （类似于二叉树的后序遍历）：

• 递归地 后根遍历 根的每一棵子树。
• 访问树的根结点。

注意树是没有 中根遍历 的，除非这棵树是二叉树。

• 树结点定义

#define MAXCHILD 20

typedef struct TreeNode {
```c
int value;
int numChildren; // 子结点的数量
struct TreeNode *children[MAXCHILD]; // 子结点指针数组
    } TreeNode;

* 先根遍历
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
    return;
}
printf("%d ", root->value);  // 先访问根结点
// 然后遍历子结点
for (int i = 0; i < root->numChildren; ++i) {
    preOrderTraversal(root->children[i]);
	}
}

 * 后根遍历
void postOrderTraversal(TreeNode* root) {
if (root == NULL) {
    return;
}
// 先遍历子结点
for (int i = 0; i < root->numChildren; ++i) {
    postOrderTraversal(root->children[i]);
}
printf("%d ", root->value);  // 再访问根结点
}

对于 上图 所示的树：其 先根遍历 为 A, B, E, F, C, D, G，后根遍历 为E, F, B, C, G, D, A。

观察可以得到如下结论：

• 树的 先根遍历 和其对应的二叉树的 先序遍历 相同
• 树的 后根遍历 和其对应的二叉树的 中序遍历 相同

森林的遍历

对于一个给定的森林，遍历方式如下：

1. 先根遍历 （与树的先根遍历相似）：依次 先根遍历 森林中的每一棵树。
2. 后根遍历 （与树的后根遍历相似）：依次 后根遍历 森林中的每一棵树。
3. 中根遍历 （普通的树构成的森林是不存在中序遍历的，这里的中序遍历指代的是二叉树森林）：依次 中根遍历 森林中的每一棵二叉树。

对于 上图 所示的森林：其 先根遍历 为 A, B, C, D, E, F, G, H, I，后根遍历 为 B, C, D, A, F, E, H, I, G，中根遍历 为 B, C, D, A, F, E, H, I, G

观察可以得到如下结论：

• 森林的 先根遍历 和其对应的二叉树的 先序遍历 相同
• 森林的 中根遍历 和其对应的二叉树的 中序遍历 相同

存储表示：字段、空间与访问代价

双亲表示法为每个结点保存 parent 下标：找父亲是 O(1)，找全部孩子必须扫描数组为 O(n)；空间为每结点一个数据域和一个下标。孩子表示法用“结点数组 + 孩子链表”（firstchild、next）：找首孩子 O(1)，遍历某结点的 d 个孩子为 O(d)，找父亲仍需扫描或反向索引。孩子兄弟表示法固定两个指针 firstchild/rightsib，把一般树编码成二叉形状，沿右兄弟链找同层后继，空间 O(n)。

不变量是：孩子兄弟表示中，firstchild 只指向第一个孩子，rightsib 只指向同一父亲的下一个孩子；终端结点的 firstchild=NULL，每棵树根的 rightsib=NULL。不要把 rightsib 当作父亲或任意兄弟。

左孩子—右兄弟转换

树转二叉树：结点的第一个孩子接 left，其余孩子依次接在前一个孩子的 right；对每个孩子递归。森林转二叉树时，先分别转换各树，再把后一棵树的根接到前一棵树根的右链上——森林各树根通过右链相连。逆转换必须在根的右链处切断边界，逐棵恢复根；若误把同一棵树内部的兄弟链当森林根链，会丢失层次。

转换保持结点集合不变，时间 O(n)、辅助栈空间 O(h)；空树/空森林返回 NULL，单结点树的左右指针均为空。

5.4-A 题目反哺：从转换结构推出结论（076–083）

把森林转换后的二叉树根记为 r。r 的左子树正是第一棵树的全部孩子及其后代，所以第一棵树结点数=根+左子树结点数=总数-根的右子树结点数；其余森林全部在根的右子树。反过来，沿二叉树根的 right 指针走到 NULL，每遇到一个根链结点就数一棵树，这个根链结点数就是森林树的棵数。

例如 16 结点完全二叉树按顺序编号时，根链为 1→3→7→15，因此是 4 棵树；第一棵树是根1及其左子树共9个结点。这个推导比凭“树高”猜棵数可靠：树高 h 对应森林必有 h 棵不能泛化，只有特定形状才可能碰巧成立。

孩子兄弟表示中，非空森林若有 n 个非终端结点，每个非终端结点的最后一个孩子贡献一个 right=NULL，最后一棵树根再贡献一个，因此 right=NULL 总数为 n+1；空森林为 0。计数对象互不重叠：前 n 个 NULL 分别归属于各非终端结点的最后孩子，额外 1 个只归属于最后一棵树根，不能重复计数。

做题步骤：先标出转换后二叉树的根、left 子树和根的 right 根链；再用总数减右子树得到第一棵树规模，用根链结点数得到森林棵数；涉及 NULL 时按“最后孩子 + 最后一棵树根”分组。边界要单独检查：空森林没有根链且结点数为 0；单树的根 right=NULL，棵数为 1；单结点树同时是第一棵树，规模为 1。

q076 四个断言的判别依据：任意 n 结点二叉树高度不固定（形状可从近似链到近似完全）；完全二叉树无左孩子则无右孩子（层序填充约束）；“树高 h 对应森林必有 h 棵”不能泛化；一般树与转换后二叉树叶数不保持，因为同一父亲的多个孩子会变成一条兄弟 right 链。不要把这些特例当成转换不变量。

5.4-B 题目反哺：孩子兄弟、遍历与重建（084–089；q088 冻结）

先把空指针含义分清：在孩子兄弟表示中，firstchild=NULL（转换后二叉树的 left=NULL）当且仅当原树叶结点；rightsib=NULL（二叉树的 right=NULL）只表示没有右兄弟或已经到达根链末端。因而“左右都空”是更强的交集条件，不能拿它数叶子：已知 6 个空 left 就有 6 个叶，5 个左右都空不能替代叶数。

为什么树后根等于转换后二叉树中序？二叉中序先处理中 left，这会递归处理该结点的全部孩子森林；再访问该结点本身；最后处理中 right，把右兄弟按顺序交给上层递归。因此这是中序对应，不要误写成后序。

已知二叉树中序和后序时，重建方法固定为：后序末尾定根，在中序中定位根并切出左右区间，再对两段递归。例：中序 BDAECF、后序 DBEFCA，末尾得根 A；中序分成 BD | A | ECF，继续递归可得到根链 A→C→F，所以重建后的森林有 3 棵树。答案来自“后序定根 + 中序分割 + 递归”，不能只背结论。

关系翻译表：B.left=原森林第一个孩子，B.right=原森林下一个右兄弟。若 X 是 P 的二叉 right child，则 X 在原森林中是 P 的右兄弟，所以 X 必有左兄弟 P；不要把二叉父子关系当作原树父子关系。若 M=P.left、N=P.right，则 M 是 P 的首孩子、N 是 P 的右兄弟；当 P 是森林某树根时，M 与 N 跨越两棵树，可能无公共祖先（最小反例：两棵单结点树 P、N，P 无孩子则不存在 M；再给 P 一个孩子 M，M 属第一棵树而 N 是第二棵树根）。

边界与做题法：空树/空森林返回 NULL；单结点树的 left/right 均空；无兄弟结点仅有 right=NULL，不因此断言它是叶。做题先标 left 的孩子森林，再沿 right 区分兄弟与根链，最后按“后序末尾定根—中序分割—递归”重建。易错点是把空 right 当叶、把后根对应成后序、把二叉父子当原树父子；q088 缺图，不能补图或猜答案。

5.4-C 题目反哺：有序树重建、森林叶数与深度（090–094；q091 冻结）

可唯一重建的前提。 对孩子顺序固定的有序树，且所有结点标识互异，树的先根序列正好是孩子兄弟二叉树的先序，树的后根序列正好是该二叉树的中序；因此两序列可按“根定位—左右区间递归”唯一重建。前提不能省：一般二叉树若只给先序 AB、后序 BA，B 可以是 A 的左孩子，也可以是右孩子；若标识重复，中序定位根也不唯一，区间切分会产生多种结果。

从序列回到森林的可执行流程。

1. 二叉序列重建：用二叉树重建算法处理先序与中序，先序首项定根，在中序定位根并递归切分左右区间。
2. 沿根的 right 切森林：二叉根的 right 链上的每个结点都是一棵树的根，先断开这些根之间的边。
3. 按 left/right 恢复首孩子/兄弟：每个结点的 left 变为 firstchild，该孩子及其 right 链变为同父亲的孩子序列；原二叉 right 则变为同层 nextsibling。

例：先序 ABDEHCFIMGJKL、中序 DBHEAIMFCGKLJ。重建并沿根链切分后，根链为 A→C→G→J；父子边为 A-B,A-E、B-D、E-H、C-F、F-I,F-M、J-K,J-L。先根/后根校验：森林先根（也即二叉先序）仍为 ABDEHCFIMGJKL，森林后根（也即二叉中序）为 DBHEAIMFCGKLJ，两条序列均闭环。

孩子兄弟森林叶数。 这里 t 代表同层森林链首；递归沿 firstchild 下探、沿 nextsibling 横移，保持“调用返回该链及其子树的叶数”不变量：

边界写作 Leaves(null)=0；非叶分支合并 Leaves(firstchild) 与 Leaves(nextsibling)。

Leaves(t):
    if t == null: return 0
    if t.firstchild == null:
        return 1 + Leaves(t.nextsibling)
    return Leaves(t.firstchild) + Leaves(t.nextsibling)

空森林返回 0，单点树返回 1；每个结点和链边至多访问常数次，时间 O(n)，递归栈为 O(h_cs)，最坏退化链为 O(n)。

孩子兄弟森林深度。 只对单棵树根调用，nextsibling 分支表示同层另一棵树，不能增加深度：

边界写作 Depth(null)=0；

Depth(null) = 0
Depth(t) = max(1 + Depth(t.firstchild), Depth(t.nextsibling))

因此 Depth(t)=max(1+Depth(firstchild),Depth(nextsibling))；空树为 0，单点为 1。正确性来自两种选择：首孩子路径向下增加一层，兄弟路径仍在当前层；每个结点只处理一次，时间 O(n)，栈 O(h_cs)，最坏 O(n)。不要把森林根直接当作一棵树深度的调用入口，否则会把兄弟树混入“单棵树”语义。做题按“序列重建→根链切森林→left/right 复原→先根/后根回放”执行，并逐项检查空指针、单点和重复标识；q091 缺关键图不能猜，不能臆造图形或答案。

树与森林遍历对应关系

树的先根遍历是“访问根，再按孩子从左到右递归”，对应孩子兄弟二叉树的先序；树的后根遍历是“先递归全部孩子，再访问根”，对应二叉树的中序。森林先根遍历对应转换后二叉树先序，森林后根遍历对应二叉树中序；普通树本身没有中根遍历，只有转换后的二叉表示才谈中序。

性质与综合算法闭环

树含 n 个结点时边数为 n−1；根无父亲，终端结点度为 0。递归算法统一采用“空树为基例、对子树求解后合并”的不变量：叶数为左右/孩子计数之和，树高为 1+max(child height)（空树高 0），重建时按根与孩子边界切分。遍历、计数、求高时间均为 O(n)；双亲查询 O(1)，孩子查询依表示法不同为 O(d) 或扫描 O(n)。

易错点：把深度（根到结点）和高度（结点到最深叶）混用；把森林根右链漏掉；逆转换不在根右链处截断；空树、单结点、无孩子结点未单独处理。题目 076–094 可按“表示字段→转换不变量→遍历对应→边界返回”逐项作答；缺少 q088、q091 的源图时只能讲通法，不应臆造图形或答案。