哈夫曼树求哈夫曼编码 c语言 数据结构

哈夫曼树是一种可以用来压缩数据的树形数据结构，它可以生成哈夫曼编码，从而实现对数据的高效压缩和解压缩。下面是一个简单的C语言实现。

首先，我们需要定义一个哈夫曼树节点的结构体：

struct huffman_node {
    char data;                  // 数据
    int weight;                 // 权重
    struct huffman_node *left;  // 左子节点
    struct huffman_node *right; // 右子节点
};

接下来，我们需要实现一个函数来创建哈夫曼树。该函数接受一个字符数组和对应的权重数组作为输入，返回哈夫曼树的根节点。

#include <stdlib.h>

struct huffman_node* create_huffman_tree(char data[], int weight[], int n) {
    // 创建叶子节点
    struct huffman_node** nodes = (struct huffman_node**)malloc(sizeof(struct huffman_node*) * n);
    for (int i = 0; i < n; i++) {
        nodes[i] = (struct huffman_node*)malloc(sizeof(struct huffman_node));
        nodes[i]->data = data[i];
        nodes[i]->weight = weight[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }

    // 构建哈夫曼树
    while (n > 1) {
        // 找到最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[0]->weight > nodes[1]->weight) {
            min1 = 1;
            min2 = 0;
        }
        for (int i = 2; i < n; i++) {
            if (nodes[i]->weight < nodes[min1]->weight) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->weight < nodes[min2]->weight) {
                min2 = i;
            }
        }

        // 创建新节点
        struct huffman_node* new_node = (struct huffman_node*)malloc(sizeof(struct huffman_node));
        new_node->data = 0;
        new_node->weight = nodes[min1]->weight + nodes[min2]->weight;
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];

        // 将新节点插入到数组中
        nodes[min1] = new_node;
        nodes[min2] = nodes[n - 1];
        n--;
    }

    // 返回根节点
    return nodes[0];
}

最后，我们需要实现一个函数来生成哈夫曼编码。该函数接受一个哈夫曼树的根节点作为输入，返回一个指向哈夫曼编码的指针数组。

#include <string.h>

void generate_huffman_code(struct huffman_node* root, char* code[], int depth, char buffer[]) {
    if (!root) {
        return;
    }

    // 处理叶子节点
    if (!root->left && !root->right) {
        buffer[depth] = '\0';
        code[root->data] = (char*)malloc(sizeof(char) * (depth + 1));
        strcpy(code[root->data], buffer);
        return;
    }

    // 处理左子树
    buffer[depth] = '0';
    generate_huffman_code(root->left, code, depth + 1, buffer);

    // 处理右子树
    buffer[depth] = '1';
    generate_huffman_code(root->right, code, depth + 1, buffer);
}

char** get_huffman_code(struct huffman_node* root) {
    char** code = (char**)malloc(sizeof(char*) * 256);
    char buffer[256];
    generate_huffman_code(root, code, 0, buffer);
    return code;
}

现在，我们可以使用上面的代码来创建一个哈夫曼树，并生成对应的哈夫曼编码。例如：

int main() {
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int weight[] = { 45, 13, 12, 16, 9, 5 };
    struct huffman_node* root = create_huffman_tree(data, weight, 6);
    char** code = get_huffman_code(root);
    for (int i = 0; i < 256; i++) {
        if (code[i]) {
            printf("%c: %s\n", i, code[i]);
        }
    }
    return 0;
}

输出结果为：

a: 0
b: 101
c: 100
d: 111
e: 1101
f: 1100