哈夫曼树的构造代码实现

哈夫曼树是一种经典的数据结构，常用于数据压缩和编码。下面是C语言中哈夫曼树的构造代码实现：

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

#define MAX_SIZE 100

typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HTNode, *HuffmanTree;

void Select(HuffmanTree HT, int n, int *s1, int *s2) {
    int i, min1, min2;
    min1 = min2 = MAX_SIZE;
    *s1 = *s2 = 0;
    for (i = 1; i <= n; i++) {
        if (HT[i].weight < min1 && HT[i].parent == 0) {
            min2 = min1;
            *s2 = *s1;
            min1 = HT[i].weight;
            *s1 = i;
        } else if (HT[i].weight < min2 && HT[i].parent == 0) {
            min2 = HT[i].weight;
            *s2 = i;
        }
    }
}

void CreateHuffmanTree(HuffmanTree *HT, int n) {
    if (n <= 1) {
        return;
    }
    int m = 2 * n - 1;
    *HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));
    HuffmanTree p;
    int i;
    for (p = *HT + 1, i = 1; i <= n; ++i, ++p) {
        scanf("%d", &p->weight);
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for (; i <= m; ++i, ++p) {
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    int s1, s2;
    for (i = n + 1; i <= m; ++i) {
        Select(*HT, i - 1, &s1, &s2);
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
        (*HT)[i].lchild = s1;
        (*HT)[i].rchild = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}

int main() {
    HuffmanTree HT;
    int n;
    printf("请输入叶子节点的个数：");
    scanf("%d", &n);
    printf("请输入每个叶子节点的权值：");
    CreateHuffmanTree(&HT, n);
    printf("哈夫曼树构造成功！\n");
    return 0;
}

以上代码实现了哈夫曼树的构造，其中`Select`函数用于在哈夫曼树中选择权值最小的两个节点，`CreateHuffmanTree`函数用于构造哈夫曼树。在主函数中，用户需要输入叶子节点的个数和每个叶子节点的权值，程序会自动构造哈夫曼树并输出构造成功的信息。