哈夫曼树与哈夫曼编码C语言

哈夫曼树是一种树形结构，它的节点可以是字符或者权值，构建哈夫曼树的过程就是根据权值构建一颗满足最小带权路径长度的树。

在哈夫曼树构建完成后，我们可以根据哈夫曼树来实现哈夫曼编码。哈夫曼编码是一种变长编码，用于将字符编码为二进制数，使得出现频率高的字符编码短，出现频率低的字符编码长。

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

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

#define MAX_NODES 256

typedef struct node {
    int value;
    char ch;
    struct node *left;
    struct node *right;
} Node;

typedef struct heap {
    Node *nodes[MAX_NODES];
    int size;
} Heap;

Node *new_node(int value, char ch) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->value = value;
    node->ch = ch;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Heap *new_heap() {
    Heap *heap = (Heap *) malloc(sizeof(Heap));
    heap->size = 0;
    return heap;
}

void swap_node(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void insert_node(Heap *heap, Node *node) {
    heap->nodes[++heap->size] = node;
    int current = heap->size;
    while (current > 1 && heap->nodes[current]->value < heap->nodes[current / 2]->value) {
        swap_node(&heap->nodes[current], &heap->nodes[current / 2]);
        current /= 2;
    }
}

Node *get_min_node(Heap *heap) {
    Node *min_node = heap->nodes[1];
    heap->nodes[1] = heap->nodes[heap->size--];
    int current = 1;
    while (current * 2 <= heap->size) {
        int child = current * 2;
        if (child + 1 <= heap->size && heap->nodes[child + 1]->value < heap->nodes[child]->value) {
            child++;
        }
        if (heap->nodes[child]->value < heap->nodes[current]->value) {
            swap_node(&heap->nodes[child], &heap->nodes[current]);
            current = child;
        } else {
            break;
        }
    }
    return min_node;
}

void build_tree(Heap *heap) {
    while (heap->size > 1) {
        Node *left = get_min_node(heap);
        Node *right = get_min_node(heap);
        Node *parent = new_node(left->value + right->value, '\0');
        parent->left = left;
        parent->right = right;
        insert_node(heap, parent);
    }
}

void print_codes(Node *root, char code[], int index) {
    if (root == NULL) {
        return;
    }
    if (root->ch != '\0') {
        code[index] = '\0';
        printf("%c: %s\n", root->ch, code);
    }
    code[index] = '0';
    print_codes(root->left, code, index + 1);
    code[index] = '1';
    print_codes(root->right, code, index + 1);
}

void huffman_codes(char *input) {
    Heap *heap = new_heap();
    int freq[MAX_NODES] = {0};
    for (int i = 0; i < strlen(input); i++) {
        freq[input[i]]++;
    }
    for (int i = 0; i < MAX_NODES; i++) {
        if (freq[i] > 0) {
            insert_node(heap, new_node(freq[i], i));
        }
    }
    build_tree(heap);
    char code[MAX_NODES];
    printf("Huffman Codes:\n");
    print_codes(heap->nodes[1], code, 0);
}

int main() {
    char input[] = "hello world";
    huffman_codes(input);
    return 0;
}

在上述代码中，我们定义了一个节点结构体（Node）和一个堆结构体（Heap）。我们使用堆来保存哈夫曼树的节点，在构建哈夫曼树时，我们将频率最小的两个节点合并为一个节点，并将其插入到堆中。构建完成后，我们使用递归的方式遍历哈夫曼树获取每个字符的编码，最后输出所有字符的哈夫曼编码。