树的基本概念：从线性到非线性的跨越

说实话，我刚开始学数据结构时，对树这个结构挺抗拒的。之前一直在跟数组、链表这些线性结构打交道，突然冒出来一个分叉的东西，脑子有点转不过弯。但后来在实际项目中——比如做文件系统解析、菜单树管理——才发现树结构无处不在。今天我们就来聊聊树的基本概念，把它的定义、术语、存储方式和遍历方法理清楚。

树的定义与术语

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

树的核心特征是什么？我总结了两点：

• 每个节点有零个或多个子节点
• 除了根节点外，每个节点有且仅有一个父节点

嗯，说白了就是——不能有环路，不能出现「我爸爸是我儿子」这种荒唐事。

常用术语一览

这些术语你迟早要背下来，我当年面试就被问过「树的深度和高度有什么区别」这种问题。

术语	含义	举个栗子
根节点	没有父节点的节点	公司的CEO
叶子节点	没有子节点的节点	基层员工
父节点/子节点	直接上下级关系	部门经理和组员
兄弟节点	同一个父节点的子节点	同部门的同事
祖先/子孙	向上/向下的所有节点	爷爷和孙子
深度	从根到该节点的路径长度	根深度为0
高度	从该节点到最远叶子的路径长度	叶子高度为0
度	节点拥有的子树个数	二叉树度≤2

树的存储结构

树在内存里怎么存？这是个好问题。我早期做嵌入式菜单系统时，就踩过存储结构的坑。下面三种是主流方案。

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;

我在项目中用过这个方案做设备树解析。优点是简单，缺点是找孩子得遍历整个数组。

2. 孩子表示法

每个节点维护一个孩子链表。适合频繁遍历子节点的场景。

typedef struct ChildNode {
    int childIndex;
    struct ChildNode *next;
} ChildNode;

typedef struct {
    char data;
    ChildNode *firstChild;
} CTNode;

typedef struct {
    CTNode nodes[MAX_TREE_SIZE];
    int r, n;
} CTree;

3. 孩子兄弟表示法（最常用）

每个节点存两个指针：指向第一个孩子，指向下一个兄弟。说白了就是把多叉树转成二叉树来存。

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

我个人最喜欢这种。为什么？因为它统一了树的存储形式，而且很多树的操作算法都可以复用二叉树的套路。你想想看，是不是很巧妙？

树的遍历

遍历树，说白了就是把所有节点按某种顺序访问一遍。常用的有四种：

• 先序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右
• 后序遍历：左 → 右 → 根
• 层序遍历：从上到下，从左到右

我举个例子，假设有这样一棵树：

      A
     / \
    B   C
   / \
  D   E

四种遍历结果分别是：

• 先序：A B D E C
• 中序：D B E A C
• 后序：D E B C A
• 层序：A B C D E

知识体系总览

下面这张图把树的核心知识点串起来了，你可以对照着复习。

总结一下

树这个结构，说白了就是「一对多」的关系。理解它的关键就三点：

1. 术语要记牢——深度、高度、度这些基础概念，面试笔试常考
2. 存储选型看场景——频繁找父节点用双亲法，频繁遍历孩子用孩子法，通用场景用孩子兄弟法
3. 遍历递归要小心——递归写法简洁，但别忘了终止条件和栈深度

我在实际项目中，用得最多的还是孩子兄弟表示法。它把多叉树转成二叉树，很多现成的二叉树算法直接拿来用，省了不少事。嗯，今天就聊到这儿，你先把这些基础概念消化掉，后面我们再看具体怎么用代码实现。

---