写一个构造哈夫曼树的函数，用c语言实现

以下是一个简单的构造哈夫曼树的函数，使用C语言实现：

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

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

typedef struct {
    int size;
    Node **data;
} PriorityQueue;

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

PriorityQueue *createPriorityQueue(int maxSize) {
    PriorityQueue *pq = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    pq->size = 0;
    pq->data = (Node **) malloc(maxSize * sizeof(Node *));
    return pq;
}

void swap(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void enqueue(PriorityQueue *pq, Node *node) {
    pq->data[pq->size++] = node;
    int child = pq->size - 1;
    int parent = (child - 1) / 2;
    while (child > 0 && pq->data[child]->freq < pq->data[parent]->freq) {
        swap(&pq->data[child], &pq->data[parent]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

Node *dequeue(PriorityQueue *pq) {
    Node *node = pq->data[0];
    pq->data[0] = pq->data[--pq->size];
    int parent = 0;
    int child = 2 * parent + 1;
    while (child < pq->size) {
        if (child + 1 < pq->size && pq->data[child + 1]->freq < pq->data[child]->freq) {
            child++;
        }
        if (pq->data[parent]->freq <= pq->data[child]->freq) {
            break;
        }
        swap(&pq->data[parent], &pq->data[child]);
        parent = child;
        child = 2 * parent + 1;
    }
    return node;
}

Node *constructHuffmanTree(char *data, int *freq, int size) {
    PriorityQueue *pq = createPriorityQueue(size);
    for (int i = 0; i < size; i++) {
        Node *node = createNode(freq[i], data[i]);
        enqueue(pq, node);
    }
    while (pq->size > 1) {
        Node *left = dequeue(pq);
        Node *right = dequeue(pq);
        Node *parent = createNode(left->freq + right->freq, '\0');
        parent->left = left;
        parent->right = right;
        enqueue(pq, parent);
    }
    return dequeue(pq);
}

void printHuffmanTree(Node *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    printHuffmanTree(root->left);
    printHuffmanTree(root->right);
}

int main() {
    char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(data) / sizeof(data[0]);
    Node *root = constructHuffmanTree(data, freq, size);
    printf("Preorder traversal of constructed Huffman tree: ");
    printHuffmanTree(root);
    return 0;
}

在这个实现中，我们首先定义了一个节点结构体 Node，用于表示哈夫曼树的节点。每个节点包含一个频率 freq，一个字符 data，以及左子树和右子树的指针 left 和 right。

我们还定义了一个优先队列结构体 PriorityQueue，用于存储节点，并按照频率从小到大排序。我们使用堆实现了这个优先队列，enqueue 函数用于插入一个节点，dequeue 函数用于弹出优先级最高的节点。

最后，我们实现了一个 constructHuffmanTree 函数，用于构造哈夫曼树。该函数接受一个字符数组 data，一个频率数组 freq，以及数组大小 size。它首先将每个字符和频率封装成一个节点，插入到优先队列中。然后，它不断地从优先队列中弹出两个频率最小的节点，并将它们合并成一个新节点。新节点的频率是左右子树的频率之和，左子树和右子树分别为被弹出的两个节点。最后，当优先队列中只剩一个节点时，它就是哈夫曼树的根节点。