8、树与森林的转换：树转换为二叉树、森林转换为二叉树、二叉树转换为树/森林
树和森林的转换，说白了就是给多叉树找个统一的存储格式。我刚开始学数据结构时，总觉得这玩意儿就是纯理论，直到后来做文件系统解析，才真正体会到它的价值。
为什么要转换？因为二叉树的结构简单，存储方便，遍历算法也成熟。你想想看，一个节点最多俩孩子，用左右指针就能搞定。但普通的树，每个节点孩子数量不定，存储起来就麻烦多了。
8.1 树转换为二叉树
转换规则其实就一句话：左孩子右兄弟。嗯，记住这四个字就够了。
具体怎么做？我习惯分三步走：
- 连线：把每个节点的兄弟节点连起来
- 拆线：只保留每个节点与第一个孩子的连线，其他孩子连线全拆掉
- 旋转：把整棵树顺时针旋转45度，兄弟连线变成右子树
举个例子，假设有一棵树：
A
/ | \
B C D
/ \ |
E F G转换过程是这样的：
- A的孩子有B、C、D，B是第一个孩子，保留A→B的连线
- B、C、D是兄弟，把它们连起来：B→C→D
- B的孩子有E、F，保留B→E，E和F是兄弟，连起来
- D的孩子有G，保留D→G
转换后的二叉树：
A
/
B
\
C
\
D
/
G等等，E和F去哪了？别急，完整的结构应该是：
A
/
B
/ \
E C
\ \
F D
/
G核心要点：转换后的二叉树中，左子树是原节点的第一个孩子，右子树是原节点的下一个兄弟。这个规律在任何情况下都成立。
8.2 森林转换为二叉树
森林就是多棵树的集合。转换起来也不复杂，我总结了两步：
- 先把森林里每棵树单独转换成二叉树
- 把转换后的二叉树根节点用右指针串起来
为什么是右指针？因为根节点之间是兄弟关系，兄弟关系在二叉树里用右指针表示。这个逻辑是自洽的。
假设森林有三棵树：
第一棵: A(B, C) 第二棵: D(E) 第三棵: F(G, H)转换后：
A
/
B
\
C
\
D
/
E
\
F
/
G
\
H你看，三棵树的根节点A、D、F通过右指针串成了一根链。这就是森林转二叉树的精髓。
小技巧：我在做项目时，经常用这个转换来统一处理树形数据。比如解析XML文档，先把DOM树转成二叉树，再用二叉树的遍历算法处理，代码写起来特别顺手。
8.3 二叉树转换为树/森林
这是逆过程。判断标准很简单：看根节点有没有右子树。
- 根节点没有右子树 → 转换成一棵树
- 根节点有右子树 → 转换成森林
转换步骤：
- 把二叉树根节点的右指针断开，每断开一次就得到一棵二叉树的根
- 对每棵二叉树，执行"右孩子变兄弟"的逆操作
- 左孩子不变，右孩子变成原节点的兄弟
举个例子，把刚才的森林二叉树转回去：
A
/
B
\
C
\
D
/
E
\
F
/
G
\
H第一步：断开A的右指针，得到三棵二叉树，根分别是A、D、F。
第二步：对每棵二叉树做逆转换。
第三步：恢复成原始森林。
我曾经踩过的坑：有一次做树形菜单的序列化，我直接把二叉树转回森林，结果发现节点顺序全乱了。后来才意识到，转换过程中兄弟节点的顺序是固定的，不能随意调整。所以，转换时一定要保持原顺序不变。
8.4 知识体系总览
下面这张图把树与森林的转换关系梳理清楚了：
8.5 代码实现要点
这里给出一段C语言的核心转换函数，我习惯用递归实现：
// 树节点结构
typedef struct TreeNode {
int data;
struct TreeNode* firstChild; // 第一个孩子
struct TreeNode* nextSibling; // 下一个兄弟
} TreeNode;
// 二叉树节点结构
typedef struct BiTreeNode {
int data;
struct BiTreeNode* left; // 左孩子
struct BiTreeNode* right; // 右孩子
} BiTreeNode;
// 树转二叉树
BiTreeNode* treeToBinary(TreeNode* root) {
if (root == NULL) return NULL;
BiTreeNode* bRoot = (BiTreeNode*)malloc(sizeof(BiTreeNode));
bRoot->data = root->data;
// 第一个孩子转左子树
bRoot->left = treeToBinary(root->firstChild);
// 下一个兄弟转右子树
bRoot->right = treeToBinary(root->nextSibling);
return bRoot;
}注意：这段代码虽然简洁，但有个隐藏问题——它假设了树节点中firstChild和nextSibling不会同时为NULL。实际项目中，我建议加上边界检查，防止野指针。
嗯，树与森林的转换就讲到这里。核心就是记住"左孩子右兄弟"这个口诀，剩下的都是这个规则的延伸应用。你在写代码时，多画几棵树手动转换一下，很快就能掌握。
公众号:蓝海资料掘金营，微信deep3321