数据结构期末复习（4）串 树和二叉树

串

在数据结构中，串是由零个或多个字符组成的有限序列。它是一种线性数据结构，常用于表示和处理文本、字符串等信息。

串的特点包括：

1. 顺序性：串中的字符按照一定的先后顺序排列，每个字符都有一个唯一的位置。
2. 有限性：串的长度是有限的，它由字符的个数决定。
3. 可变性：串可以根据需要进行插入、删除和修改操作。

串的实现方式有多种，常见的有两种主要方式：

1. 数组实现：使用字符数组来存储串的字符序列。通过定义一个固定大小的数组，将串中的字符依次存放在数组中，可以通过数组下标来访问和操作串中的字符。这种实现方式简单直观，但需要预先分配足够的内存空间，并且对于插入、删除等操作需要移动大量的字符，效率较低。

2. 链表实现：使用链表结构来存储串的字符序列。每个节点包含一个字符和一个指向下一个节点的指针，通过将节点按顺序连接起来形成链表来表示串。这种实现方式不需要预先分配固定大小的内存空间，可以根据实际需要动态调整串的长度，插入、删除操作只需修改指针的指向，效率较高。

串的常见操作包括：

• 获取长度：获取串的字符个数。
• 判空：判断串是否为空。
• 比较：比较两个串是否相等或大小关系。
• 连接：将两个串连接成一个新的串。
• 子串：提取原串中的一部分作为子串。
• 查找：在串中查找指定字符或子串的位置。
• 插入、删除：在指定位置插入字符或删除字符。

串在实际应用中非常重要，常被用于文本处理、搜索引擎、编译器等领域。了解和熟练掌握串的相关知识对于编程和算法设计都非常有帮助。

串的基本操作

好的，我来详细介绍一下每一个字符串操作。

1. 字符串初始化（String Initialization）
   这个操作是将一个字符串常量或字符数组赋值给一个字符数组。可以用以下两种方式进行字符串初始化：

   char str[] = "Hello";
   

   或者

   char str[6] = {'H', 'e', 'l', 'l', 'o', '\0'};
   

   在第一种方式中，字符串常量被自动转换为字符数组并复制到字符数组 str 中。在第二种方式中，字符数组用字符常量的形式初始化，最后一个字符必须是空字符 '\0'，表示字符串的结尾。

2. 字符串赋值（String Copy）
   这个操作是将一个字符串复制到另一个字符串中。可以使用 strcpy() 函数进行字符串赋值：

   strcpy(dest, src);
   

   这里的 src 是源字符串，dest 是目标字符串。strcpy() 函数会将 src 中的字符复制到 dest 中，直到遇到空字符 '\0' 为止。

3. 字符串连接（String Concatenation）
   这个操作是将一个字符串连接到另一个字符串的末尾。可以使用 strcat() 函数进行字符串连接：

   strcat(dest, src);
   

   这里的 src 是源字符串，dest 是目标字符串。strcat() 函数会将 src 中的字符连接到 dest 的末尾，直到遇到空字符 '\0'。

4. 字符串长度（String Length）
   这个操作是求一个字符串的长度。可以使用 strlen() 函数进行字符串长度计算：

   strlen(str);
   

   这里的 str 是要计算长度的字符串。strlen() 函数会返回 str 中的字符数，不包括空字符 '\0'。

5. 字符串比较（String Comparison）
   这个操作是比较两个字符串是否相等。可以使用 strcmp() 函数进行字符串比较：

   strcmp(str1, str2);
   

   这里的 str1 和 str2 是要比较的字符串。strcmp() 函数会返回一个整数值，表示两个字符串的大小关系。如果 str1 大于 str2，则返回一个正整数；如果 str1 小于 str2，则返回一个负整数；如果两个字符串相等，则返回0。

6. 字符串复制（String Copy with Length）
   这个操作是将一个字符串的前n个字符复制到另一个字符串中。可以使用 strncpy() 函数进行字符串复制：

   strncpy(dest, src, n);
   

   这里的 src 是源字符串，dest 是目标字符串，n 是要复制的字符数。strncpy() 函数会将 src 中的前 n 个字符复制到 dest 中，如果 src 的字符数不足 n，则在 dest 中填充空字符 '\0'。

7. 字符串查找（String Searching）
   这个操作是在一个字符串中查找特定字符或子串。可以使用 strchr() 函数查找一个特定字符：

   strchr(str, ch);
   

   这里的 str 是要查找的字符串，ch 是要查找的字符。strchr() 函数会返回一个指向第一个匹配字符的指针，如果未找到该字符，则返回 NULL。
   另外，如果要查找一个特定子串，可以使用 strstr() 函数：

   strstr(str, substr);
   

   这里的 str 是要查找的字符串，substr 是要查找的子串。strstr() 函数会返回一个指向第一个匹配子串的指针，如果未找到该子串，则返回 NULL。

8. 字符串分割（String Tokenization）
   这个操作是将一个字符串分割成多个子串。可以使用 strtok() 函数进行字符串分割：

   strtok(str, delimiters);
   

   这里的 str 是要分割的字符串，delimiters 是分割符字符串。strtok() 函数会返回一个指向当前子串的指针，每次调用 strtok() 函数时，它都会返回下一个子串。可以使用 NULL 作为第一个参数来继续返回下一个子串，直到所有的子串都被遍历过。

2.串的简单模式匹配算法

串的简单模式匹配算法（也叫朴素模式匹配算法）是一种用来在一个文本串中查找一个模式串的算法。它的思想是从文本串的第一个字符开始，依次和模式串的每个字符进行比较，如果匹配成功，则继续比较下一个字符，否则将文本串向右移动一位，重新从文本串的下一个字符开始与模式串进行比较。

具体实现步骤如下：

1. **从文本串的第一个字符开始，依次与模式串的第一个字符、第二个字符、第三个字符……进行比较。**替换
2. 如果当前字符匹配成功，则继续比较下一个字符。
3. 如果当前字符匹配失败，则将文本串向右移动一位，并从新的位置开始重新与模式串进行比较。
4. 如果文本串已经被移动到了末尾，但是模式串还没有被完全匹配上，则说明匹配失败。

代码实现如下（以 C 语言为例）：

int simpleMatch(char* text, char* pattern) {
    int i,j;
    int textLen = strlen(text);
    int patternLen = strlen(pattern);

    for (i = 0; i <= textLen - patternLen; i++) {
        for (j = 0; j < patternLen; j++) {
            if (text[i + j] != pattern[j]) break;
        }
        if (j == patternLen) return i;
    }
    return -1;
}

其中，text 表示文本串，pattern 表示模式串。函数返回第一次匹配成功的位置，如果没有匹配成功则返回 -1。

该算法的时间复杂度为 $O(nm)$，其中 $n$ 和 $m$ 分别为文本串和模式串的长度。在最坏情况下，需要进行 $n-m+1$ 次比较，因此该算法的效率并不高，但是在实际应用中，该算法可以作为其他更高效的字符串匹配算法的基础。

矩阵的压缩存储（》？）

矩阵的压缩存储是一种有效地存储稀疏矩阵（大部分元素为0）的方法，可以节省存储空间。常见的矩阵压缩存储方法有三种：行压缩存储、列压缩存储和坐标压缩存储。

1. 行压缩存储（Compressed Row Storage, CRS）：
   在行压缩存储中，矩阵的非零元素按行存储，并且每一行的非零元素按照列索引的顺序排列。此外，还需要一个额外的数组记录每一行的起始位置和结束位置。这样，对于一个 m × n 的稀疏矩阵，需要三个数组来存储数据：

   • val 数组：保存非零元素的值。
   • col_ind 数组：保存非零元素所在的列索引。
   • row_ptr 数组：保存每一行的起始位置和结束位置的索引。

2. 列压缩存储（Compressed Column Storage, CCS）：
   在列压缩存储中，矩阵的非零元素按列存储，并且每一列的非零元素按照行索引的顺序排列。与行压缩存储类似，需要三个数组来存储数据：

   • val 数组：保存非零元素的值。
   • row_ind 数组：保存非零元素所在的行索引。
   • col_ptr 数组：保存每一列的起始位置和结束位置的索引。

3. 坐标压缩存储（Coordinate Storage, COO）：
   在坐标压缩存储中，可以简单地将每个非零元素的行号、列号和值存储在一个三元组中。因此，需要三个数组来存储数据：

   • row_ind 数组：保存非零元素的行号。
   • col_ind 数组：保存非零元素的列号。
   • val 数组：保存非零元素的值。

这些压缩存储方法适用于大部分元素为0的稀疏矩阵，可以显著减少存储空间的使用，并且在某些计算中可以提高计算效率。选择哪种压缩存储方法取决于具体应用场景和对存储和计算效率的需求。

当矩阵是稀疏矩阵（大部分元素为0）时，传统的二维数组存储方式会造成大量的存储空间浪费，而压缩存储方法可以有效地减少存储空间的使用。

1. 行压缩存储（CRS）：
   在行压缩存储中，矩阵的非零元素按行存储，并且每一行的非零元素按照列索引的顺序排列。此外，还需要一个额外的数组记录每一行的起始位置和结束位置。例如，对于以下稀疏矩阵：

   1 0 0 0
   0 0 2 0
   3 4 0 5
   

   对应的行压缩存储如下：

   • val 数组：[1, 2, 3, 4, 5]，保存非零元素的值。
   • col_ind 数组：[0, 2, 0, 1, 3]，保存非零元素所在的列索引。
   • row_ptr 数组：[0, 1, 3, 5]，保存每一行的起始位置和结束位置的索引。

   在行压缩存储中，对于第 i 行的元素，其非零元素的位置范围是 row_ptr[i] 到 row_ptr[i+1]-1。

2. 列压缩存储（CCS）：
   在列压缩存储中，矩阵的非零元素按列存储，并且每一列的非零元素按照行索引的顺序排列。与行压缩存储类似，需要三个数组来存储数据。以同样的稀疏矩阵为例：

   • val 数组：[1, 3, 2, 4, 5]，保存非零元素的值。
   • row_ind 数组：[0, 2, 0, 2, 2]，保存非零元素所在的行索引。
   • col_ptr 数组：[0, 1, 2, 4, 5]，保存每一列的起始位置和结束位置的索引。

   在列压缩存储中，对于第 j 列的元素，其非零元素的位置范围是 col_ptr[j] 到 col_ptr[j+1]-1。

3. 坐标压缩存储（COO）：
   在坐标压缩存储中，可以简单地将每个非零元素的行号、列号和值存储在一个三元组中。因此，需要三个数组来存储数据。以同样的稀疏矩阵为例：

   • row_ind 数组：[0, 2, 2, 0, 2]，保存非零元素的行号。
   • col_ind 数组：[0, 2, 3, 0, 3]，保存非零元素的列号。
   • val 数组：[1, 3, 5, 2, 4]，保存非零元素的值。

   在坐标压缩存储中，每个三元组表示一个非零元素的位置和值。

这些压缩存储方法对于稀疏矩阵的存储可以大大节省存储空间。同时，在进行稀疏矩阵的运算时，这些压缩存储方法也能够提高计算效率。选择哪种压缩存储方法取决于具体应用场景和对存储和计算效率的需求。

当处理稀疏矩阵时，选择适合的压缩存储方法可以提高存储效率和计算效率。下面是一些选择压缩存储方法的考虑因素：

1. 稀疏度：稀疏度是指矩阵中非零元素占总元素数量的比例。如果矩阵非常稀疏，即非零元素很少，那么压缩存储方法可以更好地节省存储空间。行压缩存储和列压缩存储在稀疏度较高时表现较好。

2. 存储需求：根据实际存储需求选择压缩存储方法。如果需要快速访问某一行或某一列的元素，行压缩存储和列压缩存储可能更合适。如果需要随机访问元素，坐标压缩存储可能更适用。

3. 计算需求：根据对矩阵的操作和计算需求选择压缩存储方法。不同的压缩存储方法对于不同的矩阵运算操作（如矩阵乘法、矩阵加法等）具有不同的计算效率。通常情况下，行压缩存储和列压缩存储在矩阵乘法等操作中表现较好。

4. 内存限制：考虑可用内存大小，选择适当的压缩存储方法。行压缩存储和列压缩存储通常需要额外的数组来存储索引信息，因此可能需要更多的内存空间。

需要注意的是，选择压缩存储方法时需要综合考虑上述因素，并根据具体应用场景进行权衡。不同的压缩存储方法在不同的情况下可能会有不同的性能表现。

树和二叉树

前驱 后继

树和二叉树都是常见的数据结构，用于组织和表示具有分层结构的数据。下面是它们的介绍：

1. 树（Tree）：

   • 树是由节点（Node）组成的集合，每个节点可以有零个或多个子节点。
   • 树的一个节点被称为根节点（Root），它没有父节点。
   • 其他节点都有且只有一个父节点，形成父子关系。
   • 除了根节点外，其他节点可以分为内部节点和叶节点（Leaf）。内部节点有至少一个子节点，而叶节点没有子节点。
   • 节点之间的连接称为边（Edge）。
   • 树的常见应用包括文件系统、组织结构、图算法等。

2. 二叉树（Binary Tree）：

   • 二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
   • 二叉树的子节点位置固定，不能超过两个。
   • 二叉树可以为空，即不包含任何节点，或者是由根节点和左子树、右子树组成的。
   • 二叉树的遍历方式包括前序遍历（先访问根节点，然后递归地访问左子树和右子树）、中序遍历（先递归地访问左子树，然后访问根节点，最后递归地访问右子树）和后序遍历（先递归地访问左子树和右子树，最后访问根节点）等。

二叉树是树的一种特殊情况，在很多应用中具有重要作用。它可以用于实现搜索和排序算法，例如二叉搜索树（Binary Search Tree）；也可以用于构建表达式树、哈夫曼树等。树和二叉树在计算机科学中有广泛的应用，对于理解和解决各种问题都具有重要意义。

树的基本概念介绍

树是一种具有分层结构的数据结构，它由节点和边组成，每个节点可以有零个或多个子节点，除了根节点外，每个节点都有一个父节点。下面是树的一些基本概念：

1. 根节点（Root）：树的顶部节点，没有父节点。

2. 内部节点（Internal Node）：除了根节点和叶节点外，其他节点都是内部节点，即有至少一个子节点的节点。

3. 叶节点（Leaf）：没有子节点的节点，也称为终端节点。

4. 子节点（Child）：一个节点的直接下属节点。

5. 父节点（Parent）：一个节点的直接上级节点。

6. 兄弟节点（Sibling）：具有相同父节点的节点，即同级节点。

7. 子树（Subtree）：以一个节点为根节点，它的所有后代节点组成的树。

8. 深度（Depth）：根节点到某个节点的路径长度，根节点的深度为 0，其余节点深度为其父节点深度加 1。

9. 高度（Height）：从某个节点到它的最远叶节点的路径长度，叶节点的高度为 0，树的高度为根节点的高度。

10. 层次（Level）：根节点为第一层，其子节点为第二层，以此类推。

11. 森林（Forest）：由多棵树组成的集合。

树在计算机科学中有许多应用，例如解析表达式、查找和排序数据、构建文件系统和数据库等。了解树的基本概念可以帮助我们更好地理解它们的实现和应用。

二叉树

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。以下是二叉树的一些基本概念：

1. 根节点（Root）：二叉树的顶部节点，没有父节点。

2. 内部节点（Internal Node）：除了根节点外，其他节点都是内部节点，即有至少一个子节点的节点。

3. 叶节点（Leaf）：没有子节点的节点，也称为终端节点。

4. 子节点（Child）：一个节点的直接下属节点。

5. 父节点（Parent）：一个节点的直接上级节点。

6. 兄弟节点（Sibling）：具有相同父节点的节点，即同级节点。

7. 左子节点和右子节点：一个节点的直接下属节点，分别称为左子节点和右子节点。

8. 子树（Subtree）：以一个节点为根节点，它的所有后代节点组成的二叉树。

9. 二叉树的属性：

   • 对于每个节点，最多有两个子节点。
   • 左子节点和右子节点的顺序是固定的，左边的子节点先于右边的子节点。
   • 二叉树可以为空，即不包含任何节点。

10. 二叉树的遍历方式：

• 前序遍历（Preorder Traversal）：先访问根节点，然后递归地访问左子树和右子树。
• 中序遍历（Inorder Traversal）：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
• 后序遍历（Postorder Traversal）：先递归地访问左子树和右子树，最后访问根节点。

二叉树在计算机科学中具有广泛的应用，例如二叉搜索树、哈夫曼树、表达式树等。它们对于表示和操作数据以及解决各种问题都非常重要。

几个特殊的二叉树

二叉树的性质

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点（左子节点和右子节点）。以下是二叉树的一些性质：

1. 根节点：二叉树的顶部节点称为根节点。它是树的起始点，没有父节点。

2. 子节点：一个节点的直接下级节点称为其子节点。一个节点最多可以有两个子节点，分别为左子节点和右子节点。

3. 叶子节点：没有子节点的节点称为叶子节点，也称为终端节点。

4. 父节点：一个节点的直接上级节点称为其父节点。

5. 兄弟节点：具有相同父节点的节点称为兄弟节点。

6. 深度：节点到根节点的层数称为深度。根节点的深度为0，其子节点的深度为1，依次递增。

7. 高度：节点到叶子节点的最长路径的边数称为高度。叶子节点的高度为0，根节点的高度为树的高度。

8. 路径：从一个节点到另一个节点的通路称为路径。

9. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。

10. 前序遍历：先访问根节点，然后递归地遍历左子树和右子树。

11. 中序遍历：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

12. 后序遍历：先递归地遍历左子树和右子树，最后访问根节点。

这些性质是二叉树的一些基本概念和遍历方式，可以帮助我们理解和操作二叉树数据结构。

二叉树的存储结构

二叉树的存储结构有两种常见的方式：顺序存储和链式存储。

1. 顺序存储：
   在顺序存储结构中，可以使用数组来表示二叉树。通常按照完全二叉树的形式进行存储，即从上到下、从左到右依次存储节点。具体描述如下：

   // 定义二叉树节点
   struct TreeNode {
       int data;
       struct TreeNode* left;
       struct TreeNode* right;
   };
   
   // 定义顺序存储结构
   struct SeqBinaryTree {
       struct TreeNode** nodes;
       int capacity;
       int size;
   };
   

   在初始化二叉树时，需要为顺序存储结构分配足够的空间，并将二叉树的节点指针存储在对应的位置上。

   注意：由于顺序存储结构要求按照完全二叉树的形式存储节点，因此在实际使用中可能会浪费一部分空间。

2. 链式存储：
   在链式存储结构中，通过定义节点结构体，利用指针来表示二叉树节点之间的关系。具体描述如下：

   // 定义二叉树节点
   struct TreeNode {
       int data;
       struct TreeNode* left;
       struct TreeNode* right;
   };
   

   在链式存储结构中，每个节点包含了数据以及指向左子树和右子树的指针。通过指针的链接，可以形成完整的二叉树结构。

3. 双亲孩子表示法：
   在双亲孩子表示法中，每个节点除了包含数据和指向左右子节点的指针外，还包含一个指向父节点的指针。具体描述如下：

   // 定义二叉树节点
   struct TreeNode {
       int data;
       struct TreeNode* parent;
       struct TreeNode* left;
       struct TreeNode* right;
   };
   

   这种表示法可以方便地通过父节点指针访问节点的父节点，但相应地增加了空间的开销。

4. 孩子兄弟表示法：
   在孩子兄弟表示法中，每个节点包含了数据以及指向第一个孩子节点和右兄弟节点的指针。具体描述如下：

   // 定义二叉树节点
   struct TreeNode {
       int data;
       struct TreeNode* firstChild;
       struct TreeNode* nextSibling;
   };
   

   这种表示法适用于任意多叉树，通过孩子节点和兄弟节点的链接，可以形成复杂的树结构。

除了以上介绍的存储结构，还有其他一些衍生的存储结构，如线索二叉树、哈夫曼树等。具体选择哪种存储结构，取决于对二叉树操作的需求和空间效率的考量。

二叉树的遍历

在二叉树中，遍历是指按照一定的顺序访问所有节点，包括遍历所有根节点、遍历所有左子树和遍历所有右子树。常见的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：
   在前序遍历中，先访问当前节点，然后遍历左子树，最后遍历右子树。具体实现如下：

   void preOrderTraversal(struct TreeNode* root) {
       if (root == NULL) {
           return;
       }
       printf("%d ", root->data); // 访问当前节点
       preOrderTraversal(root->left); // 遍历左子树
       preOrderTraversal(root->right); // 遍历右子树
   }
   

2. 中序遍历：
   在中序遍历中，先遍历左子树，然后访问当前节点，最后遍历右子树。具体实现如下：

   void inOrderTraversal(struct TreeNode* root) {
       if (root == NULL) {
           return;
       }
       inOrderTraversal(root->left); // 遍历左子树
       printf("%d ", root->data); // 访问当前节点
       inOrderTraversal(root->right); // 遍历右子树
   }
   

3. 后序遍历：
   在后序遍历中，先遍历左子树，然后遍历右子树，最后访问当前节点。具体实现如下：

   void postOrderTraversal(struct TreeNode* root) {
       if (root == NULL) {
           return;
       }
       postOrderTraversal(root->left); // 遍历左子树
       postOrderTraversal(root->right); // 遍历右子树
       printf("%d ", root->data); // 访问当前节点
   }
   

以上是常见的三种二叉树遍历方式。在实际使用中，可以根据需要进行适当的修改和扩展，例如增加层序遍历等其他遍历方式。

二叉树的先序序列和后序序列，无法唯一确定一棵二叉树

二叉树的先序序列和后序序列无法唯一确定一棵二叉树。这是因为在先序序列和后序序列中，只有节点的相对顺序，而没有直接的线索可以确定每个节点的父节点和子节点之间的关系。

例如，考虑以下两棵二叉树：

    1             1
   / \           / \
  2   3         2   3
     /           \
    4             4

这两棵二叉树的先序序列和后序序列都是不同的。第一棵二叉树的先序序列是 [1, 2, 3, 4]，后序序列是 [2, 4, 3, 1]；而第二棵二叉树的先序序列是 [1, 2, 3, 4]，后序序列是 [2, 4, 3, 1]。可以看到，它们的先序序列和后序序列是相同的，但它们的结构是不同的。

因此，要唯一确定一棵二叉树，需要额外的信息，例如中序序列或者节点之间的连接方式。通常情况下，我们会使用先序序列和中序序列或者中序序列和后序序列来唯一确定一棵二叉树。

使用中序序列可以唯一确定一棵二叉树的原因是，中序遍历是一种按照节点值从小到大的顺序进行遍历的方式，每个节点的左子树都包含比它小的节点，右子树都包含比它大的节点。因此，在中序序列中，当前节点的左侧所有节点都应该是其左子树中的节点，右侧所有节点都应该是其右子树中的节点。这样，我们就可以通过先序序列和中序序列确定根节点，然后通过递归的方式确定左子树和右子树。

以一个例子来说明。

假设有如下一棵二叉树：

    5
   / \
  3   7
 / \   \
1   4   9

它的先序序列为 [5, 3, 1, 4, 7, 9]，中序序列为 [1, 3, 4, 5, 7, 9]。

根据先序序列，我们知道根节点是 5。然后，在中序序列中找到 5 的位置，可以知道左子树的中序序列为 [1, 3, 4]，右子树的中序序列为 [7, 9]。接下来，我们递归的求解左子树和右子树。对于左子树，它的先序序列为 [3, 1, 4]，中序序列为 [1, 3, 4]；对于右子树，它的先序序列为 [7, 9]，中序序列为 [7, 9]。我们可以通过递归的方式构建这棵二叉树。

使用后序序列来唯一确定一棵二叉树的原理类似。后序序列是指在遍历二叉树时，先遍历左子树和右子树，最后遍历根节点。因此，在后序序列中，每个节点的左右子树都已经被访问完毕，我们可以通过这个性质从后往前递推出每个节点的左右子树的范围，然后递归的方式构造二叉树。

将树转换成二叉树

将一棵树转换成二叉树可以有多种方法，这里介绍一种常见的方法，即将每个节点的孩子节点按照从左到右的顺序连接起来。

假设我们有以下一棵树：

    A
   / \
  B   C
 / \   \
D   E   F

我们可以将它转换成以下的二叉树：

    A
   /
  B
 / \
D   E
     \
      C
       \
        F

转换的步骤如下：

1. 对于每个节点，将其第一个孩子作为其左孩子，并将其兄弟节点作为其右孩子。
2. 对于每个节点的右孩子，将其右孩子的兄弟节点作为它的右孩子的右孩子，以此类推。

具体操作如下：

1. 对于节点 A，将 B 作为其左孩子，C 作为其右孩子。
2. 对于节点 B，将 D 作为其左孩子，E 作为其右孩子。
3. 对于节点 C，将 F 作为其右孩子。
4. 对于节点 E，将 C 作为其右孩子。
5. 对于节点 F，没有孩子节点。

按照以上操作，我们就成功地将一棵树转换成了二叉树。

需要注意的是，转换后的二叉树可能不是二叉搜索树或平衡二叉树等特殊类型的二叉树，它只是将树的结构改造成了二叉树的形式。转换后的二叉树的遍历顺序可能与原树不同，所以在具体应用中可能需要根据情况进行相应的调整。

将森林转换成二叉树

将一棵森林转换成二叉树的方法类似于将一棵树转换成二叉树，我们可以按照以下步骤进行转换：

1. 对于每个有左兄弟的节点，将其左兄弟作为其左孩子，并将其右兄弟作为其右孩子。
2. 对于每个没有左兄弟的节点，将其右兄弟作为其右孩子。

具体操作如下：

1. 对于节点 A，将 B 作为其左孩子，C 作为其右孩子。
2. 对于节点 B，将 D 作为其左孩子，E 作为其右孩子。
3. 对于节点 F，将 G 作为其右孩子。

转换后的二叉树如下：

    A
   / \
  B   C
 / \   \
D   E   F
       /
      G

需要注意的是，转换后的二叉树可能不是二叉搜索树或平衡二叉树等特殊类型的二叉树，它只是将森林的结构改造成了二叉树的形式。转换后的二叉树的遍历顺序可能与原森林不同，所以在具体应用中可能需要根据情况进行相应的调整。

二叉树转换成对应的森林

将一棵二叉树转换成对应的森林可以按照以下步骤进行：

1. 对于每个节点，如果它有左孩子，则将其左孩子作为一个新的树。
2. 对于每个节点，如果它有右孩子，则将其右孩子作为一个新的树，并将其父节点与右孩子之间的连接断开。

具体操作如下：

假设我们有以下的二叉树：

    A
   / \
  B   C
 / \   \
D   E   F
       /
      G

我们可以将它转换成以下的森林：

    A       C        F
   /         \        \
  B           E        G
 /                    

D                     

转换的步骤如下：

1. 对于节点 A，将其左孩子 B 作为一个新的树。
2. 对于节点 B，将其左孩子 D 作为一个新的树。
3. 对于节点 C，将其右孩子 F 作为一个新的树。
4. 对于节点 F，将其左孩子 G 作为一个新的树。

按照以上操作，我们成功地将一棵二叉树转换成了对应的森林。

需要注意的是，转换后的森林中每个树的根节点可能不是原二叉树的根节点，而是二叉树中的某个节点。转换后的森林的遍历顺序可能与原二叉树不同，所以在具体应用中可能需要根据情况进行相应的调整。

树的遍历

树的遍历是指按照一定规则访问树中的所有节点。常见的树的遍历方式有三种：前序遍历、中序遍历和后序遍历。下面我将逐一介绍这三种遍历方式的操作步骤：

1. 前序遍历（Preorder Traversal）：

   • 访问根节点。
   • 递归地前序遍历左子树。
   • 递归地前序遍历右子树。

2. 中序遍历（Inorder Traversal）：

   • 递归地中序遍历左子树。
   • 访问根节点。
   • 递归地中序遍历右子树。

3. 后序遍历（Postorder Traversal）：

   • 递归地后序遍历左子树。
   • 递归地后序遍历右子树。
   • 访问根节点。

需要注意的是，以上是针对二叉树的遍历方式，对于多叉树或森林，你可以将其看作一组独立的子树，分别按照相应的遍历方式进行遍历。

以下是一个示例树的结构，我们以此来演示三种遍历方式：

    A
   / \
  B   C
 / \   \
D   E   F

对应的遍历结果为：

• 前序遍历：A -> B -> D -> E -> C -> F
• 中序遍历：D -> B -> E -> A -> C -> F
• 后序遍历：D -> E -> B -> F -> C -> A

树的遍历方式可以根据实际需求进行选择，每种方式都有其特定的应用场景。

森林的遍历

森林是由多个独立的树组成的集合。对于森林的遍历，我们可以将其看作对每个树分别进行遍历操作。

常见的森林遍历方式有三种：前序遍历、中序遍历和后序遍历。下面我将逐一介绍这三种遍历方式在森林中的操作步骤：

1. 前序遍历（Preorder Traversal）：

   • 对于森林中的每棵树，先访问根节点。
   • 递归地前序遍历树的所有子树。

2. 中序遍历（Inorder Traversal）：

   • 对于森林中的每棵树，递归地中序遍历树的所有左子树。
   • 访问根节点。
   • 递归地中序遍历树的所有右子树。

3. 后序遍历（Postorder Traversal）：

   • 对于森林中的每棵树，递归地后序遍历树的所有子树。
   • 访问根节点。

需要注意的是，在森林遍历中，每棵树都是独立的，互不影响。因此，遍历顺序是先处理完一棵树，再处理下一棵树。

以下是一个示例森林的结构，由两棵树组成：

    A         D
   / \       / \
  B   C     E   F

对应的遍历结果为：

• 前序遍历：A -> B -> C -> D -> E -> F
• 中序遍历：B -> A -> C -> E -> D -> F
• 后序遍历：B -> C -> A -> E -> F -> D

通过对每棵树进行遍历操作，我们可以依次访问到森林中的所有节点。森林的遍历方式可以根据实际需求进行选择，每种方式都有其特定的应用场景。

二叉排序树

二叉排序树（Binary Search Tree，BST），也称为二叉搜索树或二叉查找树，是一种特殊的二叉树结构。它满足以下性质：

1. 对于树中的每个节点n，其左子树的所有节点的值都小于n的值。
2. 对于树中的每个节点n，其右子树的所有节点的值都大于n的值。
3. 左子树和右子树都是二叉排序树。

这个性质保证了在二叉排序树中，每个节点的值都大于其左子树的所有节点的值，并且小于其右子树的所有节点的值。这使得在二叉排序树中进行查找、插入和删除操作都可以在平均情况下以O(log n)的时间复杂度完成。

以下是一个示例的二叉排序树：

       6
     /   \
    2     8
   / \   / \
  1   4 7   9
     / \
    3   5

在这个二叉排序树中，每个节点的值都满足左小右大的关系。例如，节点2的左子树所有节点的值都小于2，节点4的左子树所有节点的值都小于4，节点8的右子树所有节点的值都大于8。

通过二叉排序树，我们可以很方便地进行查找、插入和删除等操作。例如，要查找值为3的节点，我们可以从根节点开始比较，由于3小于6，在根节点的左子树中继续查找；再由于3大于2，在2的右子树中继续查找；最终找到了值为3的节点。

需要注意的是，当二叉排序树中存在重复的值时，通常有多种可能的构建方式，因为相同的值可以放在左子树或右子树中。此外，如果二叉排序树不平衡（即左右子树的高度差过大），可能会导致查找效率下降，因此有一些平衡二叉排序树的变种，如红黑树和AVL树，用于提高性能。

当我们对二叉排序树进行操作时，可以执行以下几种常见的操作：

1. 查找（Search）：在二叉排序树中查找某个特定值。从根节点开始比较，根据比较结果决定是向左子树还是右子树搜索，直到找到目标值或搜索到空节点。

2. 插入（Insert）：向二叉排序树中插入一个新的节点。首先进行查找操作，找到插入位置的父节点，然后根据插入值与父节点值的大小关系，确定新节点应该插入到父节点的左侧还是右侧。

3. 删除（Delete）：删除二叉排序树中的某个节点。首先进行查找操作，找到待删除节点。删除节点时需要考虑不同情况：

   • 若待删除节点为叶子节点（没有子节点），直接删除即可。
   • 若待删除节点只有一个子节点，将其子节点替代待删除节点的位置。
   • 若待删除节点有两个子节点，可以选择将其左子树的最大节点或右子树的最小节点替代待删除节点，保持二叉排序树的性质。

4. 遍历（Traversal）：按照特定的顺序访问二叉排序树中的所有节点。常见的遍历方式包括前序遍历、中序遍历和后序遍历。这些遍历方式在前面的回答中已经详细介绍过了。

对于二叉排序树的操作，需要注意保持树的性质不变。在插入和删除操作中，需要进行相应的调整，以确保新树仍然是一个有效的二叉排序树。

需要指出的是，二叉排序树的性能取决于树的结构是否平衡。如果树的不平衡程度过高，可能会导致操作的时间复杂度退化为线性复杂度，从而降低效率。因此，为了提高性能，可以使用一些平衡二叉排序树的数据结构，如红黑树、AVL树等。这些树结构可以自动调整节点的位置，以保持树的平衡性。

插入：比较插入值和根节点大小

二叉排序树的构造

构造二叉排序树的基本思路是将元素逐个插入到树中。下面是一种常用的构造方法：

1. 创建一个空的二叉排序树。

2. 依次将元素插入到二叉排序树中：

   • 如果树为空，则将第一个元素作为根节点。
   • 如果树不为空，则从根节点开始比较待插入元素与当前节点的大小关系：
     • 如果待插入元素小于当前节点的值，继续在左子树中插入。
     • 如果待插入元素大于当前节点的值，继续在右子树中插入。
     • 如果待插入元素等于当前节点的值，根据具体需求，可以将重复元素放在左子树或右子树中。

3. 重复步骤2，直到所有元素都插入到二叉排序树中。

以下是一个示例的二叉排序树的构造过程：

假设有以下元素需要插入到二叉排序树中：7, 3, 9, 2, 1, 4, 8, 6, 5。

1. 创建一个空的二叉排序树。

2. 将第一个元素7作为根节点。

3. 插入元素3：

   • 3小于7，插入到7的左子树中。

4. 插入元素9：

   • 9大于7，插入到7的右子树中。

5. 插入元素2：

   • 2小于3，插入到3的左子树中。

6. 插入元素1：

   • 1小于2，插入到2的左子树中。

7. 插入元素4：

   • 4大于3，插入到3的右子树中。

8. 插入元素8：

   • 8大于7，插入到7的右子树中。

9. 插入元素6：

   • 6大于3，小于7，插入到7的左子树的右子树中。

10. 插入元素5：

    • 5大于3，小于6，插入到6的左子树中。

最终的二叉排序树如下所示：

         7
       /   \
      3     9
     / \   /
    2   4 8
   /     \
  1       6
         /
        5

通过以上步骤，我们成功地构造了一个二叉排序树。需要注意的是，由于二叉排序树的构造过程是依次插入元素，如果元素的插入顺序不同，最终构造出的二叉排序树可能会有所不同，但它们都满足二叉排序树的性质。

二叉排序树的删除

二叉排序树的删除操作需要考虑到三种情况：

1. 待删除节点为叶子节点：直接删除即可。

2. 待删除节点只有一个子节点：用其子节点代替待删除节点。

3. 待删除节点有两个子节点：找到待删除节点的前驱或后继节点，用它来替代待删除节点。

下面分别介绍这三种情况的具体操作步骤。

1. 待删除节点为叶子节点

如果待删除节点为叶子节点，即没有左右子节点，那么直接将该节点从树中删除即可。

假设我们要删除节点5，如下图所示：

         7
       /   \
      3     9
     / \   /
    2   4 8
   /     \
  1       5
         /
        6

首先找到要删除的节点5，因为它是叶子节点，所以直接将它从树中删除。删除后，需要将节点5的父节点4的右子树指针置为空。

删除后的树结构如下图所示：

         7
       /   \
      3     9
     / \   /
    2   4 8
   /     
  1       
         /
        6

2. 待删除节点只有一个子节点

如果待删除节点只有一个子节点，那么可以直接用其子节点代替它。

以删除节点4为例，如下图所示：

         7
       /   \
      3     9
     / \   /
    2   4 8
   /     \
  1       5
         /
        6

首先找到要删除的节点4，因为它只有一个子节点5，所以将节点5代替节点4。注意，此时需要将节点5的左子树指针指向节点4的左子树，同时将节点5的父节点指针指向节点4的父节点。

删除后的树结构如下图所示：

         7
       /   \
      3     9
     / \   /
    2   5 8
   /     \
  1       6

3. 待删除节点有两个子节点

如果待删除节点有两个子节点，那么需要找到它的前驱或后继节点，用它来替代待删除节点。这里以使用前驱节点作为例子。

前驱节点是指比待删除节点小的最大节点。在二叉排序树中，前驱节点一定在待删除节点的左子树中。具体操作步骤如下：

1. 在待删除节点的左子树中，找到最右侧的节点，即为前驱节点。

2. 将前驱节点的值赋给待删除节点，并删除前驱节点。

以删除节点3为例，如下图所示：

         7
       /   \
      3     9
     / \   /
    2   4 8
   /     \
  1       5
         /
        6

首先找到要删除的节点3，因为它有两个子节点，需要找到它的前驱节点2。在节点3的左子树中，最右侧的节点就是节点2。将节点2的值赋给节点3，然后删除节点2，即可完成删除操作。

删除后的树结构如下图所示：

         7
       /   \
      2     9
     / \   /
    1   4 8
       /   \
      5     6

通过以上三种情况的操作，我们可以实现二叉排序树节点的删除。需要注意的是，在删除节点时，需要保证删除后的树仍然满足二叉排序树的性质。

哈夫曼树

哈夫曼树（Huffman Tree），又称最优树，是一种带权路径长度最短的树。在哈夫曼树中，每个叶子节点都有一个权值，每个非叶子节点的权值等于其左右子树权值之和，因此哈夫曼树是一棵带权树。

哈夫曼树应用广泛，特别是在数据压缩领域中。数据压缩就是将一个数据集合转换为另一个更小的数据集合，以便通过更少的存储空间或网络带宽来传输数据。哈夫曼树可以用来实现无损压缩，即将数据压缩为更小的数据集合，并且在解压缩时不会丢失原始数据。

构建哈夫曼树的过程如下：

1. 将所有权值作为单独的节点，构造n棵只有根节点的二叉树。

2. 在这n棵二叉树中，选取两棵根节点权值最小的树作为左右子树合并成一棵新树。新树的根节点权值为左右子树根节点权值之和。

3. 将这个新树插入到原来的二叉树集合中。

4. 重复步骤2和3，直到只剩下一棵二叉树，这棵二叉树即为哈夫曼树。

例如，给定下面的权值数组：

[5, 6, 7, 8, 9]

首先，将这些权值构造成5棵只有根节点的二叉树，如下所示：

5        6        7        8        9
         |        |        |        |
         |        |        |        |
         +        +        +        +
         |        |        |        |
         |        |        |        |
        null     null     null     null

选取两个根节点权值最小的二叉树进行合并，得到一棵新的二叉树，其根节点权值为5+6=11，如下所示：

    11
   /  \
  5    6

再将这棵新树插入到原来的二叉树集合中，得到4棵二叉树，如下所示：

    7        8        9        11
   / \      / \      / \      / \
  5   6    5   6    5   6    7   8
              |        |        |
              |        |        |
             null     null     9

重复以上步骤，直到只剩下一棵二叉树，即可得到哈夫曼树，如下所示：

        36
       /  \
      16   20
     /  \
    7    9
   / \  / \
  3  4 5   4

在哈夫曼树中，叶子节点代表原始数据中的符号，非叶子节点代表两个或更多符号的组合。哈夫曼编码就是将每个符号映射到其所对应的叶子节点路径上的二进制编码。哈夫曼编码的特点是：任何一个符号的编码都不是另一个符号编码的前缀，因此可以通过哈夫曼编码实现无损压缩。

当我们有一个已经构建好的哈夫曼树后，可以利用它进行数据的压缩和解压缩。

首先，我们需要通过遍历哈夫曼树来构建每个字符对应的哈夫曼编码。在遍历过程中，左子树路径上的编码为0，右子树路径上的编码为1。当遍历到叶子节点时，就可以得到该字符对应的哈夫曼编码。

例如，在上面给出的哈夫曼树中，假设字符’A’对应的叶子节点路径为左-左-左（编码为000），字符’B’对应的叶子节点路径为左-左-右（编码为001），以此类推。

在进行数据压缩时，我们可以将原始数据中的字符替换为其对应的哈夫曼编码。这样，相同的字符在压缩后会占用更少的空间，从而实现了数据的压缩。

例如，如果原始数据是"ABACD"，对应的哈夫曼编码为"0000010001010100"，压缩后的数据只需占用16位空间。

在进行数据解压缩时，我们需要借助哈夫曼树来根据压缩后的编码逐步还原出原始数据。从根节点开始，根据压缩数据的每一位编码，依次遍历哈夫曼树。当遇到叶子节点时，就找到了对应的字符，可以将其输出，并回到根节点继续下一位编码的解析。

例如，对于压缩后的数据"0000010001010100"，我们可以根据哈夫曼树还原出原始数据"ABACD"。

总结一下，哈夫曼树是一种带权路径长度最短的树，常用于数据压缩中。通过构建哈夫曼树和生成哈夫曼编码，我们可以实现数据的无损压缩和解压缩。文章来源地址https://www.toymoban.com/news/detail-796623.html

到了这里，关于数据结构期末复习（4）串 树和二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！