树

🔥 高优先级

树和图每年都是必考，这一节每个知识点都十分重要。

树的基本概念

树（Tree）是一种具有层次关系的数据结构。树由若干个结点组成，当树非空时：

有且仅有一个特殊的结点称为 根结点（Root）；
除根结点外，其余结点都可以划分为若干个互不相交的集合，每个集合本身又是一棵树，称为根结点的子树（Subtree）。

补充

从图论的角度来说，树是连通且无环的有向图，其中：

存在唯一一个入度为 0 的结点（根）；
除根外，其余结点入度均为 1；
从根到任意结点有且仅有一条路径。

树具有明显的层次结构。通常将根结点画在最上方，根的孩子位于下一层，并依次向下展开。

结点属性

对于树中的结点，可以根据它们之间的层次关系定义以下概念：

根结点（root）：树中没有双亲的结点，一棵非空树有且仅有一个根结点。
双亲（parent）：如果结点 A 直接连接到下一层的结点 B，则 A 是 B 的双亲。
孩子（child）：如果 A 是 B 的双亲，则 B 是 A 的孩子。
兄弟（sibling）：具有相同双亲的结点互称为兄弟。
祖先（ancestor）：从根结点到某结点的路径上，除该结点自身以外的所有结点，都是该结点的祖先。
子孙（descendant）：某结点的孩子，以及这些孩子的孩子等，都称为该结点的子孙。

度

结点拥有的 孩子数量 称为该结点的度。

结点的度：该结点的孩子数量。
树的度：树中所有结点的度的最大值。
分支结点（非终端结点）：度大于 0 的结点。
叶子结点（终端结点）：度等于 0 的结点。

例如，一个结点有 3 个孩子，则该结点的度为 3；如果整棵树中不存在度大于 3 的结点，那么这棵树的度就是 3。

补充

需要注意区分 结点的度 和 图中顶点的度：

在树中，结点的度通常指 孩子的数量；
在无向图中，顶点的度指 与该顶点关联的边数。

因此，对于树中的非根结点，其作为无向图顶点时的度通常等于：

孩子数量 + 1

多出的 1 对应它与双亲之间的边。

深度

结点的深度（Depth）：从根结点到该结点所经过的 结点总数。
树的深度：树中所有结点深度的最大值，也就是从根结点到最远叶子结点所经过的 结点总数。

按照这种定义，根结点的深度为 1。

补充

深度描述的是 从上往下 的距离，而高度描述的是 从下往上 的距离。

对于整棵树而言：

树的高度 = 树的深度

但是对于某一个具体结点而言，结点的高度和深度通常不同。

高度

结点的高度（Height）：从该结点到其最远叶子结点所经过的 结点总数。
树的高度：根结点的高度，也就是从根结点到最远叶子结点所经过的 结点总数。

按照这种定义：

叶子结点的高度为 1；
根结点的高度等于整棵树的高度。

注意

树的高度存在两种常见定义，需要注意区分：

从某结点到最远叶子结点经过的 结点总数；
从某结点到最远叶子结点经过的边数。

两种定义的结果相差 1。

408 中通常按照第一种方式考查，即：

根结点的深度为 1；
叶子结点的高度为 1。

例如 2020 年第 3 题就采用这种定义，因此在 408 学习和考试中建议按照第一种定义记忆。

路径

树中任意两个结点之间都存在且仅存在一条路径。

路径：从一个结点到另一个结点依次经过的结点所构成的序列。
路径长度：一条路径上经过的 边的数量。

例如路径 A → B → D 经过 3 个结点，但包含 2 条边，因此 路径长度为 2。

注意

需要特别注意 路径上的结点数 和 路径长度 的区别：

路径长度 = 路径上的结点数 - 1

例如，按照前面的定义，一个第 4 层结点的深度为 4，但从根结点到它的路径长度为 3。

带权路径长度

在一些树中，可以为结点赋予一定的权值。

结点的权：赋予结点的数值，通常用于表示该结点的重要性、出现频率等。
结点的带权路径长度：从根结点到该结点的 路径长度 与该结点权值的乘积。
树的带权路径长度（WPL）：树中 所有叶子结点 的带权路径长度之和。

设叶子结点 $i$ 的权值为 $w_{i}$ ，从根结点到该叶子结点的路径长度为 $l_{i}$ ，则：

W P L = i \sum w_{i} l_{i}

补充

这里的 $l_{i}$ 是 路径上的边数，而不是结点数。

例如，一个叶子结点位于第 4 层，则按照前面的定义它的深度为 4，但从根结点到它的路径长度为 3。

带权路径长度是后面学习 哈夫曼树 的重要基础。哈夫曼树的核心目标就是构造一棵使 WPL 最小的二叉树。

树的存储结构

树的 存储结构 是指在计算机中如何表示和存储树这种数据结构，这里主要了解 双亲表示法、孩子表示法 和 孩子兄弟表示法 即可。

双亲表示法

双亲表示法 主要是使用一个数组，其中每个结点都有一个指示其双亲结点在数组中位置的索引。

#define MAXSIZE 100
typedef struct {
    int data;         // 结点数据
    int parent;       // 双亲的位置
} PTNode;

typedef struct {
    PTNode nodes[MAXSIZE];  // 结点数组
    int n;                  // 结点数
} PTree;

孩子表示法

孩子表示法 将每个结点的孩子结点排列起来，以单链表作为存储结构。然后再用一个数组与之相配合。

#define MAXSIZE 100

// 孩子结点
typedef struct ChildNode {
    int child;                   // 孩子结点在数组中的位置
    struct ChildNode* next;     // 下一个孩子
} *ChildPtr;

// 表头结构
typedef struct {
    int data;                   // 结点数据
    ChildPtr firstchild;        // 第一个孩子的指针
} CTBox;

typedef struct {
    CTBox nodes[MAXSIZE];       // 结点数组
    int n;                      // 结点数
} CTree;

孩子兄弟表示法

孩子兄弟表示法 是将树转化为 二叉树 的形式来存储。每个结点有两个指针，一个指向它的第一个孩子，另一个指向它的右兄弟。

typedef struct CSNode {
    int data;                     // 结点数据
    struct CSNode* firstchild;   // 第一个孩子
    struct CSNode* rightsib;     // 右兄弟
} CSNode, *CSTree;

森林的基本概念

森林（Forest）是一组互不相交的树的集合。换句话说，森林由若干棵树组成，每棵树都是一个独立的层次结构，且这些树之间没有连接关系。

森林与树的区别：
- 一棵树只有一个 根结点，而森林可以有多个 根结点（每棵树一个）。
- 森林可以看作是多个树的并集，树是森林的一个特例（森林中只有一棵树）。
森林的高度：森林中所有树的最大高度（从根到最远叶结点的路径长度）。

树和森林和二叉树的转换

树转二叉树

若树的根结点有孩子，那么第一个孩子是 二叉树 的左孩子，其他的孩子结点依次作为前一个孩子结点的右孩子。
对每个孩子执行上述步骤。

森林转二叉树

把森林中的每一棵树转换为 二叉树。
第一棵二叉树不动，从第二棵二叉树开始，依次将后一棵二叉树的根作为前一棵二叉树的右孩子。其结果是一个 二叉树。

树和森林的遍历

树的遍历

对于一个给定的树，通常有以下两种遍历方式：

先根遍历（类似于二叉树的前序遍历）：
- 访问树的根结点。
- 递归地 先根遍历 根的每一棵子树。
后根遍历（类似于二叉树的后序遍历）：
- 递归地 后根遍历 根的每一棵子树。
- 访问树的根结点。

注意树是没有 中根遍历 的，除非这棵树是二叉树。

至于 “中根遍历” 为什么树没有：中根遍历要求"先左子树，再根，再右子树"，这依赖于左右两个固定位置的子树。普通树的某个结点可能有 0 个、1 个、3 个甚至更多子树，没有"左右"这种二分结构，所以无法定义"根在中间"访问的规则。

#define MAXCHILD 20

typedef struct TreeNode {
    int value;
    int numChildren; // 子结点的数量
    struct TreeNode *children[MAXCHILD]; // 子结点指针数组
} TreeNode;

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->value);  // 先访问根结点
    // 然后遍历子结点
    for (int i = 0; i < root->numChildren; ++i) {
        preOrderTraversal(root->children[i]);
    }
}

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    // 先遍历子结点
    for (int i = 0; i < root->numChildren; ++i) {
        postOrderTraversal(root->children[i]);
    }
    printf("%d ", root->value);  // 再访问根结点
}

对于上图所示的树：其 先根遍历 为 A, B, E, F, C, D, G，后根遍历 为E, F, B, C, G, D, A。

观察可以得到如下结论：

树的 先根遍历 和其对应的二叉树的 先序遍历 相同
树的 后根遍历 和其对应的二叉树的 中序遍历 相同

森林的遍历

对于一个给定的森林，遍历方式如下：

先根遍历（与树的先根遍历相似）：依次 先根遍历 森林中的每一棵树。
后根遍历（与树的后根遍历相似）：依次 后根遍历 森林中的每一棵树。
中根遍历（普通的树构成的森林是不存在中序遍历的，这里的中序遍历指代的是 二叉树森林）：依次 中根遍历 森林中的每一棵二叉树。

对于上图所示的森林：其 先根遍历 为 A, B, C, D, E, F, G, H, I，后根遍历 为 B, C, D, A, F, E, H, I, G，中根遍历 为 B, C, D, A, F, E, H, I, G

观察可以得到如下结论：

森林的 先根遍历 和其对应的二叉树的 先序遍历 相同
森林的 中根遍历 和其对应的二叉树的 中序遍历 相同