树、森林与二叉树互转全攻略：孩子兄弟表示法核心解析

数据结构里“树、森林、二叉树”这三块内容，我被问得最多的不是遍历，而是“转换”。不少人上课听定义都能听懂，一到手写代码就懵：怎么把一棵普通的多叉树变成二叉树？怎么把一个森林还原成多棵树？这篇不是教科书复读，而是我实际写代码、画图、调试过程中整理出来的转换全流程。标题括号里那句“HoRain云”是我在云平台上做数据结构专题笔记时的系列名，内容本身完全通用，适合正在学数据结构、准备考研复试、或者刷算法题被树形结构卡住的人。

先给结论：树、森林、二叉树能互相转换，核心就靠“孩子兄弟表示法”。理解了这个底层存储结构，所有转换规则都不是背出来的，而是顺理成章推出来的。下面我会从为什么需要转换讲起，把它背后的存储逻辑、规则细节、C++代码实现、常见坑一次说清楚。

1. 为什么树、森林和二叉树要互相转换

很多人觉得这又是教材在折腾人，明明是一棵普通的树，干嘛非要转成二叉树？等真去写代码就会明白，转换不是考试专用，是存储和算法上的刚需。

1.1 二叉树是“最省心”的树形存储结构

普通树的难点在于：一个节点的孩子数量不确定。比如有的节点只有1个孩子，有的节点有5个孩子，你没法提前知道每个节点该分配多少个指针域。如果按“最多孩子数”来设计节点，假设一棵树的度是k，每个节点都放k个指针，n个节点一共就有 n×k 个指针域。但树本身只有 n-1 条边，也就是只有 n-1 个指针是真正有用的，其余全是空的。

空指针数量公式是：n×k − (n−1) = n(k−1)+1。k越大，浪费越夸张。当k=5时，空指针数量是4n+1，超过总指针数的八成。这就像你给每个同事都配了12个抽屉，但大多数人柜子里只放两个文件夹，空间浪费肉眼可见。

二叉树的节点只需要两个指针域，左指针和右指针。n个节点的二叉树，指针域总数是2n，边数是n−1，空指针数约是2n−(n−1)=n+1。相比起来，浪费少得多。所以把一棵普通树转成二叉树，本质上是把“变长结构”压缩成固定大小的结构，让存储更加可控。

1.2 转换能让遍历和算法“统一规格”

树和森林的遍历规则其实并不难，难的是算法套路不统一。二叉树有一套非常成熟的递归框架：先序、中序、后序，左子树、右子树，边界清晰。普通多叉树呢？子树数量不定，循环里套递归，操作起来总感觉不如二叉树顺手。

转成二叉树后，一个多叉树的问题就变成了二叉树问题。比如很多N叉树相关的算法题，官方解法第一步就是把N叉树转成二叉树，再用二叉树的遍历框架处理。森林也一样，一个森林本质上是一组树，处理起来更散。但森林一旦转成二叉树，所有树根被串在一条右链上，整体就变成了一棵“大二叉树”，可以用一套逻辑搞定。

另外还有遍历序列的好处。树的先根遍历、后根遍历，和对应二叉树的先序遍历、中序遍历存在一一对应关系。这个映射关系在做序列还原题的时候特别好用。后面我会专门讲。

2. 转换前必须搞懂的底层关系：孩子兄弟表示法

转换不是凭空变魔术，所有规则都来源于一种存储设计：孩子兄弟表示法。搞懂它，转换题目就成功了一大半。

2.1 两个指针如何装下“任意多个孩子”

孩子兄弟表示法的节点只有两个指针域：

• 第一个指针指向该节点的第一个孩子，也就是“长子”。
• 第二个指针指向该节点的下一个兄弟。

口诀只有五个字：左孩子、右兄弟。这里的“右兄弟”是重中之重，它表示右指针指向的节点，不是当前节点的右孩子，而是当前节点的兄弟。这个概念一旦混淆，后面全乱。

举个具体例子。假设原树是这样的：A是根节点，A的孩子是B、C、D三个节点；B又有两个孩子E、F。用普通多叉树存，A下面挂三个孩子。用孩子兄弟表示法存，结构是：A的左指针指向B，B的右指针指向C，C的右指针指向D；同时B的左指针指向E，E的右指针指向F。

如果把这个结构画成标准二叉树的样子，就是一棵二叉树。这里的关键是：从“二叉树长相”上看，C和D好像是A的“右子树”，但它们的真实身份是A的孩子B的兄弟。这就是为什么很多人看转换步骤觉得“硬记”，其实理解成“兄弟被右指针串起来了”就会很顺。

2.2 孩子兄弟表示法与转换是一体两面

树转二叉树，实际上就是“用孩子兄弟表示法重新组织节点指针”。你把一棵本来就按孩子兄弟表示法存储的树，直接按二叉树视角输出，得到的自然就是二叉树。反过来说，二叉树转树，就是“按照左孩子、右兄弟的约定，把节点解释回多叉树”。

所以我建议你把转换理解为“同一种指针关系，两种解释方式”，而不是两套完全不同的规则。一旦建立这个认知，代码写起来会顺畅很多。

另外，孩子兄弟表示法还有一个好处：它不只适用于普通多叉树，森林也同样适用。森林中每一棵树的根节点之间本来就是“平级关系”，可以看作一组兄弟节点。把森林的第一棵树的根作为总根，其他树的根依次挂到右边兄弟链上，森林就变成了一棵二叉树。这就是森林转二叉树最直观的解释。

2.3 遍历顺序的对应关系是转换的“验证工具”

转换是否正确，最有效的验证方式就是比较遍历序列。

• 树的先根遍历序列 = 对应二叉树的先序遍历序列
• 树的后根遍历序列 = 对应二叉树的中序遍历序列
• 森林的先序遍历序列 = 对应二叉树的先序遍历序列
• 森林的后根遍历序列 = 对应二叉树的中序遍历序列

很多初学者在这会把“树的后根遍历”对应成二叉树的“后序遍历”，这是最容易错的点。原因在于：树的后根遍历是“先依次遍历所有子树，最后访问根节点”。这个顺序转成二叉树后会呈现什么样子？根节点的所有子树，长子变成了左子树，剩下的孩子变成了右链。遍历完这些内容之后，最后回到根节点。这个“左边子树处理完，访问根，再处理右边兄弟链”的模式，正是二叉树的中序遍历。

换句话说，树的后根遍历在二叉树里被“重新解释”成了中序遍历。验证方法很简单：随便找一棵三层的多叉树，手动转换后再分别做一次遍历，对比一下，你会立刻理解这个映射关系。

3. 三步搞定转换：规则拆解与具体示例

下面进入实操规则。我会按“树转二叉树”“森林转二叉树”“二叉树还原成树和森林”三部分来讲。

3.1 树转二叉树：左孩子右兄弟

规则可以拆成三步：

1. 同一父节点的相邻兄弟节点之间，用水平线连接起来。
2. 每个节点只保留与长子的连线，删掉与其他孩子的连线。
3. 以根节点为中心，把整棵树顺时针旋转约45度，让水平兄弟链变成右子树方向。

操作的时候，你先在草稿纸上把兄弟节点画在同一水平线上，连成一条链。然后想象整个结构旋转一下，兄弟链接到右侧。旋转后，“水平兄弟链”变成“右指针链”，“长子连线”变成“左指针链”。

举个例子，原树A有两个孩子B和C，B又有孩子D和E。转换后：A.left=B；B.right=C；B.left=D；D.right=E。这时C的右指针为空，D和E的兄弟关系体现在D.right=E上。根节点A没有兄弟，所以A的右指针一定为空。

注意：如果转换后的二叉树根节点右指针不为空，说明你处理的是森林转二叉树的结果，或者原树本身是作为森林中的一棵树来处理的。单独一棵树转二叉树，根节点右指针必须为空。

3.2 森林转二叉树：先把根也串成兄弟

森林转二叉树分两步：

1. 把森林中每棵树各自转换成二叉树。
2. 从第二棵树开始，把每棵树的根节点作为前一棵树根节点的右子树。换句话说，若干树根被串成一条右指针链。

比如森林有三棵树，根分别是A、G、H。A的孩子是B，G的孩子是K，H没有孩子。先分别转换：A.left=B；G.left=K；H保持不变。然后连接根：A.right=G，G.right=H。最终得到的二叉树，根是A，A.right是G，G.right是H。

你还可以用“虚拟根”来理解：假设存在一个虚拟节点R，它的孩子分别是A、G、H，先把这个虚拟树转成二叉树，再去掉虚拟根。去掉虚拟根后，A就是整棵二叉树的根，A.right=G，G.right=H，和前面结果一致。这个思路在代码实现时非常有用，很多人写森林转二叉树的递归函数，就是靠这个虚拟根把问题简化成树转二叉树。

3.3 二叉树还原成树和森林：把指针重新解释

二叉树转树，规则是“左链变孩子，右链变兄弟”，和树转二叉树正好相反。

当前节点的左子树，还原为多叉树中该节点的第一个孩子；当前节点的右子树，还原为该节点的下一个兄弟。递归处理左子树，沿着右链遍历，把沿途所有节点都收集成当前节点的孩子列表。

二叉树转森林，需要先判断这棵二叉树是否由森林转换而来。判断特征是根节点是否有右子树。在森林转二叉树时，根节点的右指针指向下一棵树的根，所以如果二叉树的根节点存在右子树，就说明原结构很可能是一个森林。

还原步骤：从根节点开始，不断把“根节点右子树”拆出来，每拆出一棵，就得到一棵独立的二叉树；再对每棵二叉树执行“二叉树转树”操作。递归处理完右链，就能还原出多棵树组成的森林。

注意：并不是任意一棵二叉树都能“还原”成有意义的树或森林。只有满足“节点左孩子是长子、右孩子是兄弟”语义的二叉树，才能直接还原。如果你随便给一棵普通二叉树，硬要转成多叉树，得到的只是一个“结构上成立、但语义可能不对”的森林。考试和面试里，题目默认给出的二叉树就是由树或森林转换得到的。

4. C++代码实现：从定义到转换函数

理论看明白了，代码才是最终检验。

4.1 两种节点定义与工具函数

我习惯同时定义两个结构体：多叉树节点和二叉树节点。虽然孩子兄弟表示法在物理上就是二叉链表，但为了清晰，一般在转换时用一个多叉树结构和一个二叉树结构，避免把两种语义混在一起。

#include <iostream> #include <vector> #include <queue> using namespace std; // 多叉树节点 struct MultiNode { int val; vector<MultiNode*> children; MultiNode(int x) : val(x) {} }; // 二叉树节点 struct BinaryNode { int val; BinaryNode* left; BinaryNode* right; BinaryNode(int x) : val(x), left(nullptr), right(nullptr) {} };

多叉树用vector存孩子，写起来直观。面试时如果你不想用vector，也可以改成“第一个孩子 + 下一个兄弟”的节点结构，原理一样。

我还会写一个简单的创建函数，方便测试。比如手动构建一棵A为根，B、C、D为孩子的树，再给B挂上E、F两个子节点。实际测试时，你可以用一个数组批量建树，但小规模手写更不容易错。

MultiNode* createSampleTree() { MultiNode* A = new MultiNode(1); MultiNode* B = new MultiNode(2); MultiNode* C = new MultiNode(3); MultiNode* D = new MultiNode(4); MultiNode* E = new MultiNode(5); MultiNode* F = new MultiNode(6); A->children.push_back(B); A->children.push_back(C); A->children.push_back(D); B->children.push_back(E); B->children.push_back(F); return A; }

4.2 树转二叉树与森林转二叉树的实现

树转二叉树，关键是处理孩子列表。第一个孩子变成左子树，其余孩子依次变成前一个孩子的右子树。

BinaryNode* treeToBinary(MultiNode* root) { if (root == nullptr) return nullptr; BinaryNode* bNode = new BinaryNode(root->val); if (!root->children.empty()) { // 第一个孩子作为左孩子 bNode->left = treeToBinary(root->children[0]); // 后续孩子串成右链 BinaryNode* cur = bNode->left; for (size_t i = 1; i < root->children.size(); ++i) { cur->right = treeToBinary(root->children[i]); cur = cur->right; } } return bNode; }

这个递归的核心逻辑：每棵子树都独立调用treeToBinary，转换成对应的二叉树子树。第一个孩子放左指针，剩下的孩子依次放右指针。之所以能这样，是因为右指针本来就是用来表达兄弟关系的。

森林转二叉树，可以复用treeToBinary。处理方式是把森林看成一个虚拟根节点，但代码里不需要真的创建虚拟根，直接循环即可：

BinaryNode* forestToBinary(vector<MultiNode*>& forest) { if (forest.empty()) return nullptr; BinaryNode* root = treeToBinary(forest[0]); BinaryNode* cur = root; for (size_t i = 1; i < forest.size(); ++i) { cur->right = treeToBinary(forest[i]); cur = cur->right; } return root; }

这里有一个细节：第一棵树的根节点转换成二叉树后，它的右指针本来应该为空。但森林转二叉树时，我们需要把第二棵树的根挂到它的右指针上。这个操作不会丢信息，因为原树根在森林中本身就是和下一棵树根平级的。

4.3 二叉树还原为树与森林的实现

二叉树转多叉树，沿着左孩子找孩子链，沿着右孩子找兄弟链，递归还原。

MultiNode* binaryToTree(BinaryNode* root) { if (root == nullptr) return nullptr; MultiNode* mNode = new MultiNode(root->val); BinaryNode* child = root->left; while (child != nullptr) { mNode->children.push_back(binaryToTree(child)); child = child->right; } return mNode; }

这个函数读起来非常符合孩子兄弟表示法的直觉。root->left是第一个孩子，root->left->right是第二个孩子，再往后是第三个孩子。每遇到一个孩子节点，就递归把它的子树还原为多叉树子树。

二叉树转森林，关键是先拆右链，再把每棵拆出来的二叉树分别还原成树：

vector<MultiNode*> binaryToForest(BinaryNode* root) { vector<MultiNode*> forest; BinaryNode* current = root; while (current != nullptr) { BinaryNode* nextRoot = current->right; // 断开右链，让当前二叉树变成独立的一棵树 current->right = nullptr; forest.push_back(binaryToTree(current)); current = nextRoot; } return forest; }

注意：断开current->right之前，必须先保存current->right到nextRoot，否则就丢了后面树的指针。很多人第一次写会漏掉这一步，导致只还原出第一棵树。

4.4 完整测试示例

我建议每次都写一个打印函数，用先序遍历验证结果。比如：

void printBinaryPreorder(BinaryNode* root) { if (root == nullptr) return; cout << root->val << " "; printBinaryPreorder(root->left); printBinaryPreorder(root->right); } void printMultiPreorder(MultiNode* root) { if (root == nullptr) return; cout << root->val << " "; for (MultiNode* child : root->children) { printMultiPreorder(child); } }

在多叉树转二叉树时，如果打印的二叉树先序遍历序列和原多叉树的先根遍历序列一致，基本可以判定转换正确。同理，二叉树还原成多叉树后，再打印多叉树的先根遍历序列，应当与原二叉树先序遍历序列一致。这套验证方法能在早期揪出大量指针错误。

5. 常见问题与排查技巧实录

转换代码本身不复杂，但我在实际调试和帮人看代码时，发现下面几个问题出现频率非常高。

5.1 遍历序列对不上

新手最常遇到的情况是：转换完以后，用遍历结果验证，发现树的后根遍历序列和二叉树的后序遍历序列不一样，于是怀疑代码写错了。其实代码没写错，是“对应关系记错了”。

再看一遍这张对应表：

如果考试里给你一棵树，转成二叉树后要你写出“二叉树的中序遍历”，你要能反应过来它就是把原树做后根遍历。这个映射关系不是死记硬背，而是要回到孩子兄弟表示法里去理解。

5.2 转换后的二叉树形态不对

如果你写出的二叉树长得和标准答案不一样，先检查两个点。

第一，兄弟节点是不是被放到了左子树上。孩子兄弟表示法的右指针专门存兄弟，如果你把除长子外的其他孩子放到左子树上，那转换出来的二叉树会“多叉”，不符合二叉树定义。

第二，森林转二叉树时，树根连接顺序对不对。森林转二叉树后，所有树根串成一条右链，而不是左链。所有树根串成左链的写法，转换为“多叉树里的根节点有多个孩子”，语义就错了。

5.3 递归深度过大导致程序崩溃

树的深度很大时，递归转换可能出现栈溢出。比如一条链状的树，递归深度等于节点数，几万层下来很容易爆栈。

解决思路有三个：

1. 把递归改为显式栈，用非递归方式遍历。
2. 如果递归总深度可控，只是测试数据比较大，可以调大程序栈空间。
3. 分析问题本身能否转成“迭代构建”，比如按顺序插入节点，而不是一次性递归建树。

日常做算法题和考试，树深度一般不会大到爆栈。但如果你在真实项目里处理深度很大的目录结构，就要提前想到递归风险。

5.4 内存释放问题

代码里大量使用new创建节点，如果不主动释放，就会内存泄漏。很多算法题的代码不关心释放，因为程序跑完进程就结束，但养成好习惯很重要。

释放二叉树和多叉树的方式都是递归delete。需要注意的是，如果你把一棵多叉树转成了二叉树，那么两棵树的节点是独立创建的，需要分别释放。如果只是临时转换验证，要确保最后不会重复释放同一块内存。

6. 我踩过的坑和一些实操体会

最后说点代码之外的体会。转换这件事，最怕只背流程不画图。我见过太多同学能把口诀背得滚瓜烂熟，但让他手动转一棵三层的树就转错。原因是树的结构画得不清晰，兄弟链和父子链全缠在一起。

我自己的习惯是，先用缩进式文本把树写出来，比如：

A ├── B │ ├── D │ └── E └── C

然后在旁边把孩子兄弟表示法标出来：A的右指针？空。B的右指针？指向C。D的右指针？指向E。这样一标，二叉树的长相基本就出来了。

还有一个很有用的验证技巧：转换完之后，不要只看静态结构，主动做两遍遍历。第一遍对原多叉树做先根遍历，第二遍对转换出的二叉树做先序遍历，两个序列完全一致说明逻辑没跑偏。这个方法救过我无数次，尤其是调试递归的时候。

面试里比较高频的考法有几种：给你一棵树，转成二叉树并写出先序、中序序列；或者给你森林转出的二叉树的中序序列，让你还原森林有几棵树；再或者直接让你写代码实现多叉树和二叉树的互转。不管哪种考法，核心都没离开“左孩子、右兄弟”这六个字。把指针语义想清楚，代码其实就是在翻译这句话。

如果哪天你要在项目里把一棵多叉树转成二叉树，我的建议是从一棵三节点的小树开始调通，再去处理几十个节点的复杂结构。我个人的习惯是遇到了就画一遍、写一遍，转换这层窗户纸很快就能捅破。