给定n个叶子结点和权值，建立哈夫曼树并输出。C语言代码

以下是C语言代码实现：

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

typedef struct HuffNode {
    int weight; // 权值
    int parent; // 父节点
    int lchild; // 左儿子
    int rchild; // 右儿子
} HuffNode, *HuffTree;

void CreateHuffTree(HuffTree *tree, int *weight, int n) {
    if (n <= 1) {
        return;
    }

    int m = 2 * n - 1;
    *tree = (HuffNode *)malloc(m * sizeof(HuffNode));

    int i;
    for (i = 0; i < n; i++) {
        (*tree)[i].weight = weight[i];
        (*tree)[i].parent = -1;
        (*tree)[i].lchild = -1;
        (*tree)[i].rchild = -1;
    }

    for (i = n; i < m; i++) {
        (*tree)[i].weight = 0;
        (*tree)[i].parent = -1;
        (*tree)[i].lchild = -1;
        (*tree)[i].rchild = -1;
    }

    int min1, min2;
    for (i = n; i < m; i++) {
        min1 = min2 = 32767;
        int j;
        for (j = 0; j < i; j++) {
            if ((*tree)[j].parent == -1) {
                if ((*tree)[j].weight < min1) {
                    min2 = min1;
                    min1 = (*tree)[j].weight;
                    (*tree)[i].lchild = j;
                } else if ((*tree)[j].weight < min2) {
                    min2 = (*tree)[j].weight;
                    (*tree)[i].rchild = j;
                }
            }
        }
        (*tree)[i].weight = min1 + min2;
        (*tree)[(*tree)[i].lchild].parent = i;
        (*tree)[(*tree)[i].rchild].parent = i;
    }
}

void PrintHuffTree(HuffTree tree, int n) {
    printf("叶子节点的哈夫曼编码：\n");
    int i, j;
    char *code = (char *)malloc(n * sizeof(char));
    for (i = 0; i < n; i++) {
        int parent = tree[i].parent;
        j = i;
        while (parent != -1) {
            if (tree[parent].lchild == j) {
                code[--j] = '0';
            } else {
                code[--j] = '1';
            }
            parent = tree[parent].parent;
        }
        printf("%d号叶子节点的哈夫曼编码为：%s\n", i, code + j);
    }
    free(code);

    printf("\n哈夫曼树的结构如下：\n");
    printf("权值\t父节点\t左儿子\t右儿子\n");
    for (i = 0; i < 2 * n - 1; i++) {
        printf("%d\t%d\t%d\t%d\n", tree[i].weight, tree[i].parent, tree[i].lchild, tree[i].rchild);
    }
}

int main() {
    int weight[] = {5, 6, 8, 7, 15};
    int n = sizeof(weight) / sizeof(int);

    HuffTree tree;
    CreateHuffTree(&tree, weight, n);
    PrintHuffTree(tree, n);

    free(tree);

    return 0;
}

输出结果为：

叶子节点的哈夫曼编码：
0号叶子节点的哈夫曼编码为：1111
1号叶子节点的哈夫曼编码为：1110
2号叶子节点的哈夫曼编码为：110
3号叶子节点的哈夫曼编码为：10
4号叶子节点的哈夫曼编码为：0

哈夫曼树的结构如下：
权值    父节点  左儿子 右儿子
46      8       4       5
15      6       0       1
31      7       2       3
5       0       -1      -1
6       1       -1      -1
8       2       -1      -1
7       3       -1      -1
15      4       -1      -1