树与森林的存储与转换
树和森林，说实话，在嵌入式里直接用的场景不算特别多。但你要是做文件系统、做菜单管理、做语法解析，这些东西就绕不过去了。我记得早年做一个小型RTOS的shell，命令树就是用孩子兄弟法存的——那会儿还没意识到这就是树转二叉树，纯粹觉得这样存省内存。
今天咱们就把这块彻底捋清楚。孩子兄弟表示法、树转二叉树、森林转二叉树，这三件事其实是一脉相承的。你搞懂了第一个，后面两个就是顺水推舟的事。
一、孩子兄弟表示法——树的“链表化”存储
树的常规存储方式有几种：双亲表示法、孩子表示法、孩子兄弟表示法。我个人最常用的是孩子兄弟法。为什么？因为它把一棵多叉树，硬生生变成了二叉树的结构。
每个节点只存两个指针：
- firstChild：指向第一个孩子
- nextSibling：指向下一个兄弟
你看，这不就是二叉树的左孩子右兄弟吗？
核心思想：用二叉树的存储结构，表达任意多叉树。每个节点只有两个“关系”——孩子和兄弟。
代码实现很简单：
// 孩子兄弟表示法的节点结构
typedef struct CSNode {
int data; // 数据域
struct CSNode *firstChild; // 第一个孩子
struct CSNode *nextSibling; // 下一个兄弟
} CSNode, *CSTree;我项目中遇到过一种情况：一个菜单系统，每个菜单项可能有子菜单，子菜单之间是平级的。用孩子兄弟法存，遍历起来特别顺手。先走firstChild进下一层，再走nextSibling遍历同级——逻辑清晰，代码也干净。
小技巧：如果你需要频繁访问某个节点的父节点，可以在结构体里再加一个parent指针。虽然破坏了“二叉树”的纯粹性，但工程上实用。
二、树与二叉树的转换——本质是视角切换
树转二叉树，说白了就是套用孩子兄弟法的思路。规则只有两条：
- 左指针指向第一个孩子
- 右指针指向下一个兄弟
转换后的二叉树，有什么特点？
- 根节点没有右子树（因为根没有兄弟）
- 左子树里全是原树的孩子们
- 二叉树的先序遍历 = 原树的先根遍历
- 二叉树的中序遍历 = 原树的后根遍历
嗯，这里要注意：中序遍历对应后根遍历，这个很多人会搞混。我刚开始学的时候也记反过，后来自己画了几棵树才彻底明白。
举个例子，一棵树：
A
/|\
B C D
|
E转换成二叉树后：
A
/
B
/ \
E C
\
D你看，A的右指针是空，B的右指针指向C，C的右指针指向D。E是B的左孩子。结构变了，但逻辑关系没丢。
注意：转换后的二叉树，和原来那棵树的“形状”完全不同。不要试图用二叉树的形态去理解原树的层次关系。转换只是存储方式的改变，不是逻辑结构的改变。
三、森林与二叉树的转换——多棵树拼成一棵
森林就是多棵树的集合。怎么转成二叉树？
规则也很简单：
- 先把每棵树各自转成二叉树（孩子兄弟法）
- 然后把每棵树的根节点，用右指针串起来
说白了，就是把森林里所有树的根节点，当成兄弟关系处理。
举个例子，森林有两棵树：
第一棵：A(B,C) 第二棵：D(E,F)转换后：
A
/ \
B D
/ / \
C E FA的右指针指向D，表示A和D是兄弟（属于不同树的根）。
反过来，二叉树转森林也简单：从根开始，一直往右走，每遇到一个右指针断开的地方，就是一棵新树的根。
一句话总结：树转二叉树看孩子兄弟，森林转二叉树看根节点串兄弟。
四、知识体系总览
下面这张图，把今天讲的核心逻辑串起来了。我建议你多看几遍，尤其是箭头方向——转换是双向的。
五、避坑指南与个人经验
我曾经在一个项目里，用孩子兄弟法存了一个多级菜单树。当时图省事，直接拿二叉树的前序遍历去还原菜单层级——结果顺序全乱了。后来才意识到，树转二叉树后，前序遍历对应的是原树的先根遍历，不是层次遍历。
还有一次，我在做森林转二叉树时，忘了把每棵树的根节点用右指针串起来。结果遍历时只拿到了第一棵树，后面的全丢了。调试了半天才发现是右指针没赋值。
我的建议：
- 写转换代码前，先在纸上画一遍。画清楚了再动手。
- 测试时用三棵树以上的森林，确保右指针串联逻辑正确。
- 如果内存紧张，孩子兄弟法比双亲表示法更省空间——每个节点只多两个指针。
好了，今天的内容就到这儿。孩子兄弟法是基础，树和森林的转换是应用。你只要把“左孩子右兄弟”这五个字刻在脑子里，后面怎么转都不会乱。