考研全科复习资料

408

数据结构

DS-04-05 树与森林的存储与转换

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	树的定义与基本术语（度、层次、深度）、二叉树的定义与存储
知识网络定位	本单元是树与二叉树之间的桥梁，解决一般树的存储问题以及树、森林与二叉树的相互转换
考点热度	H级（高频重点）：近5年出现≥4次，森林与二叉树的转换是经典大题考点

二、知识点讲解

2.1 树的存储结构

（1）双亲表示法（顺序存储）

用一组连续空间存储树的每个节点，同时附设一个指示器指示其双亲节点的位置。

typedef struct {
    ElemType data;     // 数据域
    int parent;        // 双亲位置（下标），根节点为 -1
} PTNode;

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

优点：找双亲 $O(1)$ 。缺点：找孩子需要遍历整个数组， $O(n)$ 。

（2）孩子表示法（链表+数组）

每个节点的孩子用单链表链接起来， $n$ 个节点用 $n$ 个头指针组成一个线性表。

typedef struct CTNode {
    int child;              // 孩子节点在数组中的下标
    struct CTNode *next;    // 下一个孩子
} CTNode;

typedef struct {
    ElemType data;
    CTNode *firstchild;     // 第一个孩子链表头
} CTBox;

typedef struct {
    CTBox nodes[MAXSIZE];
    int n, r;               // 节点数、根位置
} CTree;

优点：找孩子方便。缺点：找双亲需要遍历。

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

每个节点包含两个指针：第一个孩子和右兄弟。

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild;  // 第一个孩子
    struct CSNode *nextsibling; // 右兄弟
} CSNode, *CSTree;

核心意义：孩子兄弟表示法是树转换为二叉树的物理基础。该结构本质上就是一棵二叉树——左指针指向第一个孩子，右指针指向下一个兄弟。

2.2 树转换为二叉树（左孩子右兄弟法）

转换规则：

在所有兄弟节点之间加一条连线
对每个节点，只保留它与第一个孩子的连线，删除与其他孩子的连线
以根节点为轴心，将整棵树顺时针旋转一定角度

本质：左孩子右兄弟——每个节点的左孩子是它的第一个孩子，右孩子是它的下一个兄弟。

示例：

【图示说明】原始树：
        A
      / | \
     B  C  D
    / \    |
   E   F   G

转换后的二叉树：
        A
       /
      B
     / \
    E   C
     \   \
      F   D
           \
            G

解释：
- A 的第一个孩子是 B → A 的左孩子为 B
- B 的右兄弟是 C → B 的右孩子为 C
- C 的右兄弟是 D → C 的右孩子为 D
- B 的第一个孩子是 E → B 的左孩子为 E
- E 的右兄弟是 F → E 的右孩子为 F
- D 的第一个孩子是 G → D 的左孩子为 G

2.3 森林转换为二叉树

转换规则：

将森林中的每棵树分别转换为二叉树
第一棵树的根作为转换后二叉树的根
第二棵树作为第一棵树根的右子树，第三棵树作为第二棵树根的右子树，以此类推

本质：森林中各树的根节点视为兄弟关系，用右指针串联。

2.4 二叉树转换为森林

转换规则（逆过程）：

若二叉树非空，则根节点及其左子树构成第一棵树
根的右子树构成第二棵树的二叉树形式，递归转换
重复直到右子树为空

判定：二叉树转换为树（森林中只有一棵树）当且仅当根节点无右子树。

2.5 树与森林的遍历

遍历方式	树	森林	对应二叉树遍历
先根遍历	先访问根，再依次先根遍历各子树	先根遍历第一棵树，再先根遍历剩余森林	先序遍历
后根遍历	先依次后根遍历各子树，再访问根	后根遍历第一棵树，再后根遍历剩余森林	中序遍历

关键结论：

树的先根遍历 = 转换后二叉树的先序遍历
树的后根遍历 = 转换后二叉树的中序遍历
森林的先序遍历 = 转换后二叉树的先序遍历
森林的中序遍历 = 转换后二叉树的中序遍历

2.6 存储方式对比表

存储方式	找双亲	找孩子	找兄弟	空间	适用场景
双亲表示法	$O(1)$	$O(n)$	$O(n)$	$O(n)$	需频繁找双亲（如并查集）
孩子表示法	$O(n)$	$O(1)$	$O(1)$	$O(n+e)$	需频繁找孩子
孩子兄弟表示法	$O(n)$	$O(1)$ （第一个）	$O(1)$	$O(n)$	树与二叉树转换，通用

三、记忆与理解辅助

技巧1：树↔二叉树转换口诀

"左孩子，右兄弟，兄弟连线后旋转"
转换时：左指针 → 第一个孩子，右指针 → 下一个兄弟
任何一棵树（或森林）都可以唯一地转换为二叉树

技巧2：树的遍历与二叉树遍历的对应关系

"先根=先序，后根=中序"
树没有"中根遍历"的概念（因为根不是在中间，而是在第一个孩子和最后一个孩子之间）
森林的先序 = 二叉树先序，森林的中序 = 二叉树中序

技巧3：树转换为二叉树后的特征

转换后的二叉树根节点一定没有右子树（当只转换一棵树时），因为根没有兄弟。森林转换后根有右子树（各树的根是兄弟）。

四、例题与精解

例题1（基础巩固）

题目：将以下树转换为二叉树，写出转换后二叉树的先序和中序序列：

命题意图：考查树到二叉树的转换及遍历序列的求解。

审题分析：按"左孩子右兄弟"规则转换，然后分别求先序和中序。

解题思路：先转换，再遍历。

完整步骤：

Step 1：确定每个节点的第一个孩子和右兄弟：

A：第一个孩子=B，右兄弟=无
B：第一个孩子=E，右兄弟=C
C：第一个孩子=无，右兄弟=D
D：第一个孩子=F，右兄弟=无
E：第一个孩子=无，右兄弟=无
F：第一个孩子=无，右兄弟=无

Step 2：构建二叉树：

A 的左孩子=B，A 的右孩子=无
B 的左孩子=E，B 的右孩子=C
C 的左孩子=无，C 的右孩子=D
D 的左孩子=F，D 的右孩子=无

    A
   /
  B
 / \
E   C
     \
      D
     /
    F

Step 3：先序遍历（根左右）：A → B → E → C → D → F

Step 4：中序遍历（左根右）：E → B → C → F → D → A

验证：树的先根遍历 = 二叉树先序：A, B, E, C, D, F ✓ 树的后根遍历 = 二叉树中序：E, B, C, F, D, A ✓

答案：先序 ABECDF，中序 EBCFDA。

例题2（中等提升）

题目：已知森林的先序遍历序列为 ABCDEFGH，中序遍历序列为 BCDAFEHG，请确定该森林包含几棵树，并画出森林。

命题意图：考查由森林的遍历序列还原森林结构。

审题分析：森林的先序 = 二叉树先序，森林的中序 = 二叉树中序。先还原二叉树，再转回森林。

完整步骤：

Step 1：将先序 ABCDEFGH 和中序 BCDAFEHG 视为二叉树的先序和中序，还原二叉树。

先序首元素 A 是根。在中序中 A 的位置：左边 BCD（左子树4节点），右边 FEHG（右子树4节点）。

Step 2：左子树先序 BCD，中序 BCDA → 根B，B左空，B右子树先序CD中序CDA → 根C，C左空，C右子树D...（递归处理）

实际上在中序BCDA中，B的左边为空，右边为CDA。先序BCD中B之后是CD。

左子树：先序BCD，中序BCD（注意A在中间分隔），左子树中序为BCD（A左边），右子树中序为FEHG（A右边）。

更准确：中序中A左边是BCD，所以左子树4个节点；右边是FEHG，右子树4个节点。先序中A之后的4个BCDE是左子树，后面FGHH...不对，先序是ABCDEFGH，A后面是BCDEFGH共7个，左子树4个=BCDE，右子树3个=FGH。但中序右边是FEHG=4个，不匹配。

重新分析：先序 ABCDEFGH，中序 BCDAFEHG。

中序中A在位置4（0-indexed第3个），左边BCD=3个节点，右边FEHG=4个节点。先序中A之后3个=BCD是左子树，再后面4个=EFGH是右子树。

左子树：先序 BCD，中序 BCD

B是根，中序中B左边为空，右边CD=2个
B无左子，右子树先序CD，中序CD
- C是根，中序中C左边为空，右边D=1个
- C无左子，右子=D

左子树结构：B→C→D（右斜树）

右子树：先序 EFGH，中序 FEHG

E是根，中序中E左边F=1个，右边HG=2个
E左子=F，右子树先序GH，中序HG
- G是根，中序中G左边H=1个，右边空
- G左子=H，无右子

Step 3：二叉树结构：

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

Step 4：二叉树转森林——根A的右子树断开：

第一棵树：A为根的左部分（A-B-C-D）
第二棵树：E为根（E-F，E-G-H）

森林：
树1:     A       树2:     E
          |            / \
          B           F   G
           \              /
            C            H
             \
              D

答案：森林包含2棵树。

方法反思：森林→二叉树→森林的过程：①用先序+中序还原二叉树 ②断开根的右子树链 ③每棵子树转换回树。

五、考情分析

项目	内容
考查频次	近5年约4次，高频考点
常见题型	选择题（树与二叉树的转换判断）、大题（给出树画二叉树、遍历序列还原森林）
分值占比	选择题2分 + 大题5-8分
命题趋势	树/森林与二叉树的转换是经典考点，常与遍历序列结合。近年倾向于综合性出题（如给森林的遍历序列还原森林并求某节点的度）
典型考点	①左孩子右兄弟法转换 ②树的先根/后根遍历与二叉树遍历的对应 ③森林与二叉树的相互转换

六、易错点提醒

易错点1

错误表现：树转换为二叉树时，将所有孩子都用右指针串起来，第一个孩子不放在左指针
错误原因：混淆了"第一个孩子放左"的规则
正确理解：第一个孩子→左指针，其余兄弟→右指针串链。不是所有孩子都放右边

易错点2

错误表现：混淆树的先根遍历和后根遍历与二叉树遍历的对应关系
错误原因：记混了对应关系
正确理解：先根=先序，后根=中序（不是后序！）。可以通过"根在前=先序，根在后=中序（因为后根遍历中根在所有子树之后）"来记忆

易错点3

错误表现：认为森林的中序遍历等于二叉树的后序遍历
错误原因：混淆了树的后根遍历和森林的中序遍历
正确理解：森林的中序遍历 = 二叉树的中序遍历。树的后根遍历也等于二叉树的中序遍历。这两者是一致的，但不是后序遍历

易错点4

错误表现：二叉树转森林时，忘记判断根是否有右子树
错误原因：忽略了转换条件
正确理解：若根无右子树，则转换结果只有一棵树（不是森林）；若有右子树，则右子树链上每棵子树都是一棵独立的树

七、来源标注

依据2026考研统考408大纲
依据《数据结构（C语言版）》严蔚敏版
依据《数据结构》王道考研辅导讲义

408 ​

数据结构 ​

DS-04-05 树与森林的存储与转换 ​

一、定位信息 ​

二、知识点讲解 ​

2.1 树的存储结构 ​

（1）双亲表示法（顺序存储） ​

（2）孩子表示法（链表+数组） ​

（3）孩子兄弟表示法（二叉链表表示法） ​

2.2 树转换为二叉树（左孩子右兄弟法） ​

2.3 森林转换为二叉树 ​

2.4 二叉树转换为森林 ​

2.5 树与森林的遍历 ​

2.6 存储方式对比表 ​

三、记忆与理解辅助 ​

技巧1：树↔二叉树转换口诀 ​

技巧2：树的遍历与二叉树遍历的对应关系 ​

技巧3：树转换为二叉树后的特征 ​

四、例题与精解 ​

例题1（基础巩固） ​

例题2（中等提升） ​

五、考情分析 ​

六、易错点提醒 ​

易错点1 ​

易错点2 ​

易错点3 ​

易错点4 ​

七、来源标注 ​

408