【数据结构】霍夫曼树

1.概念

霍夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。在霍夫曼树中，叶子节点的权值通常代表字符出现的频率，非叶子节点的权值是其子节点权值的和。霍夫曼树广泛应用于数据压缩，尤其是霍夫曼编码，它是一种基于字符出现频率的变长前缀编码。

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

1. 权值集合：首先，将给定的字符和它们对应的权值（频率）放入一个集合中。

2. 选择最小的权值：每次从集合中选出两个具有最小权值的节点，将它们合并成一个新节点，新节点的权值是这两个子节点权值的和。

3. 删除并添加：将选出的两个最小权值节点从集合中删除，并将新创建的节点添加到集合中。

4. 重复步骤2和3：重复步骤2和3，直到集合中只剩下一个节点，这个节点就是霍夫曼树的根节点。

5. 构建完成：此时，霍夫曼树构建完成，每个原始节点都成为了叶子节点，而新创建的节点都是非叶子节点。

霍夫曼编码的过程如下：

1. 为每个叶子节点分配码字：从根节点开始，向左的路径分配0，向右的路径分配1。这样，每个叶子节点都会得到一个唯一的二进制编码。

2. 构建编码表：将每个字符和它对应的霍夫曼编码放入一个编码表中。

3. 编码：使用编码表对原始数据进行编码，替换每个字符为其对应的霍夫曼编码。

4. 解码：解码时，从霍夫曼树的根节点开始，根据编码的0和1向左或向右移动。每次到达一个叶子节点，就输出对应的字符，然后从根节点开始继续解码过程。

霍夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀，这样可以保证编码的唯一可解性。由于频率高的字符分配的编码较短，频率低的字符分配的编码较长，因此霍夫曼编码能够实现数据的压缩。

2.如何自己实现霍夫曼编码？

实现霍夫曼编码需要定义数据结构来表示霍夫曼树节点，以及实现构建霍夫曼树和编码的过程。以下是一个简单的 C 语言实现。

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

// 定义霍夫曼树节点结构
typedef struct {
    char ch;                // 字符（仅用于叶子节点）
    int freq;               // 字符频率
    char code[100];         // 霍夫曼编码
    struct HuffmanNode *left, *right; // 左右子树指针
} HuffmanNode;

// 函数声明
HuffmanNode* createNode(int freq, char ch);
void printCodes(HuffmanNode* root, char* arr, int top);
void buildHuffmanTree(char ch[], int freq[], int size);
void destroyTree(HuffmanNode* root);

int main() {
    int n, i;
    printf("请输入字符的数量：");
    scanf("%d", &n);
    
    char ch[n];
    int freq[n];
    
    printf("请输入字符及其频率（例如：a 5）：\n");
    for(i = 0; i < n; i++) {
        scanf(" %c %d", &ch[i], &freq[i]);
    }
    
    buildHuffmanTree(ch, freq, n);
    
    return 0;
}

// 创建一个新的霍夫曼树节点
HuffmanNode* createNode(int freq, char ch) {
    HuffmanNode* newNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    newNode->ch = ch;
    newNode->freq = freq;
    newNode->left = newNode->right = NULL;
    strcpy(newNode->code, "");
    return newNode;
}

// 打印霍夫曼编码
void printCodes(HuffmanNode* root, char* arr, int top) {
    if (root->left) {
        arr[top] = '0';
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = '1';
        printCodes(root->right, arr, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: %s\n", root->ch, root->code);
        strcpy(root->code, arr);
    }
}

// 构建霍夫曼树
void buildHuffmanTree(char ch[], int freq[], int size) {
    HuffmanNode *left, *right, *top;
    
    // 创建一个节点数组
    HuffmanNode* nodes[size];
    for(int i = 0; i < size; i++) {
        nodes[i] = createNode(freq[i], ch[i]);
    }
    
    // 构建霍夫曼树
    for(int i = 0; i < size - 1; i++) {
        // 找到两个最小频率的节点
        HuffmanNode* min1 = NULL, *min2 = NULL;
        for(int j = 0; j < size; j++) {
            if(nodes[j] && (!min1 || nodes[j]->freq < min1->freq)) {
                min2 = min1;
                min1 = nodes[j];
            } else if(nodes[j] && (!min2 || nodes[j]->freq < min2->freq)) {
                min2 = nodes[j];
            }
        }
        
        // 创建一个新的内部节点
        top = createNode(min1->freq + min2->freq, '\0');
        top->left = min1;
        top->right = min2;
        
        // 从节点数组中移除已合并的节点
        nodes[size + i] = top;
        nodes[min1 - nodes] = NULL;
        nodes[min2 - nodes] = NULL;
    }
    
    // 打印霍夫曼编码
    char arr[100];
    printCodes(nodes[size + size - 2], arr, 0);
    
    // 释放内存
    for(int i = 0; i < size; i++) {
        destroyTree(nodes[i]);
    }
}

// 销毁霍夫曼树
void destroyTree(HuffmanNode* root) {
    if(root) {
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);
    }
}

这段代码定义了霍夫曼树节点的结构，并提供了一个简单的命令行界面来输入字符及其频率。然后，它构建了霍夫曼树并打印了每个字符的霍夫曼编码。最后，它释放了分配给霍夫曼树的内存。

请注意，这个实现是为了演示目的而简化的。在实际应用中，霍夫曼编码的构建和解析通常更复杂，需要处理更多的边缘情况和优化。

以上就是霍夫曼树的基本使用，本次代码分享到此结束，后续还会更新数据结构与算法的知识。最后的最后，还请大家点点赞，点点关注，谢谢大家！