• 【数据结构】树的存储结构；树的遍历；哈夫曼树；并查集

      欢~迎~光~临~^_^

    目录

    1、树的存储结构

    1.1双亲表示法

    1.2孩子表示法

    1.3孩子兄弟表示法

    2、树与二叉树的转换

    3、树和森林的遍历

    3.1树的遍历

    3.1.1先根遍历

    3.1.2后根遍历

    3.2森林的遍历

    3.2.1先序遍历森林

    3.2.2中序遍历森林

    4、树与二叉树的应用

    4.1哈夫曼树

    4.1.1概念

    4.1.2构造哈夫曼树

    4.1.3哈夫曼编码

    4.1.4C语言实现哈夫曼树

    4.2并查集​编辑

    4.2.1逻辑结构

    4.2.2基本操作

    4.2.3存储结构

    4.2.4优化

    1、树的存储结构

     

    1.1双亲表示法

    树的双亲表示法是一种简单的树结构表示方法，它在每个结点中存储了该结点的父节点信息。具体地，每个结点包含两部分信息，一部分是该结点的数据，另一部分是该结点的父节点的索引值。根结点没有父节点，通常用一个特定的值来表示。双亲表示法的优点是在访问任意结点的父节点时非常快，但是在查找任意结点的子节点时则需要遍历整棵树来确定其子节点。

    例如，下面是一个有6个节点的树的双亲表示法的例子： 

    1. struct TreeNode {
    2.     int data;      // 节点数据
    3.     int parent;    // 父节点索引
    4. };
    5.  
    6. TreeNode tree[6];   // 定义一个有6个节点的树，每个节点包含数据和父节点索引两部分信息
    7. tree[0].data = 1;   // 第一个节点的数据是1，它是根节点，没有父节点
    8. tree[1].data = 2;   // 第二个节点的数据是2，它的父节点是根节点，其父节点索引为0
    9. tree[1].parent = 0;
    10. tree[2].data = 3;   // 第三个节点的数据是3，它的父节点是根节点，其父节点索引为0
    11. tree[2].parent = 0;
    12. tree[3].data = 4;   // 第四个节点的数据是4，它的父节点是第二个节点，其父节点索引为1
    13. tree[3].parent = 1;
    14. tree[4].data = 5;   // 第五个节点的数据是5，它的父节点是第二个节点，其父节点索引为1
    15. tree[4].parent = 1;
    16. tree[5].data = 6;   // 第六个节点的数据是6，它的父节点是第三个节点，其父节点索引为2
    17. tree[5].parent = 2;
    18.

    1.2孩子表示法

    树的孩子表示法是一种常用的树的存储方式，它的基本思想是：每个节点都存储它的孩子节点的指针（地址）。

    相比于其他树的存储方式，孩子表示法的优点是：

    1. 能够较快地访问节点的孩子节点，因为每个节点都存储了它的孩子节点的指针；

    2. 孩子表示法的存储方式相对简单、直观易懂。

    但是，孩子表示法也存在一些缺点：

    1. 孩子节点的数量不固定，因此存储时需要动态分配内存空间；

    2. 访问父节点比较麻烦，需要从根节点开始遍历整棵树才能找到父节点。

    1.3孩子兄弟表示法

    孩子兄弟表示法是一种树型数据结构中用于表示节点关系的方法，通常用于表示一个树或者一棵森林中的节点之间的关系。

    在孩子兄弟表示法中，每个节点包含两个指针：一个指向该节点的第一个孩子节点，另一个指向该节点的下一个兄弟节点。因此，通过这两个指针可以遍历整棵树或森林中的节点，并找到它们的父节点、孩子节点和兄弟节点。

    孩子兄弟表示法的主要优点是它能够有效地减少存储空间的使用，因为每个节点只需要存储两个指针，而不需要像其他表示方法那样存储父节点和所有孩子节点的指针。

    然而，由于每个节点只存储了两个指针，因此在进行某些操作时，可能需要遍历整棵树或森林，这可能会导致效率较低。

    2、树与二叉树的转换

    将一棵树转换为二叉树的方法，可以选择先把树转换为森林，然后再对每棵树进行转换。转换的基本思路是：将每个节点的第一个孩子作为其左孩子，将兄弟节点作为其右孩子。

    具体实现如下：

    1. 首先对树进行先序遍历，从根节点开始遍历。

    2. 对于每个节点，如果它有孩子节点，将其第一个孩子节点作为其左孩子。

    3. 对于每个节点的兄弟节点，将其作为当前节点右孩子。

    4. 对于所有没有孩子节点的节点，将其左孩子和右孩子都设为空。

    5. 最终得到的结果是一棵二叉树。

    将一棵二叉树转换为一棵树的方法，可以选择先把二叉树转换为森林，然后再将森林中的所有树合并为一棵树。具体实现如下：

    1. 针对每个节点，将其左孩子作为其第一个孩子节点，将其右孩子的子树转换为其兄弟节点。

    2. 对于每个节点，先将其所有孩子节点合并为一棵子树，然后将其所有兄弟节点依次加入这棵子树中。

    3. 最终得到的结果是一棵树。

    3、树和森林的遍历

    3.1树的遍历

    3.1.1先根遍历

    树的先根遍历是一种树的遍历方式，先访问根节点，然后依次遍历其子节点，再依次遍历每个子节点的子树的根节点。

     例如，对于下图所示的树：

    1.     A
    2.    / \
    3.   B   C
    4.  /   / \
    5. D   E   F
    6.

    先根遍历的顺序是：A -> B -> D -> C -> E -> F。

    3.1.2后根遍历

    树的后根遍历（也叫后序遍历）是指先访问一个节点的左子树和右子树，最后再访问该节点本身。具体的遍历顺序如下：

    1. 访问该节点的左子树
    2. 访问该节点的右子树
    3. 访问该节点本身

    通常，可以使用递归或迭代算法实现树的后根遍历。递归的实现方式比较简单。

    迭代的实现方式稍微复杂一些，需要借助栈来实现。具体的算法如下：

    1. 将根节点压入栈中
    2. 如果栈不为空，则取出栈顶节点
    3. 如果该节点没有左右子节点或者其左右子节点已经被访问过，则访问该节点并弹出
    4. 如果该节点有左右子节点且其左右子节点还未被访问，则将其右子节点和左子节点依次压入栈中，保证左右子节点先被访问

    3.2森林的遍历

    3.2.1先序遍历森林

    先序遍历森林是指以任意一棵树的根节点为起点，按照先访问根节点，再依次访问子树的方式遍历整个森林。具体操作如下：

    1. 访问当前节点
    2. 依次以当前节点的子节点为根节点，重复进行上述操作

    在实际操作中，可以采用递归或栈的方式实现先序遍历森林。以递归方式为例，实现代码如下：

    1. void preOrderForest(Node* root) {
    2.     if (root == nullptr) {
    3.         return;
    4.     }
    5.     // 访问当前节点
    6.     visit(root);
    7.     // 依次遍历子树
    8.     for (Node* child : root->children) {
    9.         preOrderForest(child);
    10.     }
    11. }
    12.

    其中，Node代表树节点的数据结构，root表示当前节点，children表示当前节点的子节点列表，visit()表示访问节点的操作。

    3.2.2中序遍历森林

    森林的后序遍历是将森林中每个树的后序遍历序列依次拼接起来，得到的序列即为森林的后序遍历。

    具体步骤如下：

    1. 对每棵树分别进行后序遍历。
    2. 将每棵树的后序遍历序列依次拼接起来，即可得到森林的后序遍历序列。

    例如，对以下森林进行后序遍历：

    1.  
    2.   B    C     D
    3.  / \        / \
    4. E   F      G   H
    5.

    首先分别对三棵树 B-EF、C、D-GH 进行后序遍历，得到它们的后序遍历序列：

    B-EF的后序遍历序列为：E F B

    C的后序遍历序列为：C

    D-GH的后序遍历序列为：G H D

    然后将它们依次拼接起来，得到森林的后序遍历序列：E F B C G H D

    4、树与二叉树的应用

    4.1哈夫曼树

    4.1.1概念

    哈夫曼树（Huffman Tree）是一种特殊的二叉树，它是一种最优二叉树，常用于数据压缩和编码中。哈夫曼树的构建过程是基于哈夫曼编码的原理，即将出现频率较高的字符用较短的编码，而出现频率较低的字符用较长的编码。哈夫曼树的构建过程是将每个字符作为一个节点，并将它们按照出现频率从小到大排序，然后将频率最小的两个节点合并成一个新的节点，其权值为两个节点的权值之和。重复这个过程，直到所有节点都被合并成为一个根节点为止。最后形成的这个根节点就是哈夫曼树的根节点。哈夫曼树的叶子节点表示原始数据中的字符，而路径上的0、1代表相应的比特位编码。哈夫曼树是一种满足最优化标准的树形结构，可以使编码后的数据更加紧凑，从而达到压缩数据的目的。

     

    4.1.2构造哈夫曼树

    哈夫曼树是一种带权路径长度最小的树，用于编码和数据压缩。构造哈夫曼树的过程如下：

    1. 将节点按权值从小到大排序，构造n个只含一个节点的二叉树，每个节点代表一个权值。
    2. 选择权值最小的两棵二叉树合并成一棵新二叉树，根节点的权值为这两棵二叉树的权值之和。
    3. 从已选的n棵二叉树中删除这两棵二叉树，将新的二叉树加入到集合中。
    4. 重复步骤2和步骤3，直到只剩下一棵二叉树，这棵树就是哈夫曼树。

    4.1.3哈夫曼编码

    将字符频次作为字符结点权值，构造哈夫曼树，即可得到哈夫曼编码，可用于数据压缩。

    前缀编码：没有一个编码 是另一个编码的前缀

    固定长度编码：每个字符用相等长度的二进制位表示

    可变长度编码： 允许对不同字符用不等长的二进制位表示

    哈夫曼编码的生成过程包括以下几个步骤：

    1. 统计每个字符在数据中出现的频率；
    2. 将每个字符和其对应的频率构建成一个叶子节点；
    3. 构建哈夫曼树，将每个节点按照频率从小到大排序，然后将相邻的两个节点合并成一个新节点，其频率为两个节点的频率之和。重复此过程，直到所有节点都合并为一个根节点；
    4. 给每个叶子节点分配一个编码，从根节点开始，向左走则编码为0，向右走则编码为1，直到到达叶子节点；
    5. 用每个字符的编码替换原始数据中相应的字符，从而得到压缩后的数据。

    4.1.4C语言实现哈夫曼树

    哈夫曼树是一种应用广泛的数据结构，用于有效地压缩数据。在C语言中，哈夫曼树的实现可以通过以下步骤完成：

    1. 定义节点结构体

    首先需要定义一个节点结构体，用于表示哈夫曼树中的每个节点。该结构体包含左子树、右子树、权值和字符等信息。

    1. struct HuffmanNode {
    2.     int weight;                // 权值
    3.     char ch;                   // 字符
    4.     struct HuffmanNode *left;  // 左子树
    5.     struct HuffmanNode *right; // 右子树
    6. };
    7.

    2. 定义比较函数

    比较函数用于在构建哈夫曼树时对节点进行排序。该函数将根据节点的权值大小进行比较。

    1. int cmp(const void *a, const void *b) {
    2.     const struct HuffmanNode *node1 = a;
    3.     const struct HuffmanNode *node2 = b;
    4.     return node1->weight - node2->weight;
    5. }
    6.

    3. 构建哈夫曼树

    构建哈夫曼树的过程可以通过一些简单的步骤完成。首先需要将每个字符作为一个叶子节点插入到优先队列中，然后不断地取出队列中权值最小的两个节点，将它们合并成一个新节点，并将新节点插入到队列中。重复此过程，直到队列中只剩下一个根节点，此时构建的就是哈夫曼树。

    1. struct HuffmanNode *buildHuffmanTree(const char *str) {
    2.     // 统计字符出现的次数
    3.     int count[256] = {0};
    4.     for (int i = 0; i < strlen(str); i++) {
    5.         count[str[i]]++;
    6.     }
    7.  
    8.     // 将每个字符作为一个叶子节点插入到优先队列中
    9.     int size = 0;
    10.     struct HuffmanNode *nodes[256];
    11.     for (int i = 0; i < 256; i++) {
    12.         if (count[i] > 0) {
    13.             nodes[size] = malloc(sizeof(struct HuffmanNode));
    14.             nodes[size]->ch = (char)i;
    15.             nodes[size]->weight = count[i];
    16.             nodes[size]->left = NULL;
    17.             nodes[size]->right = NULL;
    18.             size++;
    19.         }
    20.     }
    21.  
    22.     // 构建哈夫曼树
    23.     while (size > 1) {
    24.         // 取出队列中权值最小的两个节点
    25.         qsort(nodes, size, sizeof(struct HuffmanNode *), cmp);
    26.         struct HuffmanNode *left = nodes[0];
    27.         struct HuffmanNode *right = nodes[1];
    28.  
    29.         // 合并两个节点
    30.         struct HuffmanNode *parent = malloc(sizeof(struct HuffmanNode));
    31.         parent->ch = '\0';
    32.         parent->weight = left->weight + right->weight;
    33.         parent->left = left;
    34.         parent->right = right;
    35.  
    36.         // 将新节点插入到队列中
    37.         nodes[0] = parent;
    38.         for (int i = 2; i < size; i++) {
    39.             nodes[i - 1] = nodes[i];
    40.         }
    41.         size--;
    42.     }
    43.  
    44.     return nodes[0];
    45. }
    46.

    4. 遍历哈夫曼树

    遍历哈夫曼树可以得到每个字符的编码，即通过左子树走一步为0，右子树走一步为1。在遍历过程中，需要记录下从根节点到当前节点的路径上的字符编码，以便后续使用。

    1. void traverseHuffmanTree(struct HuffmanNode *node, char *code, int depth) {
    2.     if (node->left == NULL && node->right == NULL) {
    3.         // 叶子节点，输出编码
    4.         printf("%c: %s\n", node->ch, code);
    5.     } else {
    6.         // 遍历左子树
    7.         code[depth] = '0';
    8.         traverseHuffmanTree(node->left, code, depth + 1);
    9.  
    10.         // 遍历右子树
    11.         code[depth] = '1';
    12.         traverseHuffmanTree(node->right, code, depth + 1);
    13.     }
    14. }
    15.

    5. 完整代码

    将以上步骤整合起来，可以得到完整的C语言实现代码：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct HuffmanNode {
    6.     int weight;                // 权值
    7.     char ch;                   // 字符
    8.     struct HuffmanNode *left;  // 左子树
    9.     struct HuffmanNode *right; // 右子树
    10. };
    11.  
    12. int cmp(const void *a, const void *b) {
    13.     const struct HuffmanNode *node1 = a;
    14.     const struct HuffmanNode *node2 = b;
    15.     return node1->weight - node2->weight;
    16. }
    17.  
    18. struct HuffmanNode *buildHuffmanTree(const char *str) {
    19.     // 统计字符出现的次数
    20.     int count[256] = {0};
    21.     for (int i = 0; i < strlen(str); i++) {
    22.         count[str[i]]++;
    23.     }
    24.  
    25.     // 将每个字符作为一个叶子节点插入到优先队列中
    26.     int size = 0;
    27.     struct HuffmanNode *nodes[256];
    28.     for (int i = 0; i < 256; i++) {
    29.         if (count[i] > 0) {
    30.             nodes[size] = malloc(sizeof(struct HuffmanNode));
    31.             nodes[size]->ch = (char)i;
    32.             nodes[size]->weight = count[i];
    33.             nodes[size]->left = NULL;
    34.             nodes[size]->right = NULL;
    35.             size++;
    36.         }
    37.     }
    38.  
    39.     // 构建哈夫曼树
    40.     while (size > 1) {
    41.         // 取出队列中权值最小的两个节点
    42.         qsort(nodes, size, sizeof(struct HuffmanNode *), cmp);
    43.         struct HuffmanNode *left = nodes[0];
    44.         struct HuffmanNode *right = nodes[1];
    45.  
    46.         // 合并两个节点
    47.         struct HuffmanNode *parent = malloc(sizeof(struct HuffmanNode));
    48.         parent->ch = '\0';
    49.         parent->weight = left->weight + right->weight;
    50.         parent->left = left;
    51.         parent->right = right;
    52.  
    53.         // 将新节点插入到队列中
    54.         nodes[0] = parent;
    55.         for (int i = 2; i < size; i++) {
    56.             nodes[i - 1] = nodes[i];
    57.         }
    58.         size--;
    59.     }
    60.  
    61.     return nodes[0];
    62. }
    63.  
    64. void traverseHuffmanTree(struct HuffmanNode *node, char *code, int depth) {
    65.     if (node->left == NULL && node->right == NULL) {
    66.         // 叶子节点，输出编码
    67.         printf("%c: %s\n", node->ch, code);
    68.     } else {
    69.         // 遍历左子树
    70.         code[depth] = '0';
    71.         traverseHuffmanTree(node->left, code, depth + 1);
    72.  
    73.         // 遍历右子树
    74.         code[depth] = '1';
    75.         traverseHuffmanTree(node->right, code, depth + 1);
    76.     }
    77. }
    78.  
    79. int main() {
    80.     char str[] = "hello world";
    81.     struct HuffmanNode *root = buildHuffmanTree(str);
    82.  
    83.     char code[256];
    84.     traverseHuffmanTree(root, code, 0);
    85.  
    86.     return 0;
    87. }
    88.

    4.2并查集

    4.2.1逻辑结构

    并查集是一种用于处理集合并、查找和判定两个元素是否在同一集合中的数据结构。它的基本操作有初始化、查找、合并等。

    并查集的逻辑结构通常由一个数组和若干个操作函数构成。数组中每个元素对应一个集合，它的值表示当前元素所在集合的根节点编号。在初始化时，每个元素都是一个单独的集合，即它的根节点编号为自身。查找操作用于找到某个元素所在集合的根节点编号，它通过递归查找父节点的方式实现路径压缩。合并操作用于合并两个集合，它将其中一个集合的根节点编号设为另一个集合的根节点编号，从而实现两个集合的合并。

    并查集的优点是可以快速地进行集合合并和查找，时间复杂度为O(log n)。它常用于解决连通性问题，如判断图是否连通、求无向图的连通分量等。

    4.2.2基本操作

    并查集是一种用于维护集合的数据结构，通常支持以下操作：

    1. MakeSet(x)：创建一个新的集合，其中只包含元素 x。

    2. Union(x, y)：将包含元素 x 和 y 的两个集合合并成一个新集合。

    3. Find(x)：查找元素 x 所在的集合，并返回该集合的代表元素。

    通常还会有一些额外的操作，例如：

    4. SizeOf(x)：返回包含元素 x 的集合中元素的数量。

    5. IsConnected(x, y)：判断元素 x 和 y 是否在同一个集合中。

    6. CountSets()：返回当前并查集中集合的数量。

    在实现并查集的过程中，常见的数据结构有数组和树。使用数组实现时，每个元素的值表示其父节点的索引，根节点的父节点值为-1。使用树实现时，每个节点的父节点指向它的父节点。

    在 Find(x) 操作中，可以通过递归或迭代的方式将元素 x 所在的集合中的所有元素都指向该集合的代表元素，以达到路径压缩的效果，加快后续对同一集合的 Find 操作的速度。

    在 Union(x, y) 操作中，可以选择将一个集合的根节点作为另一个集合的子树，或者将两个集合的根节点合并成一个新的集合。通常建议采用按秩合并和路径压缩（即将深度较浅的树作为深度较深的树的子树）的算法，以保证并查集操作的时间复杂度为 O(α(n))，其中 α(n) 是反阿克曼函数的逆函数，增长极其缓慢，因此在实际应用中可以认为它是一个常数。

    4.2.3存储结构

    并查集的存储结构可以采用数组或树形结构。常用的是采用树形结构进行存储。 

    对于每个元素x，都有一个对应的父结点parent[x]，如果x是根结点，则parent[x]=-1。在初始化时，可以将每个元素看成一个独立的集合，即其父节点为其自身。随着不断的合并操作，两个元素所在的集合就会合并成为一棵树。

    在合并两个集合时，需要将其中一个集合的根节点的父结点设置为另一个集合的根节点。此时，其中一个树就成为另一个树的子树。

    通过路径压缩的技巧，可以使得树形结构更加扁平化，从而提高查询效率。具体而言，在查找某个元素所在的集合时，可以沿途将路径上的节点的父节点都设置为该集合的根节点，从而将树的高度降低，进一步提高查询效率。

    4.2.4优化

    并查集是一种数据结构，用于解决集合的合并和查询问题。在对大量数据进行操作时，为了提高效率，需要对并查集进行优化。

    以下是一些并查集的优化方法：

    1. 路径压缩：在 find 操作时，将路径上的所有节点都直接连接到根节点上，从而缩短查找路径的长度，减少操作的时间复杂度。

    2. 按秩合并：在合并两个集合时，将高度低的集合合并到高度高的集合中，从而保持树的平衡，减少操作的时间复杂度。

    3. 路径分裂：在路径压缩时，不仅将路径上的所有节点直接连接到根节点上，还可以将路径上的每个节点的父节点指向其祖先节点的子节点，从而减少路径压缩导致的树的深度增加。

    4. 路径减半：在路径压缩时，不仅将路径上的所有节点直接连接到根节点上，还可以将路径上每隔一个节点的父节点指向其祖先节点的父节点，从而减少路径压缩导致的树的深度增加。

    🤞❤️🤞❤️🤞❤️树与二叉树的知识点总结就到这里啦，如果对博文还满意的话，劳烦各位看官动动“发财的小手”留下您对博文的赞和对博主的关注吧🤞❤️🤞❤️🤞❤️

     

  • 相关阅读:
    如何判断对象是否是垃圾
    无法调试MFC源码
    后代选择器（非常重要）
    MyBatis #{} 和 ${} 的区别
    kettle 使用动态变量名定义变量
    mybatis中if的test如何判断双等号（==）
    【笔记】Java - VM options、Program arguments、Environment variables、eclipse variables
    FastAPI 作为H5中流式输出的后端
    基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的无人机目标检测系统（Python+PySide6界面+训练代码）
    Python环境的安装及配置
  • 原文地址：https://blog.csdn.net/qq_52442214/article/details/132945234