树与二叉树

• 1: 树
• 2: 二叉树
• 3: 树的应用

# 树和二叉树

## 树的基本概念

## 二叉树

- 定义和主要特性
- 顺序存储结构和链式存储结构
- 遍历
- 线索二叉树的基本概念和构造

## 树、森林

- 树的存储结构
- 森林和二叉树的转化
- 树和森林的遍历

## 树和二叉树的应用

- 哈夫曼树和哈夫曼编码
- 并查集及其应用

1 - 树

树的基本概念

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

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

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

结点属性

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

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

度

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

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

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

深度

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

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

高度

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

按照这种定义：

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

路径

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

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

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

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

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

设叶子结点 $i$ 的权值为 $w_i$ ，从根结点到该叶子结点的路径长度为 $l_i$ ，则：

树的存储结构

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

双亲表示法

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

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

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

树和森林和二叉树的转换

树转二叉树

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

森林转二叉树

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

树和森林的遍历

树的遍历

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

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

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

至于 “中根遍历” 为什么树没有：中根遍历要求"先左子树，再根，再右子树"，这依赖于左右两个固定位置的子树。普通树的某个结点可能有 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。

观察可以得到如下结论：

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

森林的遍历

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

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

对于 上图 所示的森林：其 先根遍历 为 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

观察可以得到如下结论：

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

2 - 二叉树

二叉树存储结构

1. 链式存储结构：
   • 链式存储是最常见的二叉树存储方式。在链式存储中，每个节点都包含一个数据元素以及指向其左子树和右子树的指针。
   • 链式存储结构适用于表示任意形状和大小的二叉树，并且对于树的动态操作（插入、删除节点）非常方便。
2. 顺序存储结构（数组表示）：
   • 顺序存储结构使用数组来表示二叉树。通常，数组的索引与二叉树的节点之间存在特定的关系，例如，对于索引 $i$ 的节点，其左子节点在索引 $2i+1$ 处，右子节点在索引 $2i+2$ 处，父节点在索引 $(i-1)$ / $2$ 处。
   • 顺序存储结构通常用于堆数据结构（如二叉堆）的实现，其中对于堆的性质要求，使得数组表示变得非常有效。

链接存储

在 链接存储 中，我们需要在结构体中定义两个指针，分别指向二叉树左边的结点和右边的结点。

typedef struct TreeNode {
    ElementType data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

顺序存储

顺序存储表示用数组存储一颗树，如下图所示。

理解顺序存储的关键在于理解其 结点的隐式链接关系 以及 空指针的定义 这两点。

• 在顺序存储中，结点的链接关系由其下标指定：
  • 数组的下标从 1 开始的话，如果当前结点的下标为 $i$ ，那么其左结点的下标为 $2i$ ，右结点的下标为 $2i+1$ 。
  • 数组的下标从 0 开始的话，如果当前结点的下标为 $i$ ，那么其左结点的下标为 $2i+1$ ，右结点的下标为 $2i+2$ 。
• 通常采用一个特殊值来表示空指针，上图中采用 -1 表示空指针。

#define MAX_SIZE 100

int tree[MAX_SIZE];

int lchild(int i) {
    return tree[2 * i + 1];
})

int rchild(int i) {
    return tree[2 * i + 2];
}

顺序存储最常见于 堆排序 中。因为 堆是一棵完全二叉树。

• 对完全二叉树而言，顺序存储不会造成空间浪费；
• 父结点与子结点之间的关系可以直接通过下标计算得到（无需额外指针）；
• 堆排序过程中需要频繁地比较和交换父结点与子结点，数组下标运算能显著提升效率。

因此，堆排序天然适合采用顺序存储结构来实现。

特殊二叉树

特殊的二叉树 包含满二叉树、完全二叉树两种。

简单来说，满二叉树 必须每一层结点数都是满的， 完全二叉树 允许最后一层的最后几个结点为空。

满二叉树

满二叉树（Full Binary Tree）具备如下特点：

• 每个节点要么没有子节点，要么有两个子节点。
• 每一层都被完全填满。
• 第 $n$ 层的结点数量为 $2^n$ （这里假设根结点是第 $0$ 层）。
• 高度 为 $h$ 的满二叉树节点数目为 $2^h-1$ 。
• 结点数量为 $n$ 的满二叉树的高度为 ${\log }_2(n+1)$ 。

完全二叉树

完全二叉树（Complete Binary Tree）具备如下特点：

• 由满二叉树通过删除最后一层的一些节点而得到的。
• 除了最后一层外，所有其他层都是完全填满的，而且最后一层的节点都集中在左侧。
• 高度 为 $h$ 的完全二叉树的结点数量范围为 [ $2^{h-1}$ , $2^h-1$ ]。
• 结点数量为 $n$ 的完全二叉树的高度为 $\lceil {\log }_2(n+1)\rceil$ 。

遍历方式

DFS

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。

当使用 DFS 遍历二叉树中的结点时，算法会优先探索树的深度，直到达到最深的节点。 当达到叶子节点或无法继续深入时，算法会回溯返回到上一个节点，探索其他分支。

二叉树的深度优先（DFS）遍历方式包含前序、中序、后序遍历三种。 理解这三种遍历方式的关键在于理解其递归过程，不同方式的递归顺序不一样。 具体不同点如下表所示：

前序遍历

• 访问顺序：根节点 -> 左子树 -> 右子树
• 步骤：
  1. 访问根节点。
  2. 递归地进行前序遍历左子树。
  3. 递归地进行前序遍历右子树。

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // operation here
    preorderTraversal(root->left); // 遍历左子树
    preorderTraversal(root->right); // 遍历右子树
}

中序遍历

• 访问顺序：左子树 -> 根节点 -> 右子树
• 步骤：
  1. 递归地进行中序遍历左子树。
  2. 访问根节点。
  3. 递归地进行中序遍历右子树。

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    // operation here
    inorderTraversal(root->right); // 遍历右子树
}