【数据结构】霍夫曼树

发布于:2024-04-25 ⋅ 阅读:(24) ⋅ 点赞:(0)

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);
    }
}

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

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

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


网站公告

今日签到

点亮在社区的每一天
去签到