树状结构（哈夫曼树）

哈夫曼树的构建过程基于哈夫曼编码的原理，即将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而实现对数据的压缩。

构建哈夫曼树的步骤如下：

1：统计待压缩数据中每个字符出现的频率。
2：将每个字符及其频率作为叶子节点构建一颗单节点的二叉树。
3：从这些单节点的二叉树中选择两个根节点权值最小的树进行合并，构建一颗新的二叉树。合并后的新树的根节点权值为两个子树根节点权值之和。
4：将新构建的二叉树作为一个单节点的树，并将其插入到剩余的单节点树中，重复步骤3，直到只剩下一棵树，即哈夫曼树。
5：最后生成的哈夫曼树的根节点即为整个树的根节点。

在哈夫曼树中，从根节点到每个叶子节点的路径上的编码就是每个字符的哈夫曼编码。由于频率高的字符对应的编码较短，频率低的字符对应的编码较长，这样就实现了对数据的高效压缩。

哈夫曼树在数据压缩、通信领域等方面有广泛的应用，它能够有效地减小数据的存储空间和传输带宽，提高数据传输的效率。

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树节点结构
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// 创建一个新的哈夫曼树节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建哈夫曼树
struct Node* buildHuffmanTree(int freq[], int size) {
    struct Node *left, *right, *top;

    // 创建一个节点数组，用于存储所有的哈夫曼树节点
    struct Node** nodes = (struct Node**)malloc(size * sizeof(struct Node*));

    // 根据频率数组创建初始的叶子节点
    for (int i = 0; i < size; i++) {
        nodes[i] = createNode(freq[i]);
    }

    // 不断合并最小的两个节点，直到只剩下一个节点，即根节点
    while (size > 1) {
        // 找到频率最小的两个节点
        left = nodes[size - 2];
        right = nodes[size - 1];

        // 创建一个新的节点作为它们的父节点
        top = createNode(left->data + right->data);
        top->left = left;
        top->right = right;

        // 将新节点插入合适的位置，保持节点数组有序
        int i = size - 2;
        while (i > 0 && nodes[i - 1]->data > top->data) {
            nodes[i] = nodes[i - 1];
            i--;
        }
        nodes[i] = top;

        // 更新节点数组的大小
        size--;
    }

    // 返回根节点
    return nodes[0];
}

// 打印哈夫曼树的编码
void printHuffmanCodes(struct Node* root, int arr[], int top) {
    // 当遇到叶子节点时，打印编码
    if (root->left == NULL && root->right == NULL) {
        printf("字符: %d，编码: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }

    // 在路径数组中的下一个位置存储0或1，并递归处理左右子树
    if (root->left) {
        arr[top] = 0;
        printHuffmanCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        printHuffmanCodes(root->right, arr, top + 1);
    }
}

int main() {
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(freq) / sizeof(freq[0]);

    struct Node* root = buildHuffmanTree(freq, size);

    int arr[100], top = 0;
    printHuffmanCodes(root, arr, top);

    return 0;
}