用c语言构建哈夫曼树

好的，下面是一个用C语言实现的哈夫曼树的示例代码：

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

#define MAX_SIZE 100

// 哈夫曼树节点结构体
typedef struct {
    int weight;    // 权值
    int parent;    // 父节点下标
    int left;      // 左孩子下标
    int right;     // 右孩子下标
} HuffmanNode, *HuffmanTree;

// 选择权值最小的两个节点
void select(HuffmanTree tree, int n, int *s1, int *s2) {
    int i;
    int min1, min2;

    min1 = min2 = MAX_SIZE;
    for (i = 1; i <= n; i++) {
        if (tree[i].parent == 0) {
            if (tree[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = tree[i].weight;
                *s1 = i;
            }
            else if (tree[i].weight < min2) {
                min2 = tree[i].weight;
                *s2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *tree, int *w, int n) {
    int i, s1, s2;

    // 初始化哈夫曼树
    *tree = (HuffmanTree)malloc((2 * n - 1) * sizeof(HuffmanNode));
    for (i = 1; i <= n; i++) {
        (*tree)[i].weight = w[i];
        (*tree)[i].parent = 0;
        (*tree)[i].left = 0;
        (*tree)[i].right = 0;
    }
    for (i = n + 1; i < 2 * n - 1; i++) {
        (*tree)[i].weight = 0;
        (*tree)[i].parent = 0;
        (*tree)[i].left = 0;
        (*tree)[i].right = 0;
    }

    // 构建哈夫曼树
    for (i = n + 1; i < 2 * n - 1; i++) {
        select(*tree, i - 1, &s1, &s2);
        (*tree)[s1].parent = i;
        (*tree)[s2].parent = i;
        (*tree)[i].left = s1;
        (*tree)[i].right = s2;
        (*tree)[i].weight = (*tree)[s1].weight + (*tree)[s2].weight;
    }
}

int main() {
    int w[MAX_SIZE] = {0, 5, 6, 8, 7, 15};
    HuffmanTree tree;
    int n = 5;
    int i;

    createHuffmanTree(&tree, w, n);

    // 输出哈夫曼树
    printf("Huffman Tree:\n");
    for (i = 1; i < 2 * n - 1; i++) {
        printf("%d %d %d %d\n", i, tree[i].weight, tree[i].parent, tree[i].left, tree[i].right);
    }

    return 0;
}

在这个示例代码中，我们先定义了一个表示哈夫曼树节点的结构体`HuffmanNode`，然后定义了哈夫曼树的类型别名`HuffmanTree`。接着，我们实现了`select()`函数和`createHuffmanTree()`函数，用来选择权值最小的两个节点和构建哈夫曼树。最后，在`main()`函数中，我们初始化了一个权值数组`w`，并调用`createHuffmanTree()`函数构造哈夫曼树，并输出了哈夫曼树的各个节点的信息。

需要注意的是，这里的示例代码只是用于演示如何用C语言实现哈夫曼树的构建，并不够完整和健壮，实际使用时需要根据具体需求进行优化和改进。