哈夫曼树的c语言代码

哈夫曼树（Huffman Tree），也称为最优二叉树，是构建用于数据压缩的一种特殊的二叉树。在C语言中实现哈夫曼树通常包括以下几个步骤：

1. **频率统计**：收集数据中各个字符的出现频率。

2. **构建初始集合**：创建一个包含所有字符及其频率的节点集合。

3. **合并操作**：不断从频率最低的两个节点中选择频率更低的节点，合并成一个新的节点，新节点的频率是两个子节点的频率之和，然后将新节点加入到集合中，直到只剩下一个节点。

4. **构建哈夫曼树**：最后剩下的那个节点就是哈夫曼树的根节点。

5. **编码生成**：根据哈夫曼树的结构，从根节点开始，向左走代表0，向右走代表1，生成每个字符的编码。

下面是一个简单的C语言实现哈夫曼树的例子（使用链表表示节点）：

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

typedef struct Node {
    char data;
    int freq;
    struct Node* left, *right;
} Node;

// 插入节点到堆
Node* insert(Node** heap, char data, int freq) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->freq = freq;
    newNode->left = newNode->right = NULL;

    // 插入堆的顶部
    newNode->left = *heap;
    if (*heap != NULL) {
        newNode->right = (*heap)->right;
        (*heap)->right = newNode;
    }
    *heap = newNode;

    // 保持堆的特性
    while (newNode->right && newNode->right->freq < newNode->freq) {
        Node* temp = newNode->right;
        newNode->right = newNode->right->right;
        temp->right = newNode;
        newNode = temp;
    }

    return newNode;
}

// 构建哈夫曼树
Node* buildHuffmanTree(int freq[], int n) {
    Node** heap = (Node**)malloc(n * sizeof(Node*));
    for (int i = 0; i < n; i++) {
        heap[i] = insert(heap, freq[i], i);
    }

    // 剩下的只有一个节点，即为哈夫曼树的根
    return heap;
}

// 主函数
void printCodes(Node* root, char codes[]) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        codes[root->data] = '0';
        printf("%c ", codes[root->data]);
    } else {
        printCodes(root->left, codes);
        printCodes(root->right, codes);
    }
}

int main() {
    // 示例：字符频率数组
    int freq[] = {3, 2, 4, 1};
    int n = sizeof(freq) / sizeof(freq);

    Node* huffmanRoot = buildHuffmanTree(freq, n);
    char codes[256];
    memset(codes, '\0', sizeof(codes));
    printCodes(huffmanRoot, codes);

    return 0;
}