数据结构里“树、森林、二叉树”这三块内容我被问得最多的不是遍历而是“转换”。不少人上课听定义都能听懂一到手写代码就懵怎么把一棵普通的多叉树变成二叉树怎么把一个森林还原成多棵树这篇不是教科书复读而是我实际写代码、画图、调试过程中整理出来的转换全流程。标题括号里那句“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越大浪费越夸张。当k5时空指针数量是4n1超过总指针数的八成。这就像你给每个同事都配了12个抽屉但大多数人柜子里只放两个文件夹空间浪费肉眼可见。二叉树的节点只需要两个指针域左指针和右指针。n个节点的二叉树指针域总数是2n边数是n−1空指针数约是2n−(n−1)n1。相比起来浪费少得多。所以把一棵普通树转成二叉树本质上是把“变长结构”压缩成固定大小的结构让存储更加可控。1.2 转换能让遍历和算法“统一规格”树和森林的遍历规则其实并不难难的是算法套路不统一。二叉树有一套非常成熟的递归框架先序、中序、后序左子树、右子树边界清晰。普通多叉树呢子树数量不定循环里套递归操作起来总感觉不如二叉树顺手。转成二叉树后一个多叉树的问题就变成了二叉树问题。比如很多N叉树相关的算法题官方解法第一步就是把N叉树转成二叉树再用二叉树的遍历框架处理。森林也一样一个森林本质上是一组树处理起来更散。但森林一旦转成二叉树所有树根被串在一条右链上整体就变成了一棵“大二叉树”可以用一套逻辑搞定。另外还有遍历序列的好处。树的先根遍历、后根遍历和对应二叉树的先序遍历、中序遍历存在一一对应关系。这个映射关系在做序列还原题的时候特别好用。后面我会专门讲。2. 转换前必须搞懂的底层关系孩子兄弟表示法转换不是凭空变魔术所有规则都来源于一种存储设计孩子兄弟表示法。搞懂它转换题目就成功了一大半。2.1 两个指针如何装下“任意多个孩子”孩子兄弟表示法的节点只有两个指针域第一个指针指向该节点的第一个孩子也就是“长子”。第二个指针指向该节点的下一个兄弟。口诀只有五个字左孩子、右兄弟。这里的“右兄弟”是重中之重它表示右指针指向的节点不是当前节点的右孩子而是当前节点的兄弟。这个概念一旦混淆后面全乱。举个具体例子。假设原树是这样的A是根节点A的孩子是B、C、D三个节点B又有两个孩子E、F。用普通多叉树存A下面挂三个孩子。用孩子兄弟表示法存结构是A的左指针指向BB的右指针指向CC的右指针指向D同时B的左指针指向EE的右指针指向F。如果把这个结构画成标准二叉树的样子就是一棵二叉树。这里的关键是从“二叉树长相”上看C和D好像是A的“右子树”但它们的真实身份是A的孩子B的兄弟。这就是为什么很多人看转换步骤觉得“硬记”其实理解成“兄弟被右指针串起来了”就会很顺。2.2 孩子兄弟表示法与转换是一体两面树转二叉树实际上就是“用孩子兄弟表示法重新组织节点指针”。你把一棵本来就按孩子兄弟表示法存储的树直接按二叉树视角输出得到的自然就是二叉树。反过来说二叉树转树就是“按照左孩子、右兄弟的约定把节点解释回多叉树”。所以我建议你把转换理解为“同一种指针关系两种解释方式”而不是两套完全不同的规则。一旦建立这个认知代码写起来会顺畅很多。另外孩子兄弟表示法还有一个好处它不只适用于普通多叉树森林也同样适用。森林中每一棵树的根节点之间本来就是“平级关系”可以看作一组兄弟节点。把森林的第一棵树的根作为总根其他树的根依次挂到右边兄弟链上森林就变成了一棵二叉树。这就是森林转二叉树最直观的解释。2.3 遍历顺序的对应关系是转换的“验证工具”转换是否正确最有效的验证方式就是比较遍历序列。树的先根遍历序列 对应二叉树的先序遍历序列树的后根遍历序列 对应二叉树的中序遍历序列森林的先序遍历序列 对应二叉树的先序遍历序列森林的后根遍历序列 对应二叉树的中序遍历序列很多初学者在这会把“树的后根遍历”对应成二叉树的“后序遍历”这是最容易错的点。原因在于树的后根遍历是“先依次遍历所有子树最后访问根节点”。这个顺序转成二叉树后会呈现什么样子根节点的所有子树长子变成了左子树剩下的孩子变成了右链。遍历完这些内容之后最后回到根节点。这个“左边子树处理完访问根再处理右边兄弟链”的模式正是二叉树的中序遍历。换句话说树的后根遍历在二叉树里被“重新解释”成了中序遍历。验证方法很简单随便找一棵三层的多叉树手动转换后再分别做一次遍历对比一下你会立刻理解这个映射关系。3. 三步搞定转换规则拆解与具体示例下面进入实操规则。我会按“树转二叉树”“森林转二叉树”“二叉树还原成树和森林”三部分来讲。3.1 树转二叉树左孩子右兄弟规则可以拆成三步同一父节点的相邻兄弟节点之间用水平线连接起来。每个节点只保留与长子的连线删掉与其他孩子的连线。以根节点为中心把整棵树顺时针旋转约45度让水平兄弟链变成右子树方向。操作的时候你先在草稿纸上把兄弟节点画在同一水平线上连成一条链。然后想象整个结构旋转一下兄弟链接到右侧。旋转后“水平兄弟链”变成“右指针链”“长子连线”变成“左指针链”。举个例子原树A有两个孩子B和CB又有孩子D和E。转换后A.leftBB.rightCB.leftDD.rightE。这时C的右指针为空D和E的兄弟关系体现在D.rightE上。根节点A没有兄弟所以A的右指针一定为空。注意如果转换后的二叉树根节点右指针不为空说明你处理的是森林转二叉树的结果或者原树本身是作为森林中的一棵树来处理的。单独一棵树转二叉树根节点右指针必须为空。3.2 森林转二叉树先把根也串成兄弟森林转二叉树分两步把森林中每棵树各自转换成二叉树。从第二棵树开始把每棵树的根节点作为前一棵树根节点的右子树。换句话说若干树根被串成一条右指针链。比如森林有三棵树根分别是A、G、H。A的孩子是BG的孩子是KH没有孩子。先分别转换A.leftBG.leftKH保持不变。然后连接根A.rightGG.rightH。最终得到的二叉树根是AA.right是GG.right是H。你还可以用“虚拟根”来理解假设存在一个虚拟节点R它的孩子分别是A、G、H先把这个虚拟树转成二叉树再去掉虚拟根。去掉虚拟根后A就是整棵二叉树的根A.rightGG.rightH和前面结果一致。这个思路在代码实现时非常有用很多人写森林转二叉树的递归函数就是靠这个虚拟根把问题简化成树转二叉树。3.3 二叉树还原成树和森林把指针重新解释二叉树转树规则是“左链变孩子右链变兄弟”和树转二叉树正好相反。当前节点的左子树还原为多叉树中该节点的第一个孩子当前节点的右子树还原为该节点的下一个兄弟。递归处理左子树沿着右链遍历把沿途所有节点都收集成当前节点的孩子列表。二叉树转森林需要先判断这棵二叉树是否由森林转换而来。判断特征是根节点是否有右子树。在森林转二叉树时根节点的右指针指向下一棵树的根所以如果二叉树的根节点存在右子树就说明原结构很可能是一个森林。还原步骤从根节点开始不断把“根节点右子树”拆出来每拆出一棵就得到一棵独立的二叉树再对每棵二叉树执行“二叉树转树”操作。递归处理完右链就能还原出多棵树组成的森林。注意并不是任意一棵二叉树都能“还原”成有意义的树或森林。只有满足“节点左孩子是长子、右孩子是兄弟”语义的二叉树才能直接还原。如果你随便给一棵普通二叉树硬要转成多叉树得到的只是一个“结构上成立、但语义可能不对”的森林。考试和面试里题目默认给出的二叉树就是由树或森林转换得到的。4. C代码实现从定义到转换函数理论看明白了代码才是最终检验。4.1 两种节点定义与工具函数我习惯同时定义两个结构体多叉树节点和二叉树节点。虽然孩子兄弟表示法在物理上就是二叉链表但为了清晰一般在转换时用一个多叉树结构和一个二叉树结构避免把两种语义混在一起。#include iostream #include vector #include queue using namespace std; // 多叉树节点 struct MultiNode { int val; vectorMultiNode* 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(vectorMultiNode* 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是第二个孩子再往后是第三个孩子。每遇到一个孩子节点就递归把它的子树还原为多叉树子树。二叉树转森林关键是先拆右链再把每棵拆出来的二叉树分别还原成树vectorMultiNode* binaryToForest(BinaryNode* root) { vectorMultiNode* 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 递归深度过大导致程序崩溃树的深度很大时递归转换可能出现栈溢出。比如一条链状的树递归深度等于节点数几万层下来很容易爆栈。解决思路有三个把递归改为显式栈用非递归方式遍历。如果递归总深度可控只是测试数据比较大可以调大程序栈空间。分析问题本身能否转成“迭代构建”比如按顺序插入节点而不是一次性递归建树。日常做算法题和考试树深度一般不会大到爆栈。但如果你在真实项目里处理深度很大的目录结构就要提前想到递归风险。5.4 内存释放问题代码里大量使用new创建节点如果不主动释放就会内存泄漏。很多算法题的代码不关心释放因为程序跑完进程就结束但养成好习惯很重要。释放二叉树和多叉树的方式都是递归delete。需要注意的是如果你把一棵多叉树转成了二叉树那么两棵树的节点是独立创建的需要分别释放。如果只是临时转换验证要确保最后不会重复释放同一块内存。问题现象可能原因排查方法后根遍历对不上映射关系记错用表对照手算一次二叉树形态多叉兄弟放到了左子树检查递归中cur-right赋值只还原出部分树忘记保存nextRoot检查while循环中先保存再断链程序内存暴涨new的节点未释放写递归释放函数测试后调用空树转换报错没有判断root为nullptr每个递归入口先判空6. 我踩过的坑和一些实操体会最后说点代码之外的体会。转换这件事最怕只背流程不画图。我见过太多同学能把口诀背得滚瓜烂熟但让他手动转一棵三层的树就转错。原因是树的结构画得不清晰兄弟链和父子链全缠在一起。我自己的习惯是先用缩进式文本把树写出来比如A ├── B │ ├── D │ └── E └── C然后在旁边把孩子兄弟表示法标出来A的右指针空。B的右指针指向C。D的右指针指向E。这样一标二叉树的长相基本就出来了。还有一个很有用的验证技巧转换完之后不要只看静态结构主动做两遍遍历。第一遍对原多叉树做先根遍历第二遍对转换出的二叉树做先序遍历两个序列完全一致说明逻辑没跑偏。这个方法救过我无数次尤其是调试递归的时候。面试里比较高频的考法有几种给你一棵树转成二叉树并写出先序、中序序列或者给你森林转出的二叉树的中序序列让你还原森林有几棵树再或者直接让你写代码实现多叉树和二叉树的互转。不管哪种考法核心都没离开“左孩子、右兄弟”这六个字。把指针语义想清楚代码其实就是在翻译这句话。如果哪天你要在项目里把一棵多叉树转成二叉树我的建议是从一棵三节点的小树开始调通再去处理几十个节点的复杂结构。我个人的习惯是遇到了就画一遍、写一遍转换这层窗户纸很快就能捅破。