树与森林 ↔ 二叉树的转换

2026 大纲 四（三）2 森林与二叉树的转换、（三）3 树和森林的遍历 · 本篇负责转换规则与遍历对应关系的推导（树 / 森林各自遍历的定义与求法见《树与森林》）。

转换不是"变成另一棵树"，是换一种读法

一个结点在内存里就是"数据 + 两个指针"。

把这两个指针读作 "第一个孩子 / 右兄弟"，你看到的是一棵一般树；
读作 "左孩子 / 右孩子"，你看到的就是一棵二叉树。

存储一个字节都没动。 这一句话解释了三件事：

对应关系为什么是一一的——同一份存储只有一种读法结果，反过来也只有一种；
转换为什么是 $O (n)$ 且原地的——本质上什么都不用做；
转换后为什么能直接套用二叉树的全部算法——它本来就是一棵二叉链表。

由这个读法立刻推出一条关键性质：树转出来的二叉树，根一定没有右子树。 右指针指向右兄弟，而树只有一个根、根没有兄弟。教材把这句写成"任何一棵和树对应的二叉树，其根结点的右子树必空"。

森林则相反：第二棵树的根被看作第一棵树根的兄弟，所以森林（两棵及以上）转出的二叉树，根有右子树。这条性质是整篇的枢纽——后面判断"该还原成树还是森林""森林有几棵树"，靠的都是它。

先看一眼

加载可视化中...

看完你应该确认：转换前后结点个数不变，变的只是连线的解释——原来横着的兄弟关系，变成了竖着的右指针。

树 → 二叉树：兄弟相连留长子

手工画法三步：① 在所有相邻兄弟结点之间加连线；② 每个结点只保留与第一个孩子的连线，删除与其他孩子的连线；③ 以根为轴心顺时针旋转 45°（横线变成右指针、竖线变成左指针）。

第 0 步：原树              第 1 步：兄弟相连           第 2 步：只留长子
      A                        A                          A
    / | \                    / | \                        |
   B  C  D                  B—-C—-D                      B—-C—-D
  / \    |                 / \    |                      |     |
 E   F   G               E—-F     G                      E—-F  G

第 3 步：顺时针旋转 45°（横线变成右指针、竖线变成左指针）
      A
     /
    B
   / \
  E   C
   \    \
    F    D
        /
       G

逐个核对：A 的左孩子是 B（A 的长子）、A 无右孩子（A 无兄弟）；B 的左孩子是 E（B 的长子）、右孩子是 C（B 的右兄弟）；E 无左孩子、右孩子是 F（E 的右兄弟）；C 无左孩子（C 是叶子）、右孩子是 D；D 的左孩子是 G、无右孩子 ✓

一棵树对应唯一一棵二叉树——孩子的次序（有序树）唯一决定了长子与兄弟链，二叉树的形态被完全钉死。

森林 → 二叉树：各棵树的根互为兄弟

直观做法是：先把每棵树各自转成二叉树，再把第二棵作为第一棵根的右子树、第三棵作为第二棵根的右子树，依此类推——所有树的根通过右指针串成一条链。

等价的一句话理解更好用：把森林中各棵树的根看作互为兄弟，然后整体按孩子兄弟法处理。 因为"右指针指向右兄弟"，各树根自然被串起来。

不过真正好用的是递归定义。设森林 $F = {T_{1}, T_{2}, \dots, T_{m}}$ ，对应的二叉树 $B = (root, L B, R B)$ ：

若 $F$ 为空（ $m = 0$ ），则 $B$ 为空树；
若 $F$ 非空，则 $B$ 的根即为第一棵树的根； $B$ 的左子树由 $T_{1}$ 根结点的子树森林转换而成； $B$ 的右子树由森林 ${T_{2}, \dots, T_{m}}$ 转换而成。

二叉树的根 \leftrightarrow 第一棵树的根, 左子树 \leftrightarrow 第一棵树的子树森林, 右子树 \leftrightarrow 剩余树的森林

这三条对应是本篇后半部分的全部依据——遍历的对应关系、棵数的数法，都由它一步推出，不需要另外记。

森林转换的完整示例与逐指针核对（第一次学、想手工核对时展开）

森林 F = { T1, T2, T3 }

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

转换后的二叉树（左指针 = 长子，右指针 = 右兄弟）：

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

逐个核对：A 的长子是 B → 左孩子 B；A 的"右兄弟"是 E（T2 的根）→ 右孩子 E。B 无孩子 → 无左孩子；B 的右兄弟是 C → 右孩子 C。C 的长子是 D → 左孩子 D；C 无右兄弟 → 无右孩子。E 的长子是 F → 左孩子 F；E 的右兄弟是 G（T3 的根）→ 右孩子 G。G 的长子是 H → 左孩子 H；G 无右兄弟 → 无右孩子。H 无孩子；H 的右兄弟是 I → 右孩子 I ✓

根 A 有右子树（因为 A 有"兄弟" E），与"一棵树转出来的根没有右子树"形成对照。

逆变换：先看根有没有右子树

判据只有一条：根没有右子树 → 还原为一棵树；根有右子树 → 还原为森林，且

森林的棵数 = 沿根的右链能走的步数 + 1 = 根的右链上的结点数

因为各树根正是被右指针串成一条链的。数右链时只算沿右孩子能到达的结点——右子树内部的左孩子不在右链上，把它们也数进去是这里最典型的错法。

具体执行三步：① 沿根的右指针链逐个断开，得到若干棵二叉树（还原成一棵树时这一步为空操作）；② 对每棵二叉树，若结点 $p$ 是其双亲的左孩子，则把 $p$ 的右孩子、右孩子的右孩子……全部与 $p$ 的双亲连线——它们原本都是 $p$ 的兄弟；③ 删除所有结点与其右孩子的连线，调整层次。

遍历的对应关系：后序没有对应物

树（一般树）的遍历	森林的遍历	对应二叉树的遍历
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历
没有对应	没有对应	后序遍历

前两行不必死记，它们是"逐字相同"的。 把上面那三条框起来的对应代进二叉树遍历的定义即可：

Pre (B (F)) = \underset{访问第一棵树的根}{\underset{⏟}{root (T_{1})}} \cdot \underset{先序遍历第一棵树的子树森林}{\underset{⏟}{Pre (B (children (T_{1})))}} \cdot \underset{先序遍历剩余森林}{\underset{⏟}{Pre (B ({T_{2}, \dots}))}}

这三段逐字就是森林先序遍历的定义。中序同理：

In (B (F)) = \underset{中序遍历子树森林}{\underset{⏟}{In (B (children (T_{1})))}} \cdot \underset{访问第一棵树的根}{\underset{⏟}{root (T_{1})}} \cdot \underset{中序遍历剩余森林}{\underset{⏟}{In (B ({T_{2}, \dots}))}}

之所以逐字相同不是巧合——森林的这两种遍历本来就是照着"二叉树的根 / 左子树 / 右子树"的三段式定义出来的。

真正要想一下的是第三行：树的后根为什么对应中序，而不是后序。

用前面那棵树对照三种序列：

二叉树遍历	序列	树上的对应
先序	A B E F C D G	= 树的先根遍历
中序	E F B C G D A	= 树的后根遍历
后序	F E G D C B A	树上没有任何一种遍历给出它

根源在于"树转出来的二叉树，根没有右子树"。 树的后根遍历要求"根排在它的所有子树之后"；转换后，一棵树的全部子树都被塞进了二叉树的左子树，右子树是空的。于是：

中序（左 → 根 → 右）：左子树（ $=$ 全部子树）→ 根 → 空。根排在所有子树之后 ✓
后序（左 → 右 → 根）：在根这一层上后序和中序给出的位置相同，但在内部结点上就不同了——内部结点的右子树是它的兄弟们，非空。上表里 B 被排到了 C、D、G 之后，而"访问完兄弟才访问自己"在树上没有任何语义。

转换后的空指针分别是谁贡献的

转换不增删结点，所以对应的二叉树同样是 $n$ 个结点，作为一棵二叉链表有 $n + 1$ 个空指针域。这 $n + 1$ 个还能进一步分清来源：

空指针	什么时候为空	个数
左指针（`firstchild`）	该结点没有孩子，即它是原森林中的叶结点	$n_{0}$ （叶结点数）
右指针（`nextsibling`）	该结点是其双亲的最后一个孩子，或是最后一棵树的根	（分支结点数） $+ 1 = (n - n_{0}) + 1$
合计	—	$n_{0} + (n - n_{0}) + 1 = n + 1$ ✓

第一行反过来读特别有用：原森林中叶结点的个数，等于转换后二叉树中左指针为空的结点个数。 因为"在森林中有孩子"与"在二叉树中左指针非空"是同一件事。

用上面折叠块里那片 9 个结点的森林验算：叶结点是 B、D、F、H、I 共 5 个 → 空左指针 5 个；分支结点是 A、C、E、G 共 4 个 → 空右指针 $4 + 1 = 5$ 个；合计 10 $= 9 + 1$ ✓

考点速记

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

转换只是换一种读法：孩子兄弟表示法的两个指针改读作左右孩子即得二叉树，所以对应是一一的、 $O (n)$ 的、原地的。
"根有没有右子树"是树与森林的分水岭：正变换里树的根必无右子树，逆变换里它是"还原成树还是森林"的唯一判据，森林棵数 $=$ 根的右链结点数。
树的后根 $=$ 二叉树的中序（不是后序），二叉树的后序在树 / 森林上没有对应物。

这一节在真题里被考过的形式。 需要说明：这个知识点的真题分散挂在几个考点标签下——下方「真题练习」列出直接挂在本节的两道，另有几道挂在《树与森林》《树与二叉树基本概念》下，考的是同一件事。四类考法：

遍历对应的直接问法。 "树 $T$ 转成二叉树 $B T$ ， $B T$ 的哪种遍历与 $T$ 的后根遍历序列相同"——答中序。或者反过来，给森林的先根 + 中根序列，要求对应二叉树的后序：先把森林遍历翻译成二叉树遍历（先根 ↔ 先序、中根 ↔ 中序），再由先序 + 中序重建，最后读后序。
数森林的棵数。 给二叉树的先序 + 中序，问森林有几棵树。重建出二叉树后数根的右链结点数。
转换前后的结点属性对应。 "森林 $F$ 转成二叉树 $T$ ， $F$ 中叶子的个数等于什么"——等于 $T$ 中左指针为空的结点数。这一类题的通法是：先把"在森林中的某性质"翻译成"在二叉树中某指针的空 / 非空"，再数。
祖孙关系的还原。 "二叉树中 $u$ 是 $v$ 的父结点的父结点，原森林中 $u$ 与 $v$ 可能是什么关系"——做法是枚举那两步各自是左边还是右边，共四种组合，逐一翻译回森林：左左 $\to$ 祖孙；左右 $\to$ 父子；右左 $\to$ 叔侄；右右 $\to$ 兄弟。

易错：数森林棵数时把右子树里的左孩子也算进右链。 只有沿右孩子链能到达的结点才算。

易错：把树的后根对应成二叉树的后序。 对应的是中序，这是这一节被考得最直接的一条。

易错：以为森林转出的二叉树根也没有右子树。 只有单棵树才没有；有没有右子树正是判别树与森林的依据。

教材出处

孩子兄弟法（"又称二叉树表示法，或二叉链表表示法……分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild 域和 nextsibling 域"），以及"从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其根结点的右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p134（5.6.1–5.6.2 节）
森林转换成二叉树的递归定义（" $B$ 的根 root 即为森林中第一棵树的根 $ROOT (T_{1})$ ； $B$ 的左子树 $L B$ 是从 $T_{1}$ 中根结点的子树森林转换而成的二叉树；其右子树 $R B$ 是从森林 $F^{'} = {T_{2}, \dots, T_{m}}$ 转换而成的二叉树"）与二叉树转换成森林的互逆定义，以及"这个一一对应的关系说明森林或树与二叉树可以相互转换"：印刷 p135（5.6.2 节）
树的先根 / 后根遍历定义与"按照森林和树相互递归的定义，可以推出森林的两种遍历方法：先序遍历和中序遍历"：印刷 p135（5.6.3 节）
森林的先序 / 中序遍历的三步规则，以及"当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历""树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现"：印刷 p136

真题练习

2021Q42分 2020Q42分

树与森林 ↔ 二叉树的转换

转换不是"变成另一棵树"，是换一种读法

先看一眼

树 → 二叉树：兄弟相连留长子

森林 → 二叉树：各棵树的根互为兄弟

逆变换：先看根有没有右子树

遍历的对应关系：后序没有对应物

转换后的空指针分别是谁贡献的

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（2题）

树与森林 ↔ 二叉树的转换 ​

转换不是"变成另一棵树"，是换一种读法 ​

先看一眼 ​

树 → 二叉树：兄弟相连留长子 ​

森林 → 二叉树：各棵树的根互为兄弟 ​

逆变换：先看根有没有右子树 ​

遍历的对应关系：后序没有对应物 ​

转换后的空指针分别是谁贡献的 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（2题）

树与森林 ↔ 二叉树的转换

转换不是"变成另一棵树"，是换一种读法

先看一眼

树 → 二叉树：兄弟相连留长子

森林 → 二叉树：各棵树的根互为兄弟

逆变换：先看根有没有右子树

遍历的对应关系：后序没有对应物

转换后的空指针分别是谁贡献的

考点速记

相关知识

真题练习