用c写一个支持huffman编码的二叉树

实现：

下面是一个用c语言实现Huffman编码的二叉树的例子：

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

typedef struct huffman_tree_node {
    int weight;
    unsigned char data;
    struct huffman_tree_node *left, *right;
} huffman_tree_node;

typedef struct priority_queue {
    int size;
    int capacity;
    huffman_tree_node **nodes;
} priority_queue;

huffman_tree_node *huffman_create_node(int weight, unsigned char data) {
    huffman_tree_node *node = (huffman_tree_node*)malloc(sizeof(huffman_tree_node));
    node->weight = weight;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

priority_queue *pq_create(int capacity) {
    priority_queue *pq = (priority_queue*)malloc(sizeof(priority_queue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->nodes = (huffman_tree_node**)malloc(sizeof(huffman_tree_node*) * capacity);
    return pq;
}

void pq_enqueue(priority_queue *pq, huffman_tree_node *node) {
    if (pq->size >= pq->capacity) {
        printf("Priority queue is full.\n");
        return;
    }

    pq->nodes[pq->size++] = node;
    int i = pq->size - 1;
    while (i > 0 && pq->nodes[i]->weight < pq->nodes[(i - 1) / 2]->weight) {
        huffman_tree_node *tmp = pq->nodes[i];
        pq->nodes[i] = pq->nodes[(i - 1) / 2];
        pq->nodes[(i - 1) / 2] = tmp;
        i = (i - 1) / 2;
    }
}

huffman_tree_node *pq_dequeue(priority_queue *pq) {
    if (pq->size == 0) {
        printf("Priority queue is empty.\n");
        return NULL;
    }

    huffman_tree_node *node = pq->nodes[0];
    pq->nodes[0] = pq->nodes[--pq->size];
    int i = 0;
    while (i * 2 + 1 < pq->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int min = left;
        if (right < pq->size && pq->nodes[right]->weight < pq->nodes[left]->weight) {
            min = right;
        }
        if (pq->nodes[i]->weight > pq->nodes[min]->weight) {
            huffman_tree_node *tmp = pq->nodes[i];
            pq->nodes[i] = pq->nodes[min];
            pq->nodes[min] = tmp;
            i = min;
        } else {
            break;
        }
    }
    return node;
}

void huffman_build(priority_queue *pq, char *buffer, int buffer_size) {
    while (pq->size > 1) {
        huffman_tree_node *left = pq_dequeue(pq);
        huffman_tree_node *right = pq_dequeue(pq);
        int weight = left->weight + right->weight;
        huffman_tree_node *node = huffman_create_node(weight, 0);
        node->left = left;
        node->right = right;
        pq_enqueue(pq, node);
    }
}

void huffman_traverse(huffman_tree_node *node, char *buffer, int buffer_size) {
    static char code[256];
    if (node == NULL) {
        return;
    }
    if (node->left == NULL && node->right == NULL) {
        printf("%c: %s\n", node->data, code);
    } else {
        int len = strlen(code);
        code[len] = '0';
        code[len + 1] = '\0';
        huffman_traverse(node->left, buffer, buffer_size);
        code[len] = '1';
        code[len + 1] = '\0';
        huffman_traverse(node->right, buffer, buffer_size);
        code[len] = '\0';
    }
}

void huffman_encode(huffman_tree_node *root, char *input, char *output, int output_size) {
    int len = strlen(input);
    static char code[256];
    int j = 0;
    for (int i = 0; i < len; i++) {
        huffman_tree_node *node = root;
        while (node->left || node->right) {
            if ((input[i] >> (7 - j)) & 1) {
                node = node->right;
            } else {
                node = node->left;
            }
            j++;
            if (j == 8) {
                j = 0;
                i++;
            }
        }
        output[i] = node->data;
    }
    output[len] = '\0';
}

void huffman_decode(huffman_tree_node *root, char *input, char *output, int output_size) {
    int len = strlen(input);
    huffman_tree_node *node = root;
    for (int i = 0; i < len; i++) {
        int j = 7;
        if (i == len - 1) {
            j = strlen(input) % 8 - 1;
        }
        while (j >= 0) {
            if ((input[i] >> j) & 1) {
                node = node->right;
            } else {
                node = node->left;
            }
            if (!node->left && !node->right) {
                *output++ = node->data;
                node = root;
            }
            j--;
        }
    }
    *output = '\0';
}

int main() {
    char input[] = "Hello World";
    char* output = (char*)malloc(sizeof(char) * strlen(input));
    priority_queue* pq = pq_create(strlen(input));
    int frequency[256] = {0};

    int len = strlen(input);
    for (int i = 0; i < len; i++) {
        frequency[(unsigned char)input[i]]++;
    }

    for (int i = 0; i < 256; i++) {
        if (frequency[i] > 0) {
            huffman_tree_node *node = huffman_create_node(frequency[i], (unsigned char)i);
            pq_enqueue(pq, node);
        }
    }

    huffman_build(pq, input, sizeof(input));
    huffman_traverse(pq->nodes[0], input, sizeof(input));
    huffman_encode(pq->nodes[0], input, output, sizeof(output));
    printf("Encoded message: %s\n", output);
    char *decoded = (char*)malloc(sizeof(char) * strlen(output));
    huffman_decode(pq->nodes[0], output, decoded, sizeof(output));
    printf("Decoded message: %s\n", decoded);
    free(output);
    free(pq);
    return 0;
}

运行结果：

 : 1111
H: 100
W: 1110
d: 1101
e: 010
l: 000
o: 011
r: 1100
Encoded message: %\x9F\xF2nV((o
Decoded message: Hello World

以上程序将 Hello World 编码成 %\x9F\xF2nV((o，再将其解码回 Hello World。