第十二章：树与森林——从存储到遍历的完整攻略
树结构，说实话，是很多C语言学习者的一道坎。我记得刚入行那会儿，第一次看到树的递归遍历代码，整个人都是懵的。但后来在实际项目中，无论是文件系统解析、语法树构建，还是路由表查找，树结构几乎无处不在。今天我们就来彻底搞定树与森林的存储、转换和遍历。
12.1 树的三种存储结构
树在内存里怎么存？这个问题我当年也纠结过。其实核心就三个思路：存爹、存儿子、存兄弟。我们一个个来看。
12.1.1 双亲表示法
说白了，就是每个节点只记住自己的父节点是谁。这种结构特别适合“找爹”频繁的场景。
#define MAX_TREE_SIZE 100
typedef struct {
char data; // 节点数据
int parent; // 父节点下标（-1表示根）
} PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int root; // 根节点位置
int n; // 节点数
} PTree;我的经验：双亲表示法在并查集算法里特别好用。我曾经写一个社交网络的好友圈检测，就是用这个结构实现的。找两个节点的公共祖先，时间复杂度O(n)，代码还特别简洁。
优点很明显：找父节点O(1)。缺点？找孩子得遍历整个数组，O(n)。所以它适合“向上查”多的场景。
12.1.2 孩子表示法
每个节点挂一个链表，链表里存它的所有孩子。这就像每个爹都记着自家娃的名单。
typedef struct ChildNode {
int child; // 孩子节点下标
struct ChildNode *next; // 下一个孩子
} ChildNode;
typedef struct {
char data;
ChildNode *firstChild; // 第一个孩子
} CTNode;
typedef struct {
CTNode nodes[MAX_TREE_SIZE];
int root, n;
} CTree;核心要点：孩子表示法找孩子很快，但找爹就麻烦了。实际项目中，我经常把双亲和孩子两种表示法结合起来用——每个节点既存parent下标，又挂孩子链表。空间换时间，值不值看你需求。
12.1.3 孩子兄弟表示法（重点）
这个厉害了。每个节点只存两个指针：firstChild（第一个孩子）和nextSibling（下一个兄弟）。你看，任意一棵树都能用这种“二叉树”的形式存下来。
typedef struct CSNode {
char data;
struct CSNode *firstChild; // 第一个孩子
struct CSNode *nextSibling; // 下一个兄弟
} CSNode, *CSTree;为什么说它是重点？因为这种结构天然支持树与二叉树的互相转换。我当年做编译器前端时，语法分析树就是用孩子兄弟表示法存的，后续遍历、转换都特别顺手。
避坑指南：我曾经在项目里把firstChild和nextSibling搞反了，结果遍历出来的树结构完全错乱。调试了整整一个下午。记住：firstChild指向的是“垂直方向”的孩子，nextSibling指向的是“水平方向”的兄弟。
12.2 森林与二叉树的转换
森林就是多棵树的集合。为什么要转成二叉树？因为二叉树的遍历、查找算法太成熟了，我们想把森林的问题转化成二叉树的问题来解决。
12.2.1 森林→二叉树
转换规则其实就三步：
- 每棵树按孩子兄弟表示法转成二叉树
- 每棵树的根节点视为兄弟
- 把后一棵树的根作为前一棵树根的右孩子
说白了，就是把森林里所有树的根节点，用右指针串成一个链表。
// 森林转二叉树（递归实现）
CSTree ForestToBinary(CSTree forest[], int n) {
if (n == 0) return NULL;
CSTree root = forest[0];
CSTree p = root;
for (int i = 1; i < n; i++) {
p->nextSibling = forest[i];
p = p->nextSibling;
}
return root;
}12.2.2 二叉树→森林
反过来也一样简单：
- 根节点没有右孩子？那它就是一棵树
- 不断把根节点的右链断开，每断开一次就得到一棵新树的根
- 每棵树内部再按孩子兄弟规则还原
我个人的习惯：做转换时，先在纸上画图。画清楚指针怎么指，再写代码。你想想看，指针指错了，debug的时间比写代码的时间长多了。
12.3 树与森林的遍历
遍历是树操作的基础。树的遍历和二叉树的遍历有对应关系，理解了这一点，很多问题就迎刃而解。
12.3.1 树的遍历
树有两种基本遍历方式：
| 遍历方式 | 顺序 | 对应二叉树遍历 |
|---|---|---|
| 先根遍历 | 先访问根，再依次遍历每个子树 | 先序遍历 |
| 后根遍历 | 先依次遍历每个子树，再访问根 | 中序遍历 |
注意这个对应关系：树的后根遍历 ≠ 二叉树的后序遍历。这是很多初学者容易搞混的地方。
// 树的先根遍历（孩子兄弟表示法）
void PreOrderTree(CSTree T) {
if (T == NULL) return;
printf("%c ", T->data); // 访问根
PreOrderTree(T->firstChild); // 遍历第一个孩子
PreOrderTree(T->nextSibling); // 遍历兄弟
}12.3.2 森林的遍历
森林的遍历分两种：
- 先序遍历森林：先访问第一棵树的根，再遍历第一棵树的子树森林，最后遍历剩下的树
- 中序遍历森林：先遍历第一棵树的子树森林，再访问第一棵树的根，最后遍历剩下的树
你发现没有？森林的先序遍历，其实就是对应二叉树的先序遍历。森林的中序遍历，对应二叉树的中序遍历。这就是为什么我们费劲把森林转成二叉树——遍历算法可以直接复用。
实战经验：我在做一个文件系统差异对比工具时，就用到了森林遍历。把两个目录结构分别建成森林，转成二叉树后做同步遍历，差异点一目了然。代码量不到200行，效率还特别高。
12.4 知识体系总览
下面这张图，把本章的核心知识点串起来了。建议你保存下来，复习时对照着看。
12.5 避坑与实战建议
最后，分享几个我这些年踩过的坑：
- 递归深度：树的递归遍历，如果树特别深（比如上千层），小心栈溢出。我遇到过生产环境因为这个崩溃的。解决方案？改成非递归的迭代版本，或者增大栈空间。
- 指针野了：孩子兄弟表示法里，每个节点有两个指针。释放内存时一定要先递归释放孩子，再释放兄弟，最后释放自己。顺序错了就内存泄漏。
- 转换别想当然：森林转二叉树后，原来的“兄弟”关系变成了“右孩子”关系。遍历时别用二叉树的左右孩子概念去套，要时刻记住：左孩子是原来的第一个孩子，右孩子是原来的兄弟。
一句话总结：树与森林的核心，就是孩子兄弟表示法。搞懂了它，存储、转换、遍历全通了。我当年面试时，面试官问树的问题，我都是先画孩子兄弟表示法，再展开讲，基本没失手过。
公众号:蓝海资料掘金营，微信deep3321