c 语言哈夫曼树构造

c语言中构造哈夫曼树的过程如下：

1. 创建一个结构体来表示哈夫曼树的节点，该结构体包含权值和指向左右子节点的指针。
2. 创建一个优先队列（最小堆）来存储所有的叶子节点，并按照权值从小到大的顺序排列。
3. 从优先队列中选取权值最小的两个节点，将它们合并为一个新的父节点，并将父节点插入到优先队列中。
4. 重复步骤3，直到队列中只剩下一个节点，即为根节点。
5. 构建完成后，根节点就是哈夫曼树的根。

下面是c语言的示例代码实现：

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

// 定义哈夫曼树的节点
struct Node {
    int weight;
    struct Node* left;
    struct Node* right;
};

// 创建一个新的节点
struct Node* createNode(int weight) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->weight = weight;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构造哈夫曼树
struct Node* buildHuffmanTree(int weights[], int n) {
    // 创建一个优先队列（最小堆）
    struct Node** queue = (struct Node**)malloc(n * sizeof(struct Node*));
    if (queue == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        queue[i] = createNode(weights[i]);
    }

    // 依次选择最小的两个节点构建哈夫曼树
    int size = n;
    while (size > 1) {
        struct Node* newNode = createNode(0);
        newNode->left = queue[0];
        newNode->right = queue[1];
        newNode->weight = newNode->left->weight + newNode->right->weight;

        int i = 2;
        while (i < size && newNode->weight > queue[i]->weight) {
            queue[i - 2] = queue[i];
            i++;
        }
        queue[i - 2] = newNode;
        size--;    }

    struct Node* root = queue[0];
    free(queue);
    return root;
}

// 释放哈夫曼树的内存
void freeHuffmanTree(struct Node* root) {
    if (root == NULL) {
        return;
    }
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    free(root);
}

int main() {
    int weights[] = {5, 9, 12, 13, 16, 45};
    int n = sizeof(weights) / sizeof(weights[0]);

    struct Node* root = buildHuffmanTree(weights, n);

    // 打印哈夫曼树的根节点权值
    printf("Huffman Tree root weight: %d\n", root->weight);

    // 释放哈夫曼树的内存
    freeHuffmanTree(root);

    return 0;
}