实现存放一个字符的哈夫曼树

哈夫曼树是一种用于数据压缩和解压缩的二叉树，其中每个叶节点都对应一个字符，其权值表示该字符在压缩前出现的频率。构建哈夫曼树的基本思想是通过反复合并权值最小的节点，从而使得树的总权值最小。

若要实现存放一个字符的哈夫曼树，可以按照以下步骤进行：

1. 统计每个字符在原数据中出现的频率，将这些频率作为节点的权值。
2. 将每个节点视为一棵只包含该节点的树。
3. 反复进行以下操作，直到只剩下一颗树：从森林中取出两棵权值最小的树合并，新树的权值为这两棵树的权值之和，新树的左右儿子分别为这两棵树。
4. 最后剩下的一颗树即为所求的哈夫曼树。

在哈夫曼树中，每个字符对应的叶节点可以记录该字符的编码，编码的生成方法是：从根节点出发，若向左走则为0，向右走则为1，一直走到叶节点即可。这样，对于任意一个字符，都可以通过查找其对应的叶节点来获得其编码。对于一个给定的字符串，可以通过对每个字符进行查找并记录其编码，最后将这些编码串联起来得到该字符串的哈夫曼编码。

相关问题

实现哈夫曼树和哈夫曼编码C语言

以下是C语言实现哈夫曼树和哈夫曼编码的示例代码：

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

#define MAX_NODE_NUM 256
#define MAX_CODE_LEN 256

struct huff_node {
    unsigned char ch;           // 字符
    unsigned int freq;          // 频率
    struct huff_node *left;     // 左子节点
    struct huff_node *right;    // 右子节点
};

struct huff_tree {
    struct huff_node *root;     // 根节点
};

// 初始化哈夫曼树节点
struct huff_node *init_node(unsigned char ch, unsigned int freq) {
    struct huff_node *node = (struct huff_node *) malloc(sizeof(struct huff_node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建哈夫曼树
struct huff_tree *create_huff_tree(unsigned int *freqs) {
    struct huff_node *nodes[MAX_NODE_NUM];
    int node_cnt = 0;
    int i, j;

    for (i = 0; i < MAX_NODE_NUM; i++) {
        if (freqs[i] > 0) {
            nodes[node_cnt++] = init_node(i, freqs[i]);
        }
    }

    while (node_cnt > 1) {
        unsigned int min_freq1 = -1, min_freq2 = -1;
        int min_idx1 = -1, min_idx2 = -1;

        for (i = 0; i < node_cnt; i++) {
            if (nodes[i]->freq < min_freq1) {
                min_freq2 = min_freq1;
                min_idx2 = min_idx1;
                min_freq1 = nodes[i]->freq;
                min_idx1 = i;
            } else if (nodes[i]->freq < min_freq2) {
                min_freq2 = nodes[i]->freq;
                min_idx2 = i;
            }
        }

        struct huff_node *new_node = init_node(0, min_freq1 + min_freq2);
        new_node->left = nodes[min_idx1];
        new_node->right = nodes[min_idx2];
        nodes[min_idx1] = new_node;
        nodes[min_idx2] = nodes[--node_cnt];
    }

    struct huff_tree *tree = (struct huff_tree *) malloc(sizeof(struct huff_tree));
    tree->root = nodes[0];
    return tree;
}

// 释放哈夫曼树节点及其子节点内存
void free_huff_node(struct huff_node *node) {
    if (node != NULL) {
        free_huff_node(node->left);
        free_huff_node(node->right);
        free(node);
    }
}

// 释放哈夫曼树内存
void free_huff_tree(struct huff_tree *tree) {
    free_huff_node(tree->root);
    free(tree);
}

// 计算哈夫曼编码
void calc_huff_code(struct huff_node *node, char **codes, char *buf, int len) {
    if (node->left == NULL && node->right == NULL) {
        buf[len] = '\0';
        codes[node->ch] = strdup(buf);
    } else {
        buf[len] = '0';
        calc_huff_code(node->left, codes, buf, len + 1);
        buf[len] = '1';
        calc_huff_code(node->right, codes, buf, len + 1);
    }
}

// 哈夫曼编码
void huff_encode(unsigned char *src, int src_len, char **codes, unsigned char *dst, int *dst_len) {
    int i, j, k;
    char *code;

    for (i = 0, k = 0; i < src_len; i++) {
        code = codes[src[i]];
        for (j = 0; j < strlen(code); j++) {
            if (code[j] == '0') {
                dst[k / 8] &= ~(1 << (7 - k % 8));
            } else {
                dst[k / 8] |= 1 << (7 - k % 8);
            }
            k++;
        }
    }

    *dst_len = (k + 7) / 8;
}

// 哈夫曼解码
void huff_decode(char *code, int code_len, struct huff_node *root, unsigned char *dst, int *dst_len) {
    int i;
    struct huff_node *node = root;

    for (i = 0; i < code_len; i++) {
        if (code[i] == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == NULL && node->right == NULL) {
            dst[*dst_len] = node->ch;
            (*dst_len)++;
            node = root;
        }
    }
}

int main() {
    unsigned char src[] = "hello, world!";
    int src_len = strlen(src);
    unsigned int freqs[MAX_NODE_NUM] = {0};
    char *codes[MAX_NODE_NUM] = {NULL};
    unsigned char dst[MAX_CODE_LEN] = {0};
    int dst_len;
    int i;

    // 统计字符频率
    for (i = 0; i < src_len; i++) {
        freqs[src[i]]++;
    }

    // 构建哈夫曼树
    struct huff_tree *tree = create_huff_tree(freqs);

    // 计算哈夫曼编码
    char buf[MAX_CODE_LEN];
    calc_huff_code(tree->root, codes, buf, 0);

    // 输出哈夫曼编码表
    for (i = 0; i < MAX_NODE_NUM; i++) {
        if (codes[i] != NULL) {
            printf("%c: %s\n", i, codes[i]);
        }
    }

    // 哈夫曼编码
    huff_encode(src, src_len, codes, dst, &dst_len);

    // 输出哈夫曼编码后的二进制数据
    for (i = 0; i < dst_len; i++) {
        printf("%02x ", dst[i]);
    }
    printf("\n");

    // 哈夫曼解码
    unsigned char decoded[MAX_CODE_LEN] = {0};
    int decoded_len = 0;
    char code[MAX_CODE_LEN];
    for (i = 0; i < dst_len * 8; i++) {
        if (dst[i / 8] & (1 << (7 - i % 8))) {
            code[i] = '1';
        } else {
            code[i] = '0';
        }
    }
    huff_decode(code, dst_len * 8, tree->root, decoded, &decoded_len);

    // 输出解码后的数据
    for (i = 0; i < decoded_len; i++) {
        printf("%c", decoded[i]);
    }
    printf("\n");

    // 释放内存
    for (i = 0; i < MAX_NODE_NUM; i++) {
        free(codes[i]);
    }
    free_huff_tree(tree);

    return 0;
}

该示例代码实现了哈夫曼树的构建、哈夫曼编码的计算、哈夫曼编码的实现和哈夫曼解码的实现。在使用时，只需要将需要编码的数据存放在一个 unsigned char 数组中，并传入该数组的长度，即可获得对应的哈夫曼编码后的二进制数据。在解码时，只需要将哈夫曼编码后的二进制数据转换为对应的字符数组即可。

哈夫曼树统计字符出现频率

要统计字符出现频率，可以使用哈希表（Hash Table）来实现。具体步骤如下：

1. 建立一个哈希表，用来存放每个字符出现的次数。

2. 遍历整个文本，对于每个字符，如果它在哈希表中已经存在，则将它的出现次数加1；否则，在哈希表中添加该字符，并将它的出现次数初始化为1。

3. 遍历哈希表，将每个字符和它的出现次数存入一个二元组中，然后将所有二元组存入一个列表中。

4. 对列表中的二元组按照字符出现的次数进行排序，可以使用快速排序等算法。

5. 构建哈夫曼树，根据每个字符出现的次数构建叶子节点，然后根据节点的权值（即出现次数）构建哈夫曼树。

6. 遍历哈夫曼树，可以得到每个字符的哈夫曼编码，即0和1的序列。