树与森林

2026 大纲 四（三）1 树的存储结构、（三）3 树和森林的遍历 · 本篇负责三种存储结构与树 / 森林各自的遍历（森林与二叉树的转换、遍历对应关系的推导见《转换》）。

一般树的麻烦：指针域开几个都不对

二叉树有一个隐藏的便利——每个结点最多两个孩子，所以可以用固定大小的结点（lchild、rchild）表示。一般树没有这个便利：结点的度可能是 1、2、3 甚至几十。

于是存储上立刻两难：

按最大度 $k$ 开 $k$ 个指针——大量结点的度远小于 $k$ ，空指针泛滥；
按每个结点的实际度开——结点大小不统一，无法用数组，指针运算全失效。

下面三种存储方式，就是对这个两难的三种不同取舍。它们的分歧只有一条：存哪个方向的边。

// ① 双亲表示法：只存向上的一条边
typedef struct { ElemType data; int parent; } PTNode;   // 根的 parent = -1

// ② 孩子表示法（孩子链表）：每个结点挂一条孩子单链表
typedef struct ChildNode { int childIdx; struct ChildNode *next; } ChildNode;
typedef struct { ElemType data; ChildNode *firstChild; } CTBox;

// ③ 孩子兄弟表示法（又称二叉链表表示法）：固定两个指针
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild;   // 第一个孩子
    struct CSNode *nextsibling;  // 右兄弟（同一双亲下的下一个孩子）
} CSNode, *CSTree;

选型的判据只看主要操作是往上走还是往下走：查双亲、判连通 → 双亲表示法；展开子树 → 孩子表示法；要复用二叉树的算法 → 孩子兄弟表示法。

双亲表示法：只存向上的边

用一维数组存所有结点，每个结点带一个 parent 字段指向双亲在数组中的下标。

        A                下标 | data | parent
      / | \               0  |  A   |  -1
     B  C  D              1  |  B   |   0
    / \    |              2  |  C   |   0
   E   F   G              3  |  D   |   0
                          4  |  E   |   1
                          5  |  F   |   1
                          6  |  G   |   3

这种结构的取向非常明确：它利用"除根之外每个结点只有唯一双亲"这条性质，把每个结点的存储压缩成一个整数，代价是彻底放弃向下的可达性。 找双亲 $O (1)$ 、沿 parent 找根 $O (h)$ 、判断两结点是否同属一棵树 $O (h)$ （各自找根比较）；但找孩子、找兄弟都要扫全表， $O (n)$ 。

并查集是它的典型应用——并查集的两个核心操作恰好是"沿双亲找根"和"把一个根挂到另一个根下"，全是向上操作，一个 parent[] 数组就够。这不是巧合，而是先有需求、后选结构。

一个实现细节：根的 parent 有两种约定，一是置 $- 1$ ，二是指向自己。后者的好处是找根的循环可以写成 while (parent[x] != x) x = parent[x];，不用额外判负。做题时看清题面给的约定。

孩子表示法：只存向下的边

最直接的想法是让每个结点带 $k$ 个指针域（ $k$ = 树的度），这叫多重链表。它的浪费有精确公式： $n$ 个结点共 $n k$ 个指针域，其中非空的与树中的边一一对应共 $n - 1$ 个，故

空链域数 = n k - (n - 1) = n (k - 1) + 1

空链域占全部指针域的比例约为 $\frac{k - 1}{k}$ —— $k = 3$ 时约 67%， $k = 10$ 时约 90%。比例只由 $k$ 决定，与结点数几乎无关，所以多重链表基本不用。

实际用的是孩子链表：把每个结点的孩子看成一个线性表，用单链表串起来； $n$ 个头指针再组成一个顺序表便于随机访问。

下标  data   孩子链表
 0    A   →  [1] → [2] → [3] → ∧
 1    B   →  [4] → [5] → ∧
 2    C   →  ∧
 3    D   →  [6] → ∧

链表结点总数恰为边数 $n - 1$ ，没有任何空链域浪费（每个链表结点都对应一条真实的边）。找孩子 $O (度)$ 、找双亲 $O (n)$ （没有反向指针，只能扫描所有孩子链表）。适合目录展开这类自上而下为主的场景。

常见折中——孩子双亲表示法：在 CTBox 里再加一个 parent 字段，找双亲 $O (1)$ 、找孩子 $O (度)$ ，只多一个整数域。

孩子兄弟表示法：把"多个孩子"改写成一条链

每个结点只用两个指针——第一个孩子（firstchild）和右兄弟（nextsibling）。

一般树的困难在于"孩子有多少个不知道"。孩子兄弟法把这件事改写成一条链：一个结点的全部孩子被串成一条以 firstchild 为表头、以 nextsibling 为链的单链表；于是每个结点只需两个指针。

原一般树                 孩子兄弟表示法（firstchild 向下、nextsibling 向右）

      A                      A
    / | \                    │
   B  C  D                   B ──→ C ──→ D
  / \    |                   │           │
 E   F   G                   E ──→ F     G

  竖线 │ 是 firstchild（指向第一个孩子）
  箭头 ──→ 是 nextsibling（指向右兄弟）

关键洞察：把 firstchild 当作二叉树的左指针、nextsibling 当作右指针，整个结构在内存里与一棵二叉链表一模一样。

孩子兄弟表示法把一般树映射成了一棵二叉树。 这就是"树 / 森林 ↔ 二叉树"转换成立的全部理由——它不是一个"技巧"，而是同一份存储的两种读法。

由于每个结点 2 个指针域、非空的仍是 $n - 1$ 个（对应树中的 $n - 1$ 条边，只是这些边有的表示父子、有的表示兄弟），空链域为 $n + 1$ ，与二叉链表完全一致。

找第一个孩子 $O (1)$ 、找右兄弟 $O (1)$ 、找第 $i$ 个孩子 $O (i)$ （先到 firstchild 再沿 nextsibling 走 $i - 1$ 步）；找双亲不方便，须从根查找或另加 parent 域。

这是应用最广的一种一般树表示法，原因就是它能把一般树的操作全部转成二叉树的操作。转换规则见树与森林和二叉树的转换。

计数题的共同起点： $n =$ 度之和 $+ 1$

这一节的题目大多不问存储结构，而问计数。这类题的出发点是同一条恒等式：

n = \sum_{v} d (v) + 1

证明是边数双计数：树中每条边恰好由一个结点"射出"（从双亲指向孩子），所以边数 $= \sum_{v} d (v)$ ；另一方面除根之外每个结点恰有一条边"射入"，所以边数 $= n - 1$ 。两式相等即得。

把它套到"给定各度结点个数、求叶结点数"上就是一步的事：总度数就是边数，边数加 1 就是总结点数，再减去已知的各度结点数，剩下的就是叶子。

由这条恒等式还能顺出几个直接可用的结论：

森林的棵数 $m = N - E$ （ $N$ 结点总数、 $E$ 边总数）。因为第 $k$ 棵树有 $n_{k}$ 个结点、 $n_{k} - 1$ 条边，求和得 $E = N - m$ 。直观说法是：从 $N$ 个孤立点出发，每加一条边就合并两棵树、让 $m$ 减 1。

高度为 $h$ 的 $m$ 叉树至多 $\frac{m^{h} - 1}{m - 1}$ 个结点（各层上界 $1, m, m^{2}, \dots, m^{h - 1}$ 求和）。反过来， $n$ 个结点的 $m$ 叉树最小高度由 $\frac{m^{h} - 1}{m - 1} \geq n$ 解出。考场上不必解不等式，逐层累加找第一个装得下的 $h$ 更快也更不容易错。

正则 $k$ 叉树（每个非叶结点都恰有 $k$ 个孩子）的两条公式，用同一套"孩子总数 $=$ 非根结点总数"的数法即可推出：

若有 $m$ 个非叶结点，则叶结点数 $L = m (k - 1) + 1$ 。推导：非叶结点共生出 $m k$ 个孩子，而除根之外每个结点恰是某个非叶结点的孩子，故 $m + L - 1 = m k$ 。
若高度为 $h$ ，结点数最多 $\frac{k^{h} - 1}{k - 1}$ （满树），最少 $1 + (h - 1) k$ 。最少的形态是"每层只留 1 个非叶结点"：第 1 层 1 个根，第 2 层到第 $h$ 层各 $k$ 个。注意正则树不允许某个非叶结点只有几个孩子，所以最少不是每层 1 个。

术语辨析：正则 $k$ 叉树只要求每个非叶恰有 $k$ 个孩子；满 $k$ 叉树还额外要求所有叶子在同一层。满一定正则，反之不然。另外，"度为 $m$ 的树"要求至少存在一个度恰为 $m$ 的结点，而" $m$ 叉树"只要求每个结点至多 $m$ 个孩子——求"最少结点数"时这个差别直接改变答案。

树的遍历与森林的遍历

遍历	规则	对应二叉树的遍历
树·先根遍历	先访问根，再依次先根遍历根的每棵子树	先序遍历
树·后根遍历	先依次后根遍历根的每棵子树，再访问根	中序遍历
树·层次遍历	按层从上到下、每层从左到右（用队列实现）	无严格对应
森林·先序遍历	① 访问第一棵树的根 → ② 先序遍历第一棵树的子树森林 → ③ 先序遍历剩余树构成的森林	先序遍历
森林·中序遍历	① 中序遍历第一棵树的子树森林 → ② 访问第一棵树的根 → ③ 中序遍历剩余树构成的森林	中序遍历

森林那两条的三步结构不是随意写的：它精确对应转换后二叉树的"根 / 左子树 / 右子树"——第一棵树的根就是二叉树的根，第一棵树的子树森林转成左子树，剩余树的森林转成右子树。

所以题目要"转换成二叉树后的先序 / 中序序列"时，直接对原树 / 森林做先根 / 后根遍历即可，不必真的把转换图画出来。

为什么树没有"中根遍历"：二叉树的中序之所以能定义，是因为"根"两侧的子树数量固定为 2——"在左子树之后、右子树之前"是一个无歧义的位置。一般树的孩子数不固定，"在第几个孩子之后访问根"完全没有依据：度为 3 的结点可以在第 1 或第 2 个孩子之后访问根，度为 5 的又有 4 个可选位置。不同结点之间无法统一，所以这个次序定义不出来。

为什么森林没有"后序遍历"：森林的两种遍历是从"森林 ↔ 二叉树"的对应关系里继承过来的。若照搬"左、右、根"写成"先遍历子树森林、再遍历剩余森林、最后访问第一棵树的根"，得到的次序里第一棵树的根会排在后面所有树之后——这与"森林中各树有先后次序"严重冲突，没有对应的应用语义，所以不定义。

注意术语：森林的中序遍历在部分材料里也叫"森林的后根遍历"，因为它对每棵树内部执行的正是后根次序。两个名字指同一件事。

遍历序列的逐步求法（想核对序列怎么写出来就展开）

      A
    / | \
   B  C  D
  / \    |
 E   F   G

先根遍历：A B E F C D G 推导：访问 A → 先根遍历子树 B（访问 B → 子树 E → 子树 F）→ 先根遍历子树 C → 先根遍历子树 D（访问 D → 子树 G）
后根遍历：E F B C G D A 推导：后根遍历子树 B（E → F → B）→ 后根遍历子树 C（C）→ 后根遍历子树 D（G → D）→ 访问 A
层次遍历：A B C D E F G

森林的例子：

森林 F = { T1, T2, T3 }

   T1         T2        T3
    A          E         G
   / \         |        / \
  B   C        F       H   I
      |
      D

先序遍历森林：访问 A → 先序遍历 A 的子树森林 ${B, C}$ （B → C → D）→ 先序遍历剩余森林 ${T_{2}, T_{3}}$ （E → F → G → H → I）结果：A B C D E F G H I
中序遍历森林：中序遍历 A 的子树森林（B → D → C）→ 访问 A → 中序遍历剩余森林（F → E → H → I → G）结果：B D C A F E H I G

逐层核对第二条： ${B, C}$ 的中序 = 中序遍历 B 的子树森林（空）→ 访问 B → 中序遍历剩余森林 ${C}$ ； ${C}$ 的中序 = 中序遍历 C 的子树森林（ ${D}$ → 得 D）→ 访问 C。故 ${B, C}$ 的中序为 B D C ✓

考点速记

三条会被反复调用的结论：

三种存储结构一句话：双亲表示法只存向上的边、孩子表示法只存向下的边、孩子兄弟表示法把"多个孩子"改写成"长子 + 兄弟链"；选哪种只看主要操作往上走还是往下走。
孩子兄弟表示法等价于一棵二叉链表，firstchild / nextsibling 就是左右指针——这是树 / 森林 ↔ 二叉树转换成立的根据。
一般树没有中根遍历、森林没有后序遍历，原因都是"这个次序在定义上无法统一"，不是遗漏。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。有一点值得先说：这一节的真题几乎不问三种存储结构本身，问的是计数——所以复习重心应该放在上面那条恒等式和由它导出的公式上。

给各度结点的个数，求叶结点数。 例如"度为 4 的树中有 20 个度 4、10 个度 3、1 个度 2、10 个度 1 的结点，求叶结点数"。做法固定两步：先算总度数（ $=$ 边数）， $20 \times 4 + 10 \times 3 + 1 \times 2 + 10 \times 1 = 122$ ；再用 $n =$ 边数 $+ 1$ ， $122 = (41 + n_{0}) - 1$ ，得 $n_{0} = 82$ 。
给森林的边数与结点数，求树的棵数。 直接套 $m = N - E$ 。
给 $m$ 叉树的结点数，求最小高度。 逐层累加满 $m$ 叉树的容量，找第一个 $\geq n$ 的高度。例如 244 个结点的三叉树：高度 5 只能装 121 个、高度 6 能装 364 个，所以至少 6。
正则 $k$ 叉树的推导题（大题）。 两问： $m$ 个非叶结点对应多少叶子（ $L = m (k - 1) + 1$ ）、高度 $h$ 时结点数的最多与最少（ $\frac{k^{h} - 1}{k - 1}$ 与 $1 + (h - 1) k$ ）。这是一道要求写推导过程的题，所以"孩子总数 $=$ 非根结点总数"这句话本身要能写出来。

易错：把总度数直接当成总结点数。 总度数等于边数，还要加 1 才是结点数。

易错：正则 $k$ 叉树求最少结点数时按"每层 1 个"算。 正则要求非叶结点必须恰有 $k$ 个孩子，所以是"每层只留 1 个非叶"，第 2 层起每层都有 $k$ 个结点。

易错：混淆"度为 $m$ 的树"与" $m$ 叉树"、"正则 $k$ 叉树"与"满 $k$ 叉树"。 前者要求存在度为 $m$ 的结点，后者要求所有叶子同层。

易错：以为森林也有后序遍历、树也有中根遍历。 这两个次序定义不出来。

教材出处

树的三种存储结构总述、双亲表示法的结点形式与"求结点的双亲十分方便，也很容易求树的根，但求结点的孩子时需要遍历整个结构"、孩子表示法的两种结点格式，以及"在一棵有 $n$ 个结点度为 $k$ 的树中必有 $n (k - 1) + 1$ 个空链域"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p133（5.6.1 节）
孩子链表与带双亲的孩子链表；孩子兄弟法（"又称二叉树表示法，或二叉链表表示法"）的结点形式、CSNode 类型定义、"若要访问结点 $x$ 的第 $i$ 个孩子，则只要先从 firstchild 域找到第 1 个孩子结点，然后沿着孩子结点的 nextsibling 域连续走 $i - 1$ 步"，以及"这种存储结构的优点是它和二叉树的二叉链表表示完全一样，便于将一般的树结构转换为二叉树进行处理"：印刷 p134
树的先根遍历与后根遍历的定义，以及教材示例树的先根序列 RADEBCFGHK 与后根序列 DEABGHKFCR；"按照森林和树相互递归的定义，可以推出森林的两种遍历方法：先序遍历和中序遍历"：印刷 p135（5.6.3 节）
森林的先序遍历与中序遍历的三步规则，教材示例森林的先序序列 ABCDEFGHIJ 与中序序列 BCDAFEHJIG，以及"当以二叉链表做树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现"：印刷 p136

真题练习

2026Q42分 2022Q42分 2021Q42分 2020Q4210分 2017Q4115分 2016Q52分 2016Q428分 2014Q52分 2014Q4113分 2010Q52分 2009Q62分

树与森林

一般树的麻烦：指针域开几个都不对

双亲表示法：只存向上的边

孩子表示法：只存向下的边

孩子兄弟表示法：把"多个孩子"改写成一条链

计数题的共同起点： $n =$ 度之和 $+ 1$

树的遍历与森林的遍历

考点速记

相关知识

相关文章

真题练习

相关真题（11题）

树与森林 ​

一般树的麻烦：指针域开几个都不对 ​

双亲表示法：只存向上的边 ​

孩子表示法：只存向下的边 ​

孩子兄弟表示法：把"多个孩子"改写成一条链 ​

计数题的共同起点：n= 度之和 + 1 ​

树的遍历与森林的遍历 ​

考点速记 ​

相关知识 ​

相关文章

真题练习 ​

相关真题（11题）

树与森林

一般树的麻烦：指针域开几个都不对

双亲表示法：只存向上的边

孩子表示法：只存向下的边

孩子兄弟表示法：把"多个孩子"改写成一条链

计数题的共同起点： $n =$ 度之和 $+ 1$

树的遍历与森林的遍历

考点速记

相关知识

真题练习