haffman树的构造原理

Huffman树是一种经典的数据压缩算法，其构造原理如下：

1. 统计每个字符出现的频率，将其存储在一个频率表中。

2. 将频率表中的所有字符按照出现频率从小到大排序。

3. 选取出现频率最小的两个字符，构造一个只有这两个字符的二叉树，其中出现频率较小的字符作为左子树，出现频率较大的字符作为右子树。同时将这两个字符的频率相加，作为新节点的频率。

4. 将新节点插入频率表中，并将频率表按照出现频率从小到大排序。

5. 重复3和4步骤，直到只剩下一个节点，此时生成的二叉树即为Huffman树。

6. 对于每个叶子节点，将其对应的字符编码为从根节点到该叶子节点的路径上的0和1，其中向左走为0，向右走为1。

7. 将所有字符编码拼接在一起，即为压缩后的结果。

通过上述步骤，Huffman树能够将出现频率较高的字符用较少的比特数表示，从而实现数据压缩的目的。

相关问题

写函数以字母出现次数作权值,建haffman树(n个叶子),给出每个字母的haffman编码。

要实现这样的函数，首先需要统计每个字母在给定字符串中出现的次数，并按照次数给字母分配权值。接着，使用哈弗曼算法构建哈弗曼树，并根据哈弗曼树给每个字母生成对应的哈弗曼编码。

下面是一个实现这个功能的函数的例子：

def huffman_encoding(s):
    # 统计字母出现次数，生成权值列表
    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    weight_list = [(count[char], char) for char in count]

    # 构建哈弗曼树
    while len(weight_list) > 1:
        weight_list.sort()
        min1 = weight_list.pop(0)
        min2 = weight_list.pop(0)
        weight_list.append((min1[0]+min2[0], [min1[1], min2[1]]))

    # 生成哈弗曼编码
    codes = {}
    def traverse(node, code):
        if isinstance(node[1], list):
            traverse(node[1][0], code + "0")
            traverse(node[1][1], code + "1")
        else:
            codes[node[1]] = code

    traverse(weight_list[0], "")

    return codes

调用这个函数并传入一个字符串，将会返回一个字典，其中键是各个字母，值是对应的哈弗曼编码。

C语言 写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。

下面是基于哈夫曼编码的 C 语言实现代码：

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

#define MAX_LETTERS 26

typedef struct Node {
    int weight;
    int parent;
    int lchild;
    int rchild;
    char code[MAX_LETTERS];
} Node;

void build_huffman_tree(Node *nodes, int n);
void generate_huffman_code(Node *nodes, int n);

int main() {
    // 初始化字符出现次数
    int freq[MAX_LETTERS] = {0};
    char str[] = "hello world";
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[str[i] - 'a']++;
    }

    // 构建哈夫曼树
    Node nodes[MAX_LETTERS * 2 - 1];
    int n = MAX_LETTERS;
    for (int i = 0; i < n; i++) {
        nodes[i].weight = freq[i];
        nodes[i].parent = -1;
        nodes[i].lchild = -1;
        nodes[i].rchild = -1;
    }
    build_huffman_tree(nodes, n);

    // 生成哈夫曼编码
    generate_huffman_code(nodes, n);

    // 输出每个字符的哈夫曼编码
    for (int i = 0; i < n; i++) {
        printf("%c: %s\n", i + 'a', nodes[i].code);
    }

    return 0;
}

void build_huffman_tree(Node *nodes, int n) {
    int min1, min2;
    for (int i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 0;
        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].weight < nodes[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (nodes[j].weight < nodes[min2].weight) {
                    min2 = j;
                }
            }
        }
        nodes[min1].parent = i;
        nodes[min2].parent = i;
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[i].lchild = min1;
        nodes[i].rchild = min2;
    }
}

void generate_huffman_code(Node *nodes, int n) {
    for (int i = 0; i < n; i++) {
        int j = i;
        int parent = nodes[j].parent;
        while (parent != -1) {
            if (nodes[parent].lchild == j) {
                strcat(nodes[i].code, "0");
            } else {
                strcat(nodes[i].code, "1");
            }
            j = parent;
            parent = nodes[j].parent;
        }
        strrev(nodes[i].code);
    }
}

代码中，我们首先统计字符串中每个字母出现的次数，然后根据出现次数构建哈夫曼树，最后根据哈夫曼树生成每个字母的哈夫曼编码。在生成哈夫曼编码时，我们从每个叶子节点出发，沿着其父节点一直到根节点，记录下所经过的路径（0 表示左子树，1 表示右子树），然后把路径逆序，就得到了该叶子节点的哈夫曼编码。