哈夫曼树的构造c语言

以下是一个简单的C语言实现哈夫曼树的构造过程：

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

//定义哈夫曼树结构体
typedef struct HuffmanTreeNode {
    int weight; //权值
    int parent; //父节点下标
    int left; //左子节点下标
    int right; //右子节点下标
} HuffmanTreeNode;

//构造哈夫曼树
void createHuffmanTree(HuffmanTreeNode *huffmanTree, int n) {
    int i, j, k, min1, min2;
    int *weight; //存储每个节点的权值
    int *parent; //存储每个节点的父节点
    int *left; //存储每个节点的左子节点
    int *right; //存储每个节点的右子节点

    //动态分配内存
    weight = (int*)malloc(sizeof(int) * n);
    parent = (int*)malloc(sizeof(int) * n);
    left = (int*)malloc(sizeof(int) * n);
    right = (int*)malloc(sizeof(int) * n);

    //初始化哈夫曼树
    for (i = 0; i < n; i++) {
        huffmanTree[i].weight = weight[i];
        huffmanTree[i].parent = -1;
        huffmanTree[i].left = -1;
        huffmanTree[i].right = -1;
    }

    //输入每个节点的权值
    printf("请输入每个节点的权值：\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }

    //构造哈夫曼树
    for (i = 0; i < n - 1; i++) {
        min1 = min2 = 9999;
        k = 0;
        //找出权值最小的两个节点
        for (j = 0; j < n + i; j++) {
            if (huffmanTree[j].parent == -1) {
                if (huffmanTree[j].weight < min1) {
                    min2 = min1;
                    min1 = huffmanTree[j].weight;
                    k = j;
                } else if (huffmanTree[j].weight < min2) {
                    min2 = huffmanTree[j].weight;
                }
            }
        }
        //将找出的两个节点合并为一个节点
        huffmanTree[k].weight = min1 + min2;
        //将权值较小的节点作为左子节点
        huffmanTree[k].left = min1;
        //将权值较大的节点作为右子节点
        huffmanTree[k].right = min2;
        //将合并后的节点的父节点设置为-1
        huffmanTree[min1].parent = k;
        huffmanTree[min2].parent = k;
    }

    //释放动态分配的内存
    free(weight);
    free(parent);
    free(left);
    free(right);
}

int main() {
    int n;
    printf("请输入节点个数：\n");
    scanf("%d", &n);

    HuffmanTreeNode *huffmanTree;
    huffmanTree = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode) * (2 * n - 1));

    createHuffmanTree(huffmanTree, n);

    return 0;
}

以上代码仅提供了一个简单的哈夫曼树构造的示例，实际上，哈夫曼树还有很多变种，如带权路径长度(WPL)最小的哈夫曼树、基于贪心算法的哈夫曼树等等。具体实现方法可以根据需求进行调整。