1. 树形结构入门：从现实到代码

大家好，我是老刘。今天咱们聊聊树形结构。

说实话，我刚学数据结构那会儿，对树的感觉就是——这不就是递归吗？后来做项目多了才发现，树结构远比我当初想的要实用。你想想看，文件系统、网页DOM、编译器语法分析，哪个离得开树？

好，咱们正式开始。

1.1 树的定义

树是一种非线性的数据结构。它由 n（n≥0）个节点组成，节点之间有明确的层次关系。

专业定义是这样的：树是 n 个节点的有限集合。当 n=0 时，称为空树。当 n>0 时，有且仅有一个节点称为根节点，其余节点可以划分为 m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，称为子树。

嗯，这段话有点绕。我换个说法：

• 树有一个根，就像家族里的老祖宗
• 根下面可以分叉，每个分叉又是一棵小树
• 子树之间不能交叉，否则就成图了

1.2 树的基本术语

这些术语你早晚得背下来。我当年面试时就被问过「树的深度和高度有什么区别」，差点翻车。

术语	定义	我的理解
根节点	没有父节点的节点	一棵树只有一个根，就像公司只有一个CEO
叶子节点	没有子节点的节点	也叫终端节点，就是树的最末端
父节点/子节点	直接相连的上下层关系	父节点可以有多个子节点，但子节点只有一个父节点
兄弟节点	同一个父节点的子节点	它们之间是平级关系
度	节点拥有的子树个数	说白了就是有几个孩子。树的度是所有节点度的最大值
深度	从根节点到该节点的路径长度	根节点深度为1，往下每层+1
高度	从该节点到最远叶子节点的路径长度	叶子节点高度为1，往上每层+1
层	根节点在第1层，子节点在第2层，以此类推	树的深度 = 最大层数

1.3 树的存储结构

树怎么存到内存里？这是个好问题。数组？链表？还是两者结合？

我做过一个项目，需要存储组织架构树，当时选了双亲表示法。为什么？因为经常需要查某个人的上级是谁，这个操作要快。你看，选存储结构，关键看你的业务场景。

1.3.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;

优点：找父节点快，O(1) 时间。

缺点：找子节点慢，得遍历整个数组。

1.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;

优点：找子节点方便。

缺点：找父节点麻烦，得遍历所有链表。

我曾经在一个文件系统模拟项目里用过这个结构。当时需要快速遍历某个目录下的所有子文件，孩子表示法就很顺手。

1.3.3 孩子兄弟表示法

这个我最喜欢。它把一棵多叉树，用二叉树的方式存下来。

核心思想：每个节点存两个指针——firstChild 指向第一个孩子，nextSibling 指向下一个兄弟。

typedef struct CSNode {
    char data;
    struct CSNode *firstChild;   // 第一个孩子
    struct CSNode *nextSibling;  // 下一个兄弟
} CSNode, *CSTree;

你看，这个结构很巧妙。它把「树」变成了「二叉树」。后面我们学二叉树的各种操作，都可以直接套用过来。

1.4 三种存储结构对比

存储结构	找父节点	找子节点	空间开销	适用场景
双亲表示法	O(1)	O(n)	小	向上查找频繁
孩子表示法	O(n)	O(度)	中	向下遍历频繁
孩子兄弟表示法	O(n)	O(度)	中	需要转二叉树

1.5 知识体系总览

下面这张图，是我画的本章节知识结构。你可以把它当作一张地图，学完回头再看，会更有感觉。

1.6 避坑指南

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

• 「树」和「森林」别搞混。一棵树只有一个根，森林是多棵树的集合。但森林也能用孩子兄弟表示法转成一棵二叉树。
• 空树也是树。很多算法题里，空树是边界条件。我刚开始写递归时，经常忘记处理 n=0 的情况，结果段错误。
• 度不要算错。节点的度是子树的个数，不是子孙的总数。树的度是所有节点度的最大值。

---