C语言哈夫曼树的构造和输出代码

哈夫曼树（Huffman Tree），又称为最优二叉树，是一种特殊的二叉树，常用于数据压缩算法如 Huffman 编码。在 C 语言中，我们可以手动构建哈夫曼树并输出其编码规则。以下是简单的步骤和代码示例：

**步骤**：
1. 创建一个结构体存储字符及其频率。
2. 使用优先队列（例如，最小堆）对字符进行排序。
3. 取出两个频率最低的节点合并成新的节点，新节点的频率为两者之和，左子节点为第一个节点，右子节点为第二个节点。
4. 将新节点插入优先队列，并更新频率先低的节点。
5. 重复步骤3和4，直到队列只剩下一个节点，即生成了哈夫曼树。

**C 语言代码示例**：

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

// 定义字符及其频率的结构体
typedef struct {
    char ch;
    int freq;
} Node;

// 比较函数，用于优先队列
int compare(const void *a, const void *b) {
    return ((Node *)a)->freq - ((Node *)b)->freq;
}

// 构建哈夫曼树
void huffmanTree(Node *nodes, int n, Node **huffTree) {
    // 优先队列
    priority_queue<Node*, std::vector<Node*>, decltype(compare)> pq(compare);

    for (int i = 0; i < n; ++i)
        pq.push(nodes + i);

    while (pq.size() > 1) {
        Node *left = pq.top(); pq.pop();
        Node *right = pq.top(); pq.pop();

        // 新节点
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->ch = '\0'; // 初始化为特殊字符
        newNode->freq = left->freq + right->freq;
        newNode->left = left;
        newNode->right = right;

        pq.push(newNode);
    }
    *huffTree = pq.top();
}

// 输出哈夫曼编码
void outputCodes(Node *root, int codeLength, char *codes) {
    if (!root)
        return;

    codes[root->ch] = codeLength++;
    outputCodes(root->left, codeLength, codes);
    outputCodes(root->right, codeLength, codes);
}

int main() {
    // 例子：给定字符和频率
    Node nodes[] = { {'a', 9}, {'b', 3}, {'c', 4}, {'d', 2} };
    int n = sizeof(nodes) / sizeof(nodes[0]);

    Node *huffTree = NULL;
    huffmanTree(nodes, n, &huffTree);

    // 假设初始编码长度为1
    char codes[256];
    outputCodes(huffTree, 1, codes);

    // 输出编码规则
    for (int i = 'a'; i <= 'd'; ++i)
        printf("%c -> %d\n", i, codes[i]);
    
    free(huffTree);
    return 0;
}

这个代码首先创建了一个哈夫曼树，然后计算每个字符的编码。注意，由于实际应用中需要动态分配内存，这里简化为了固定大小数组。在实际项目中，你需要处理字符集的范围可能会更大，因此代码需要适应这种情况。