17. 树与森林：存储、转换与遍历

树和森林，说实话，是很多初学者从线性结构迈向非线性结构的第一个坎。我记得自己刚学那会儿，总觉得“森林”这个概念有点多余——不就是几棵树嘛？后来在项目中处理文件系统目录树的时候，才真正体会到，把多棵树统一管理起来，是多么实用的需求。

这一章，我会带你从树的存储结构讲起，再到森林与二叉树的转换，最后聊聊遍历。嗯，内容不少，但都是硬核干货。

17.1 树的存储结构

树在内存里怎么存？这是个经典问题。因为每个节点的孩子数量不固定，所以不能像数组那样简单连续存储。我个人习惯把存储结构分成三类：双亲表示法、孩子表示法和孩子兄弟表示法。每种都有它的适用场景。

17.1.1 双亲表示法

说白了，就是每个节点只存它的父节点是谁。用一个数组，每个元素包含数据域和父节点下标。

#define MAX_TREE_SIZE 100

typedef struct {
    char data;        // 节点数据
    int parent;       // 父节点下标
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;         // 根位置和节点数
} PTree;

这种结构找父节点很快，O(1) 就能搞定。但找孩子呢？得遍历整个数组。我在项目中处理过组织架构树，当时就用双亲表示法——因为业务场景里经常要查“这个人的上级是谁”，很少需要知道“谁是他下属”。

17.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 r, n;
} CTree;

找孩子很快，但找父节点就麻烦了。你想想看，如果我要查某个节点的父节点，得遍历所有节点的孩子链表——这效率，嗯，不太行。

17.1.3 孩子兄弟表示法（重点）

这个方法很巧妙。每个节点只存两个指针：第一个孩子和下一个兄弟。这样一来，任何一棵普通的树，都能用二叉树的形式存下来。

typedef struct CSNode {
    char data;
    struct CSNode *firstChild, *nextSibling;
} CSNode, *CSTree;

你看，这个结构跟二叉链表几乎一模一样。只是左指针指向孩子，右指针指向兄弟。我个人觉得，这是最优雅的树存储方式——因为它为后面的“树转二叉树”铺平了道路。

17.2 森林与二叉树的转换

为什么要转换？因为二叉树的算法更成熟、更简单。你想想看，遍历、查找、插入，二叉树的代码写起来多顺手。所以把森林转成二叉树，本质上是在“借用”二叉树的处理能力。

17.2.1 树 → 二叉树

规则很简单：

• 每个节点的左指针指向它的第一个孩子
• 每个节点的右指针指向它的下一个兄弟

说白了，就是“左孩子右兄弟”。我刚开始学的时候，总觉得这个转换会丢失信息。后来写代码验证才发现——不会。因为兄弟关系被右指针保留了，孩子关系被左指针保留了，整棵树的结构信息一点没丢。

17.2.2 森林 → 二叉树

森林是多棵树。转换时，先把每棵树转成二叉树，然后把后一棵树的根作为前一棵树根的右孩子。嗯，就像把几棵树的根用右指针串起来。

// 森林转二叉树的伪代码
CSTree ForestToBinaryTree(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;
}

17.2.3 二叉树 → 森林

反过来也一样。从根开始，把右指针指向的节点都拆出来，每个节点作为一棵新树的根。然后对每棵树，左指针指向的是孩子，右指针指向的是兄弟——按这个规则还原即可。

我曾经在做一个文件系统模拟器时，就用这个转换把多级目录（森林）转成二叉树，然后用二叉树的遍历算法做目录搜索。效果很好，代码量也少。

17.3 树与森林的遍历

遍历，说白了就是按某种顺序把每个节点访问一遍。树的遍历和二叉树的遍历有相似之处，但也有区别。

17.3.1 树的遍历

树有两种基本遍历方式：

• 先根遍历：先访问根，再依次遍历每个子树
• 后根遍历：先依次遍历每个子树，再访问根

注意，树没有中序遍历——因为树的孩子数量不固定，没有“左中右”这种概念。

// 树的先根遍历（孩子兄弟表示法）
void PreOrderTree(CSTree T) {
    if (T == NULL) return;
    printf("%c ", T->data);          // 访问根
    PreOrderTree(T->firstChild);     // 遍历第一个孩子的子树
    PreOrderTree(T->nextSibling);    // 遍历兄弟
}

你发现没有？这个代码跟二叉树的先序遍历几乎一样。这就是孩子兄弟表示法的威力——把树的遍历统一成了二叉树的遍历。

17.3.2 森林的遍历

森林的遍历分两种：

• 先序遍历森林：先访问第一棵树的根，再遍历第一棵树的子树森林，再遍历剩下的树
• 中序遍历森林：先遍历第一棵树的子树森林，再访问第一棵树的根，再遍历剩下的树

嗯，这里要注意：森林的中序遍历，对应到二叉树上就是中序遍历。因为森林转二叉树后，左子树是孩子，右子树是兄弟——中序遍历正好是先左、再根、再右。

17.4 知识体系图

下面这张图，是我梳理的本章知识结构。你可以把它当作复习提纲。

17.5 避坑指南

最后，分享几个我踩过的坑：

• 混淆“孩子”和“兄弟”：我曾经在写转换代码时，把左指针指向了兄弟，右指针指向了孩子。结果遍历出来全乱套了。记住：左孩子，右兄弟。
• 忘记处理空树：递归遍历时，一定要先判空。我刚开始写代码时经常漏掉这个，导致段错误。
• 森林转二叉树后根节点有右子树？不会。因为所有树的根通过右指针串成兄弟链，所以根节点一定有右子树——除非森林只有一棵树。

嗯，这一章的内容就到这里。树和森林的存储与转换，是后续学习图、并查集等结构的基础。把这一章吃透，后面的路会顺很多。

---

公众号:蓝海资料掘金营，微信deep3321