赫夫曼树的构建和编码的c语言代码

赫夫曼树（Huffman Tree），也称为最优二叉树，是一种自底向上的贪心算法用于构建带权路径长度最短的二叉树，常用于数据压缩。以下是简单的C语言代码示例，它展示了如何构造赫夫曼树并生成相应的编码：

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

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

Node* newNode(char data, int freq) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

void insert(Node** root, char data) {
    if (*root == NULL) {
        *root = newNode(data, 1);
    } else {
        Node* temp = *root, *parent;
        while (temp != NULL) {
            parent = temp;
            if (data < temp->data)
                temp = temp->left;
            else
                temp = temp->right;
        }
        if (data < parent->data)
            parent->left = newNode(data, 1);
        else
            parent->right = newNode(data, 1);
    }
}

Node* buildHuffmanTree(Node** heap) {
    if (heap[0] == NULL || heap[1] == NULL)
        return heap[0];
    Node* left = buildHuffmanTree(heap + 2);
    Node* right = buildHuffmanTree(heap + 4);
    Node* temp = newNode('\0', left->freq + right->freq);
    temp->left = left;
    temp->right = right;
    qsort(heap, 6, sizeof(Node*), compare);
    return heap[0];
}

int compare(const void* a, const void* b) {
    return (*(Node**)b)->freq - (*(Node**)a)->freq;
}

void printCodes(Node* root, char* code, int len) {
    if (root == NULL)
        return;
    if (root->left == NULL && root->right == NULL) {
        printf("%c = %.*s\n", root->data, len, code);
    } else {
        len++;
        printCodes(root->left, code, len);
        printCodes(root->right, code + "1", len);
    }
}

int main() {
    // 初始化节点数组
    Node* heap[6];
    // 插入数据...
    insert(&heap[0], 'A');
    insert(&heap[1], 'B');
    // 构建赫夫曼树
    heap[2] = heap[3] = NULL; // 分隔符
    Node* huffmanRoot = buildHuffmanTree(heap);
    // 打印编码
    char code[50];
    printCodes(huffmanRoot, code, 0);
    return 0;
}

这个程序首先插入字符及其频率到堆中，然后通过递归构建赫夫曼树，并利用`printCodes`函数打印出每个字符的编码。