求解哈夫曼树HuffmanTree以及C语言实现

哈夫曼树的实现思想是基于贪心算法。哈夫曼树的构建过程基于字符出现的频率或权重。在压缩数据时，出现频率较高的字符被编码为较短的二进制码，而出现频率较低的字符则被编码为较长的二进制码，以达到压缩数据的目的。
求解步骤： 创建一个优先队列（最小堆），用于存储待构建哈夫曼树的节点。对于每个字符，创建一个节点，并将该节点插入到优先队列中。节点的频率可以是字符在文本中出现的次数或者其他预定义的权重。从优先队列中提取出两个频率最小的节点作为左右子节点，并创建一个新节点作为它们的父节点。新节点的频率是左右子节点频率之和。将新节点插入优先队列中。重复上述操作，直到优先队列中只剩下一个节点，即根节点。

代码示例: Node表示哈夫曼树的节点，包含字符数据、频率和左右子节点指针；PriorityQueue表示优先队列，用于构建哈夫曼树，包含队列的大小、容量和节点指针数组。

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

// 定义哈夫曼树的节点结构
struct Node {
    char data;           // 节点存储的字符数据
    int freq;            // 节点对应字符的频率
    struct Node* left;   // 左子节点指针
    struct Node* right;  // 右子节点指针
};

// 定义优先队列结构，用于构建哈夫曼树
struct PriorityQueue {
    int size;               // 当前队列中的节点个数
    int capacity;           // 队列的最大容量
    struct Node** nodes;    // 节点指针数组
};

// 创建一个新的节点
struct Node* createNode(char data, int freq) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建优先队列
struct PriorityQueue* createPriorityQueue(int capacity) {
    struct PriorityQueue* queue = (struct PriorityQueue*)malloc(sizeof(struct PriorityQueue));
    queue->size = 0;
    queue->capacity = capacity;
    queue->nodes = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return queue;
}

// 交换两个节点的位置
void swap(struct Node** a, struct Node** b) {
    struct Node* temp = *a;
    *a = *b;
    *b = temp;
}

// 最小堆调整
void minHeapify(struct PriorityQueue* queue, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    // 找到子节点中值最小的节点
    if (left < queue->size && queue->nodes[left]->freq < queue->nodes[smallest]->freq)
        smallest = left;

    if (right < queue->size && queue->nodes[right]->freq < queue->nodes[smallest]->freq)
        smallest = right;

    // 如果最小节点不是当前节点，则交换位置，并递归调整
    if (smallest != idx) {
        swap(&queue->nodes[idx], &queue->nodes[smallest]);
        minHeapify(queue, smallest);
    }
}

// 判断队列中是否只有一个节点
int isSizeOne(struct PriorityQueue* queue) {
    return queue->size == 1;
}

// 从队列中提取最小节点
struct Node* extractMin(struct PriorityQueue* queue) {
    struct Node* minNode = queue->nodes[0];
    queue->nodes[0] = queue->nodes[queue->size - 1];
    --queue->size;
    minHeapify(queue, 0);
    return minNode;
}

// 向队列中插入一个节点
void insert(struct PriorityQueue* queue, struct Node* node) {
    ++queue->size;
    int i = queue->size - 1;
    while (i && node->freq < queue->nodes[(i - 1) / 2]->freq) {
        queue->nodes[i] = queue->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    queue->nodes[i] = node;
}

// 判断节点是否为叶节点
int isLeaf(struct Node* root) {
    return !(root->left) && !(root->right);
}

// 打印哈夫曼编码
void printCodes(struct Node* root, unsigned int code, unsigned int bitCount) {
    if (root) {
        // 如果是叶节点，则打印字符和对应的编码
        if (isLeaf(root)) {
            printf("%c: ", root->data);

            // 根据编码的位数逐位输出
            unsigned int mask = 1 << (bitCount - 1);
            while (mask) {
                if (code & mask)
                    printf("1");
                else
                    printf("0");
                mask >>= 1;
            }
            printf("n");
        }

        // 递归打印左右子树的编码
        printCodes(root->left, code << 1, bitCount + 1);
        printCodes(root->right, (code << 1) | 1, bitCount + 1);
    }
    }

}

// 构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int freq[], int size) {
    struct Node *left, *right, *top;
    struct PriorityQueue* queue = createPriorityQueue(size);

    // 将字符和频率作为节点插入优先队列
    for (int i = 0; i < size; ++i)
        insert(queue, createNode(data[i], freq[i]));

    // 从优先队列中取出两个最小频率的节点，合并成一个新节点
    // 直到队列中只剩下一个节点，即根节点
    while (!isSizeOne(queue)) {
        left = extractMin(queue);
        right = extractMin(queue);
        top = createNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insert(queue, top);
    }

    return extractMin(queue);
}

// 打印哈夫曼编码
void huffmanCodes(char data[], int freq[], int size) {
    struct Node* root = buildHuffmanTree(data, freq, size);
    unsigned int code = 0;
    unsigned int bitCount = 0;
    printCodes(root, code, bitCount);
}

int main() {
    char data[] = { 'A', 'B', 'C', 'D', 'E' };
    int freq[] = { 5, 9, 12, 13, 16 };
    int size = sizeof(data) / sizeof(data[0]);

    huffmanCodes(data, freq, size);

    return 0;
}

最小堆是一种二叉树，其中每个节点的值都小于或等于其子节点的值。