通俗易懂的解释哈夫曼树并用C语言实现

哈夫曼树是一种特殊的二叉树，用于压缩数据。它的特点是，将频率较高的字符用较短的编码表示，而将频率较低的字符用较长的编码表示，以达到压缩数据的目的。

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

1. 将所有字符及其频率按照频率从小到大的顺序排列，构成一个森林，每个节点都是一棵只包含一个字符的树。
2. 从森林中选出两棵根节点权值最小的树，将它们合并成一棵新的树，新树的根节点的权值为两棵子树的权值之和。
3. 将新树插入到森林中，重复步骤2，直至森林中只剩下一棵树，即哈夫曼树。

下面是用C语言实现哈夫曼树的代码：

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

#define MAX_TREE_SIZE 1000

typedef struct {
    int weight; // 权值
    int parent; // 父节点在数组中的下标
    int lchild, rchild; // 左右孩子在数组中的下标
} HTNode, *HuffmanTree;

typedef char **HuffmanCode; // 编码表

// 选择两个权值最小的节点
void select(HuffmanTree tree, int n, int *s1, int *s2) {
    int min1 = 0, min2 = 0;
    for (int i = 1; i <= n; i++) {
        if (tree[i].parent == 0) {
            if (tree[i].weight < tree[min1].weight) {
                min2 = min1;
                min1 = i;
            } else if (tree[i].weight < tree[min2].weight) {
                min2 = i;
            }
        }
    }
    *s1 = min1;
    *s2 = min2;
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *tree, int *w, int n) {
    if (n <= 1) return;

    int m = 2 * n - 1;
    *tree = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));

    // 初始化前n个节点
    for (int i = 1; i <= n; i++) {
        (*tree)[i].weight = w[i];
        (*tree)[i].parent = 0;
        (*tree)[i].lchild = 0;
        (*tree)[i].rchild = 0;
    }

    // 构建哈夫曼树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        select(*tree, i - 1, &s1, &s2);
        (*tree)[s1].parent = i;
        (*tree)[s2].parent = i;
        (*tree)[i].lchild = s1;
        (*tree)[i].rchild = s2;
        (*tree)[i].weight = (*tree)[s1].weight + (*tree)[s2].weight;
    }
}

// 生成哈夫曼编码
void createHuffmanCode(HuffmanTree tree, HuffmanCode *code, int n) {
    *code = (HuffmanCode) malloc((n + 1) * sizeof(char *));
    char *temp = (char *) malloc(n * sizeof(char)); // 临时存储编码

    for (int i = 1; i <= n; i++) {
        int start = n - 1;
        int j = i;
        int parent = tree[i].parent;
        while (parent != 0) {
            if (tree[parent].lchild == j) {
                temp[start] = '0';
            } else {
                temp[start] = '1';
            }
            start--;
            j = parent;
            parent = tree[j].parent;
        }
        (*code)[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy((*code)[i], &temp[start + 1]);
    }
    free(temp);
}

int main() {
    int n;
    scanf("%d", &n);

    int *w = (int *) malloc((n + 1) * sizeof(int));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }

    HuffmanTree tree;
    createHuffmanTree(&tree, w, n);

    HuffmanCode code;
    createHuffmanCode(tree, &code, n);

    // 输出每个字符的编码
    for (int i = 1; i <= n; i++) {
        printf("%d: %s\n", i, code[i]);
    }

    return 0;
}

在这个代码中，我们定义了 `HTNode` 结构体来表示哈夫曼树的节点，用 `HuffmanTree` 来表示整棵树，用 `HuffmanCode` 来表示编码表。我们使用了 `select` 函数来选择两个权值最小的节点，使用 `createHuffmanTree` 函数来构建哈夫曼树，使用 `createHuffmanCode` 函数来生成编码表，最后输出每个字符的编码。

需要注意的是，这个代码中只考虑了字符的权值，实际应用中还需要考虑字符的出现次数。