跳转至

树与森林笔记

树的存储结构

树是一种一对多的逻辑结构。要把它存进计算机，必须同时保存两样东西：结点的数据本身和结点之间的父子关系。常用的存储方案有三种：双亲表示法、孩子表示法、孩子兄弟表示法。它们的本质区别只在于——每个结点"额外记录谁"。

双亲表示法

核心思想：树中除根以外的每个结点都恰好有一个双亲，那就让每个结点记下自己双亲的下标即可。

具体做法：用一个一维数组顺序存放全部结点，每个结点附带一个 parent 域（伪指针），记录其双亲结点在数组中的下标；根结点没有双亲，约定把它的 parent 记为 -1。

1786180377967-d08dd680-c761-4884-9780-86aea30164de.png

以上图中 T1 为例：数组下标 0 存根 M（parent = -1），下标 1~3 依次存 P、Q、S（parent 均为 0），下标 4、5 存 N、R（parent 为 1），下标 6、7 存 T、U（parent 为 3）。

存储结构定义（C 语言描述）：

#define MAX_TREE_SIZE 100        // 树中结点数上限

typedef struct {
    ElemType data;               // 数据域
    int parent;                  // 双亲在数组中的下标
} PTNode;

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

操作特性：

  • 找双亲：直接读 parent 域，O(1)，非常高效；沿 parent 链一路向上还能找到根，因此这种结构天然适合并查集。
  • 找孩子：结点里没有孩子信息，只能从头到尾扫描整个数组，看哪些结点的 parent 指向它，O(n)，效率低。
  • 正因为它"认父不认子"，双亲表示法一般只用于需要频繁向上回溯的场合。

删除结点的两种策略（设被删的是叶结点；若非叶，需先递归删掉它的子树）：

策略 做法 时间复杂度 缺点
① 打标记 把 parent 改为 -2（区别于根的 -1），表示该位置已废弃 O(1) 结点被删后仍占着数组空间，造成浪费
② 物理搬移 把数组尾部元素前移填补空缺，并同步修正受影响结点的下标/伪指针 O(n) 需要扫描修正，删除变慢

注意区分：双亲表示法靠 parent 域显式记录父子关系；而二叉树的顺序存储（如完全二叉树的数组表示）是靠下标计算隐含父子关系（结点 i 的左孩子为 2i+1）。一般树的孩子个数不固定，不能直接套用二叉树的顺序存储。

孩子表示法

核心思想：与双亲表示法相反——不记爹，改记娃。把每个结点的所有孩子串成一条单链表，n 个结点就有 n 条孩子链表（叶子对应空链表）；再把所有链表的头指针集中放进一个数组（表头数组），数组每个位置还同时保存结点数据。

链表结点中保存的不是孩子数据本身，而是孩子在表头数组中的下标，外加一个指向下一个孩子的指针。

1786181123176-de7fd9a9-43b3-46f7-adb0-12ef05578c12.png

存储结构定义：

typedef struct CCNode {      // 孩子链表的结点
    int child;               // 孩子在表头数组中的下标
    struct CCNode *next;     // 指向下一个孩子
} CCNode;

typedef struct {
    ElemType data;           // 数据域
    CCNode *firstChild;      // 孩子链表头指针
} TreeNode;

typedef struct {
    TreeNode nodes[MAX_TREE_SIZE];  // 表头数组
    int n;
} CTree;

操作特性：

  • 找孩子：沿该结点的 firstChild 链表走一遍即可，非常方便；
  • 找双亲：结点里没有双亲信息，只能遍历所有链表、检查哪个链表里包含它，O(n)，效率低。

实用技巧：把双亲表示法和孩子表示法拼在一起（结点同时带 parent 域和孩子链表头），找爹找娃都快，代价是多花一点空间。

【对比记忆】该种存储方式可以与图的邻接表存储、散列表的拉链法、基数排序对比记忆

图的邻接表存储 散列表的拉链法 基数排序
image-20230804153532443.png image-20230804153847710.png image-20230804153947514.png

可见，上述四种数据结构/算法的示意图结构是类似的。相应地，对四种数据结构的定义也是类似的，可放在一起学习和记忆。

孩子兄弟表示法（二叉链表 / 二叉树表示法）

核心思想：不再借助数组，而是用二叉链表存储树。每个结点设两个指针：

  • 左指针 → 指向该结点的第一个孩子（firstChild）；
  • 右指针 → 指向该结点的下一个兄弟（nextSibling）。

想枚举某结点的全部孩子：先沿左指针找到老大，再沿老大的右指针依次往后找，直到右指针为空。

1786182126909-c2a59f29-e082-4621-8588-406b0efbaebe.png

存储结构定义：

typedef struct CSNode {
    ElemType data;                          // 数据域
    struct CSNode *firstChild;              // 左指针：第一个孩子
    struct CSNode *nextSibling;             // 右指针：下一个兄弟
} CSNode, *CSTree;

与孩子表示法的联系和区别：二者找孩子的思路一致（先找第一个孩子、再顺藤摸瓜）；区别在于孩子表示法需要"表头结点 + 链表结点"两种结点，而孩子兄弟表示法只用一种结点、两个指针就统一了整棵树。

操作特性：

  • 找孩子容易、找双亲难（与孩子表示法相同）；如需快速回溯双亲，可再增加一个 parent 指针域，构成三叉链表；
  • 最大优点：存储结构与二叉树的二叉链表在物理形式上完全一致，同一棵树可以毫不费力地"解读"成一棵二叉树——这正是下一节"树与二叉树相互转换"的物理基础。

三种存储结构对比

对比项 双亲表示法 孩子表示法 孩子兄弟表示法
额外记录 双亲下标 孩子链表头 第一个孩子 + 下一个兄弟
找双亲 O(1)，极快 需遍历，慢 需遍历，慢
找孩子 需扫描全表，慢 沿链表，快 沿左指针 + 右链，快
存储形式 顺序（数组） 顺序 + 链式 纯链式（二叉链表）
典型用途 并查集等向上回溯场景 需要频繁枚举孩子的场景 树/森林与二叉树的转换

树、森林与二叉树的相互转换

树、森林和二叉树之间存在一一对应关系：任何一棵树（或森林）都能唯一地转成一棵二叉树，反之亦然。这意味着——凡是在树上不好做的事，都可以转成二叉树来做（二叉树的算法体系最成熟），做完再翻译回去。

树 → 二叉树

转换规则（"左孩子右兄弟"）：二叉树结点的左指针指向树中该结点的第一个孩子，右指针指向树中该结点的下一个右兄弟。其实就是把孩子兄弟表示法"换了个读法"。

手工画法三步走（以 T2 为例）：

  1. 断开：对每个结点，只保留它与第一个孩子的连线，其余父子连线全部擦掉；
  2. 连线：把同一层的兄弟结点从左到右用线串起来；
  3. 整形：以树根为轴心，把整幅图顺时针旋转约 45°，让兄弟连线变成"右指针"，即得标准二叉树形态。1786182694158-01d7acd1-67ad-441f-ae4a-88acf4c1592a.png

Note

重要结论：根结点没有兄弟，所以由单棵树转来的二叉树，其根结点必定没有右子树。反过来，一棵二叉树若根结点没有右子树，它才可以还原成"一棵树"。

森林 → 二叉树

森林是若干棵树的集合，转换建立在单棵树转换的基础之上，推荐用虚构根结点法（画图时最不容易错）：

  1. 加虚根：虚构一个根结点 r，把森林中每棵树都当作 r 的子树（于是各棵树的根互为兄弟）；
  2. 转换：对"虚根 + 森林"整体应用上节的左孩子右兄弟规则，画出对应二叉树；
  3. 删虚根：把虚根 r 及与它相连的边擦掉，剩下的就是森林对应的二叉树。

1786189001548-616d0114-35f2-45c3-8066-a2a69492ff66.png

等效的手工画法（不画虚根）：先把森林中每棵树各自转成二叉树（它们的根都没有右子树），然后把第 2 棵树的根接在第 1 棵树的根的右指针上、第 3 棵接在第 2 棵的右指针上……依次串联即可。本质上就是"把各棵树的根视为兄弟"。

逆过程（ 二叉树 → 树/森林 ）：

  • 若二叉树根结点无右子树 → 它对应一棵树：把每个结点的左孩子还原为"第一个孩子"，把沿右指针串起来的一串结点还原为同一双亲的一排兄弟即可；
  • 若二叉树根结点有右子树 → 它对应一个森林：把根结点的右指针断开，右子链上每断开一处就分离出一棵新树，对分离出的每棵二叉树分别还原，直至全部还原完。

Note

一个有用的计数性质：任取森林中的一棵树 T，T 的每个分支结点 p 的最右边那个孩子在二叉树中必无右孩子（它没有右兄弟）；T 的根结点在"T 单独转换出的二叉树"中也无右孩子。所以，若 T 有 n 个分支结点，则 T 对应的二叉树中"无右孩子的结点"恰有 n + 1 个。

推广到整个森林：全部 n 个分支结点各贡献 1 个"最右孩子"，再加上最后一棵树的根（它没有下一棵树可接，右指针为空），因此森林转出的二叉树中无右孩子的结点同样是 n + 1 个。

用本笔记的例子验证：T2 中分支结点为 X、Y、Z（n = 3），对应二叉树中无右孩子的结点是 X、V、T、W，恰为 4 = 3 + 1 ✓。森林 F 中分支结点为 A、B、E、G（n = 4），对应二叉树中无右孩子的结点是 C、D、F、H、G（A 的最右孩子 C、B 的最右孩子 D、E 的最右孩子 F、G 的最右孩子 H，再加上最后一棵树的根 G），恰为 5 = 4 + 1 ✓。

树与森林的遍历

树的遍历

树的孩子个数不固定，没法像二叉树那样把根的访问"夹在两棵子树中间"，所以树没有"中根遍历"，只有两种：

先根遍历：先访问根结点，再从左到右依次先根遍历根的每一棵子树。

后根遍历：先从左到右依次后根遍历根的每一棵子树，最后访问根结点。

以 T2（X(Y(V), Z(U, T), W)）为例：

  • 先根遍历序列：X Y V Z U T W
  • 后根遍历序列：V Y U T Z W X

此外树也可以做层序遍历（借助队列，自上而下、自左而右逐层访问），原理与二叉树层次遍历相同。对 T2 做层次遍历的结果为：X Y Z W V U T。

森林的遍历

森林的遍历是递归定义的（设森林非空）：

先序遍历森林：

  1. 访问第一棵树的根结点；
  2. 先序遍历"第一棵树的根的所有子树"组成的森林；
  3. 先序遍历"去掉第一棵树后剩下的树"组成的森林。

效果上等同于：依次对每棵树做先根遍历。

中序遍历森林：

  1. 中序遍历"第一棵树的根的所有子树"组成的森林；
  2. 访问第一棵树的根结点；
  3. 中序遍历"去掉第一棵树后剩下的树"组成的森林。

效果上等同于：依次对每棵树做后根遍历。

以森林 F（A(B(D), C)、E(F)、G(H)）为例：

  • 先序遍历序列：A B D C E F G H
  • 中序遍历序列：D B C A F E H G

3.3 与二叉树遍历的对应关系

把树/森林先转成二叉树，再对二叉树做遍历，序列之间存在严格的对应：

树 森林 对应二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历(后序遍历) 中序遍历

记忆要点："先对先，后对中"——树的先根/森林的先序 ≡ 二叉树先序；树的后根/森林的中序 ≡ 二叉树中序。

用本笔记的例子验证（见下图）：

  • T2 先根 X Y V Z U T W = 对应二叉树先序 ✓；T2 后根 V Y U T Z W X = 对应二叉树中序 ✓
  • F 先序 A B D C E F G H = 对应二叉树先序 ✓；F 中序 D B C A F E H G = 对应二叉树中序 ✓

1787303628870-5cf08c63-1e66-42e2-9cc4-77830206579d.png

部分教材把森林的中序遍历称作"后序遍历"（因为对每棵树做的是后根遍历）。两种叫法指的是同一个序列——森林的先序、中序序列分别与其对应二叉树的先序、中序序列一致，考试时以题目采用的口径为准。

练习题

  1. 【2009-06】将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中， u 和 v 可能具有的关系是（ ）。

I. 父子关系

II. 兄弟关系

III. u 的父结点与 v 的父结点是兄弟关系

A. 只有II

B. I和II

C. I和III

D. I、II和III

解析

森林转换为二叉树采用“左孩子、右兄弟”规则：

  • 二叉树中的左边 L：对应森林中的第一个孩子。
  • 二叉树中的右边 R：对应森林中的下一个兄弟。

设二叉树中 v 的父结点为 x，题意即路径为 u → x → v。两条边各有左、右两种可能，共有四种情况：

题图

方法一：枚举四种情况

  1. L-L：x 是 u 的孩子，v 是 x 的孩子。
    因此 u 与 v 是祖孙关系，不符合 I～III。
  2. L-R：x 是 u 的第一个孩子，v 是 x 的下一个兄弟。
    所以 x、v 都是 u 的孩子，即 u 与 v 是父子关系。
    I 正确。
  3. R-L：x 是 u 的下一个兄弟，v 是 x 的孩子。
    因此 u 是 v 的父结点 x 的兄弟，二者属于叔侄关系，不符合 I～III。
  4. R-R：x 是 u 的下一个兄弟，v 又是 x 的下一个兄弟。
    所以 u、x、v 是同一组兄弟结点。
    II 正确。

方法二：快速判断

二叉树中从 u 到 v 恰好只有两条边，因此只能出现 L-L、L-R、R-L、R-R 四种情况。它们在森林中分别对应祖孙、父子、叔侄和兄弟关系。

其中没有任何一种情况能使“u 的父结点与 v 的父结点是兄弟关系”，故 III 错误。

因此，本题选择 B．I 和 II。

答案：B

  1. 【2014-05】将森林F转换为对应的二叉树T，F中叶子的个数等于（ ）。

A. T中叶结点的个数

B. T中度为1的结点个数

C. T中左孩子指针为空的结点个数

D. T中右孩子指针为空的结点个数

解析

在“左孩子—右兄弟”表示法中，二叉树结点的左孩子指针指向原森林中该结点的第一个孩子。

因此：

  • 原森林中的结点若有孩子，其左孩子指针一定非空；
  • 原森林中的结点若是叶子，没有任何孩子，其左孩子指针一定为空。

两者一一对应，所以森林叶子数等于对应二叉树中左孩子指针为空的结点数。

右孩子指针反映的是“有没有下一个兄弟”，与是否为叶子无直接对应关系。

答案：C

  1. 【2019-02】若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是（ ）。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层遍历

解析

树的后根遍历规则是：

  1. 从左到右依次遍历根的各棵子树；
  2. 最后访问根。

转换后的二叉树用左指针连接第一个孩子，用右指针连接后续兄弟。

对二叉树进行中序遍历时：

  1. 先沿左指针进入第一个孩子；
  2. 孩子的右兄弟链会在对应子树的遍历过程中依次得到处理；
  3. 所有孩子及其子树处理完成后，才访问当前根。

这与原树“先遍历各子树、后访问根”的后根遍历一致。

一个简单例子：原树根 a 有孩子 b、c。原树后根遍历为 b、c、a。转换后二叉树中 a 的左孩子是 b，b 的右孩子是 c，其中序遍历同样为 b、c、a。

答案：B

  1. 【2020-04】已知森林F和对应的二叉树T，若F的先根遍历序列序是a, b, c, d, e, f，后根遍历序列是b, a, d, f, e, c，则T的后序遍历序列是（ ）。

A. b, a, d, f, e, c

B. b, d, f, e, c, a

C. b, f, e, d, c, a

D. f, e, d, c, b, a

解析

题图

  1. 【2021-04】某森林F对应的二叉树为T，若T的先序遍历序列是a, b, d, c, e, g, f，中序遍历序列是b, d, a, e, g, c, f，则F中树的棵数是（ ）。

A. 1

B. 2

C. 3

D. 4

解析

题图