树与二叉树

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

# 树和二叉树

## 树的基本概念

## 二叉树

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

## 树、森林

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

## 树和二叉树的应用

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

1 - 树

基本概念

结点属性

• 双亲（parent）：如果一个结点包含子结点，则该结点被称为其子结点的双亲。
• 兄弟（sibling）：具有相同双亲结点的结点互称为兄弟结点。
• 孩子（child）：一个结点直接连接到另一个结点，并且位于较低的层级，则该结点被称为子结点或孩子。

度

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

深度

• 树的深度（Depth）：从根结点到最远叶子结点的最长路径上的边的数量。
• 结点的深度：是指从根结点到该结点的路径长度。

高度

• 树的高度（Height）：从根结点到最远叶子结点的最长路径上的边的数量。
• 结点的高度：从该结点到其最远叶子结点的最长路径上的边的数量。

路径

• 路径： 在一棵树中，从一个结点到另一个结点所经过的所有结点，被称为这两个结点之间的路径。
• 结点的权： 每个结点被赋予的一个数值，通常表示该结点的重要性或频率。
• 结点的带权路径长度： 从根结点到该结点的路径长度与该结点权值的乘积。
• 树的带权路径长度： 所有叶子结点的带权路径长度之和。

树的存储结构

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

双亲表示法

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

#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;

树、森林和二叉树的转换

树转化为二叉树

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

森林转二叉树

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

树和森林的遍历

树的遍历

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

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

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

• 树结点定义
• 先根遍历
• 后根遍历

#define MAXCHILD 20

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

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 先访问根结点
    // 然后遍历子结点
    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]);
    }
    // 然后访问根结点
}

对于上图所示的树：其先根遍历为 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 index) {
    return tree[2 * i + 1];
})

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

顺序存储最常见于 堆排序 中。

特殊二叉树

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

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

满二叉树

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

• 每个节点要么没有子节点，要么有两个子节点。
• 每一层都被完全填满。
• 第 $n$ 层的结点数量为 $2^n$。
• 高度为 $h$ 的满二叉树节点数目为 $2^{h+1} - 1$。

完全二叉树

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

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

遍历方式

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); // 遍历右子树
}

后序遍历

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

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

BFS

二叉树的层次遍历（Level Order Traversal），也称为广度优先搜索（Breadth-First Search，BFS），是一种从上到下、从左到右逐层访问二叉树节点的方法。

BFS 算法从根节点开始，逐层访问节点。同一层级的节点按照从左到右的顺序访问。

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

    struct Queue* queue = createQueue();
    enqueue(queue, root);

    while (queue->front != NULL) {
        struct TreeNode* current = dequeue(queue);
        // operation here

        if (current->left != NULL) {
            enqueue(queue, current->left);
        }

        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
}

线索二叉树

线索二叉树（Threaded Binary Tree）是一种对普通二叉树进行优化的数据结构。它的主要目的是在二叉树上添加一些线索（thread），使得在遍历树的过程中可以更加高效地找到前驱和后继节点。线索二叉树在某些应用中能够提高对树的遍历性能，尤其是中序遍历。

线索二叉树中的每个节点都可以包含以下线索信息：

• 前驱线索（Inorder Predecessor Thread）： 如果节点有左子树为空，那么它的左子树指针可以指向其前驱节点，即在中序遍历中位于它之前的节点。
• 后继线索（Inorder Successor Thread）： 如果节点有右子树为空，那么它的右子树指针可以指向其后继节点，即在中序遍历中位于它之后的节点。

线索二叉树的主要优点是，在不使用递归或栈的情况下，可以通过线索信息直接找到下一个要访问的节点，从而提高了中序遍历的效率。这对于需要频繁进行中序遍历的应用非常有用，例如数据库中的 B 树和 AVL 树的实现。

• 节点存储结构
• 遍历

// ltag = 0 时表示 lchild 域指向节点的左孩子，ltag = 1 时表示 lchild 域指向节点的前驱
// rtag = 0 时表示 rchild 域指向节点的右孩子，rtag = 1 时表示 rchild 域指向节点的后继
typedef struct ThreadNode {
    ElementType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
} ThreadNode;

// 中序遍历，找到中序遍历的第一个节点，然后遍历 rchild 即可
void InOrder(ThreadNode *n) {
    ThreadNode *p = n;
    while (p->lchild) {
        p = p->lchild;
    }
    for (; p != NULL; p = p->rchild) {
        visit(p);
    }
}

二叉树构建

已知二叉树，可以获得其前序、中序和后序遍历序列。

反之，给定二叉树的遍历序列，可以通过以下两种方式重建其二叉树结构：

1. 带空指针的单序列重建：给定包含空指针信息的单一遍历序列（如带空指针的前序遍历），可以唯一确定二叉树的结构。
2. 双序列组合重建：给定两种不同的遍历序列组合，可以唯一确定二叉树的结构。

带空指针的单序列

在二叉树的遍历序列中，明确地标记出空节点（通常用特定的符号，如“#”或“NULL”表示），可以使得单一的遍历序列足以唯一确定二叉树的结构。

常规的前序、中序或后序遍历，如果二叉树中存在空节点，则这些空节点的信息会丢失。 因此，单一的常规遍历序列无法区分某些二叉树的结构。

假设有如下二叉树：

     1
    / \
  2    3
 / \   /
4   # #

那么他的带空指针的前序遍历序列为：1 2 4 # # # 3 # #

重建步骤如下：

1. 从序列的第一个元素开始，创建根节点。
2. 读取下一个元素，如果不是空节点，则创建当前节点的左子节点，并递归地处理左子树。
3. 如果遇到空节点，则表示当前子树为空，返回。
4. 处理完左子树后，读取下一个元素，创建当前节点的右子节点，并递归地处理右子树。
5. 重复上述步骤，直到序列结束。

上述过程的 C 代码实现如下所示：

TreeNode *createTree(char a[], int *i) {
    if (a[i] == '#') {
        return NULL;
    }
    TreeNode *cur = new TreeNode(a[i]);
    *i = *i + 1;
    cur->left = createTree(a, i);
    cur->right = createTree(a, i);
}

双序列组合重建

从前序、中序、后序序列中选两个构造二叉树，有两种方式：

1. 前序 + 中序：这是最常见的组合，因为前序确定了根节点的位置，而中序则可以区分哪些节点在左子树，哪些在右子树。有了这两个信息，就可以唯一确定一棵二叉树。
2. 后序 + 中序：后序确定了根节点的位置（它是后序遍历的最后一个节点），而中序同样可以帮助我们区分左、右子树。因此，这两者也可以唯一确定一棵二叉树。

重点在于选取的两种遍历方式可以提供关于这颗二叉树的结构信息，以 前序 和 中序 为例：