12. 树：从定义到存储，一次讲透
树这个结构，说实话，是很多程序员从「线性思维」转向「层次思维」的第一道坎。我记得自己刚学的时候，总觉得链表、数组用得好好的，干嘛要搞这么复杂？直到后来做文件系统解析，才真正体会到树的威力。
今天我们就来聊聊树。我会从定义讲起，再到术语，最后落到三种存储结构上。嗯，都是实战中经常碰到的。
12.1 树的定义
树是一种非线性的数据结构。它由 n（n≥0）个节点组成，节点之间有明确的层次关系。
专业定义是这样的：
- 有且仅有一个根节点
- 除根节点外，其余节点被分成 m（m≥0）个互不相交的子树
- 每个子树本身也是一棵树
说白了，就是「一个根，多个叉，层层往下分」。我在项目中遇到过最典型的例子——解析 XML 文档。XML 的标签嵌套，本质上就是一棵树。根标签是根节点，子标签是子树。
核心要点：树的定义是递归的。子树本身也是树，这意味着很多树的操作天然适合用递归实现。
12.2 树的基本术语
这些术语我建议你记牢。因为后面讲二叉树、平衡树、B树，都会用到。我当年面试时，就被问过「树的度和图的度有什么区别」——嗯，当时答得不太好。
| 术语 | 含义 | 我的理解 |
|---|---|---|
| 根节点 | 没有父节点的节点 | 整棵树的起点 |
| 叶子节点 | 没有子节点的节点 | 树的末端，度为0 |
| 父节点/子节点 | 直接上下层关系 | 一对一的关系 |
| 兄弟节点 | 同一个父节点的子节点 | 平级关系 |
| 节点的度 | 节点拥有的子树个数 | 有几个孩子 |
| 树的度 | 所有节点中最大的度 | 最「能生」的那个节点 |
| 深度/高度 | 从根到最远叶子的层数 | 树的层数，根为第1层 |
| 森林 | m棵互不相交的树 | 去掉根节点，剩下的就是森林 |
小技巧：判断一个节点是不是叶子，就看它的度是否为0。我在写树遍历时，经常用这个条件作为递归终止。
12.3 树的存储结构
树怎么存到内存里？这是个好问题。数组？链表？还是两者结合？
实际上，三种主流方案各有优劣。我分别讲一下。
12.3.1 双亲表示法
思路很简单：每个节点只存自己的数据和父节点的位置（下标）。
你想想看，这就像每个人都知道自己爸爸是谁，但不知道孩子是谁。适合什么场景？找父节点非常快，O(1) 就能找到。但找子节点？得遍历整个数组。
#define MAX_TREE_SIZE 100
typedef struct {
char data; // 节点数据
int parent; // 父节点下标，-1表示根
} PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int r, n; // 根的位置和节点数
} PTree;注意：双亲表示法下，删除一个节点时，要小心处理它的子节点。我曾经在写一个树形菜单时，忘了更新子节点的 parent 字段，结果整个树结构乱了——排查了半天。
12.3.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;我个人习惯在需要频繁遍历子树的场景用孩子表示法。比如渲染一个树形组件，从根往下递归，孩子表示法就非常自然。
12.3.3 孩子兄弟表示法
这个方案我觉得最巧妙。它用二叉链表来表示任意树。每个节点只有两个指针：
- firstChild：指向第一个孩子
- nextSibling：指向下一个兄弟
这样一来，任何一棵树都能转成二叉树。你想想看，是不是很神奇？
typedef struct CSNode {
char data; // 节点数据
struct CSNode *firstChild; // 第一个孩子
struct CSNode *nextSibling;// 下一个兄弟
} CSNode, *CSTree;为什么说它重要？因为这种结构把「多叉」转成了「二叉」。而二叉树的操作，我们有很多成熟的算法。比如遍历、查找、插入，都能复用二叉树的套路。
我在做文件系统遍历时就用过这个结构。每个目录节点，firstChild 指向第一个子文件/目录，nextSibling 指向同级的下一个。写递归遍历时，逻辑非常清晰。
12.4 三种存储结构对比
| 存储方式 | 找父节点 | 找子节点 | 空间开销 | 适用场景 |
|---|---|---|---|---|
| 双亲表示法 | O(1) | O(n) | 小 | 频繁找父节点 |
| 孩子表示法 | O(n) | O(度) | 中 | 频繁遍历子树 |
| 孩子兄弟表示法 | 较慢 | O(度) | 小 | 通用，可转二叉树 |
12.5 知识体系总览
下面这张图，我把本章的核心知识点串了起来。你可以用它来快速回顾。
嗯，树的内容就讲到这里。三种存储结构各有千秋，没有绝对的好坏。关键看你需要频繁做什么操作——找父节点？遍历子树？还是希望结构通用？选对了，代码写起来会顺手很多。
我的建议：初学者先从孩子兄弟表示法入手。因为它和二叉树打通了，后续学二叉树的遍历、查找、平衡，都能直接迁移。我自己做项目时，90% 的树结构都用这种表示法。
公众号：蓝海资料掘金营，微信 deep3321