c语言递归生成哈夫曼编码

好的，以下是递归生成哈夫曼编码的C语言代码实现：

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

#define MAX_TREE_HT 100

// 哈夫曼树结点
struct HuffmanNode {
    char data; // 数据
    int freq; // 频率
    struct HuffmanNode *left, *right; // 左右子树
};

// 哈夫曼编码表
struct HuffmanCode {
    char data; // 数据
    char bits[MAX_TREE_HT]; // 编码
};

// 建立哈夫曼树
struct HuffmanNode* build_huffman_tree(char data[], int freq[], int n) {
    struct HuffmanNode *left, *right, *parent;
    int i;
    struct HuffmanNode *nodes[n];
    for (i = 0; i < n; i++) {
        nodes[i] = (struct HuffmanNode*) malloc(sizeof(struct HuffmanNode));
        nodes[i]->data = data[i];
        nodes[i]->freq = freq[i];
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }

    while (n > 1) {
        // 找到频率最小的两个结点
        left = nodes[n - 1];
        right = nodes[n - 2];

        // 创建新结点作为它们的父结点
        parent = (struct HuffmanNode*) malloc(sizeof(struct HuffmanNode));
        parent->data = '\0';
        parent->freq = left->freq + right->freq;
        parent->left = left;
        parent->right = right;

        // 将新结点插入结点数组中，并按照频率从小到大排序
        nodes[n - 2] = parent;
        n--;

        for (i = n - 2; i >= 0; i--) {
            if (nodes[i]->freq > parent->freq) {
                nodes[i + 1] = nodes[i];
            } else {
                break;
            }
        }

        nodes[i + 1] = parent;
        n++;
    }

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

// 生成哈夫曼编码表
void build_huffman_table(struct HuffmanNode* root, char *bits, int len,
                          struct HuffmanCode huffman_table[]) {
    if (root->left == NULL && root->right == NULL) {
        int i;
        for (i = 0; i < len; i++) {
            huffman_table[(int) root->data].bits[i] = bits[i];
        }
        huffman_table[(int) root->data].bits[len] = '\0';
        huffman_table[(int) root->data].data = root->data;
    } else {
        bits[len] = '0';
        build_huffman_table(root->left, bits, len + 1, huffman_table);
        bits[len] = '1';
        build_huffman_table(root->right, bits, len + 1, huffman_table);
    }
}

int main() {
    char data[] = {'a', 'b', 'c', 'd'};
    int freq[] = {4, 2, 1, 3};
    int n = sizeof(data) / sizeof(data[0]);

    // 建立哈夫曼树
    struct HuffmanNode* root = build_huffman_tree(data, freq, n);

    // 生成哈夫曼编码表
    struct HuffmanCode huffman_table[256];
    char bits[MAX_TREE_HT];
    build_huffman_table(root, bits, 0, huffman_table);

    // 输出编码表
    int i;
    for (i = 0; i < 256; i++) {
        if (huffman_table[i].bits[0] != '\0') {
            printf("%c: %s\n", huffman_table[i].data, huffman_table[i].bits);
        }
    }

    return 0;
}

在这个实现中，我们使用了结构体来表示哈夫曼树结点和哈夫曼编码表。递归生成哈夫曼编码表的函数build_huffman_table采用了类似树的前序遍历的方式，对于当前遍历到的结点，如果它是叶子结点，则将其对应的编码存入哈夫曼编码表中；如果不是叶子结点，则分别遍历它的左右子树，并将当前比特位的值分别设置为0和1。