用C语言实现时间复杂度为O（n)的生成哈夫曼树，并计算带权路径的长度

生成哈夫曼树的算法有很多种，其中最常用的就是贪心算法。以下是用C语言实现时间复杂度为O(n)的生成哈夫曼树的代码，并计算带权路径的长度：

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

#define MAX_SIZE 100

typedef struct {
    int weight;     // 权值
    int parent;     // 父节点
    int leftChild;  // 左孩子
    int rightChild; // 右孩子
} HTNode, *HuffmanTree;

typedef char * *HuffmanCode;

// 构建哈夫曼树
void CreateHuffmanTree(HuffmanTree *HT, int n) {
    if (n <= 1) {
        return;
    }
    int m = 2 * n - 1;
    *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 0号单元不用
    // 初始化
    for (int i = 1; i <= m; i++) {
        (*HT)[i].parent = 0;
        (*HT)[i].leftChild = 0;
        (*HT)[i].rightChild = 0;
    }
    // 输入权值
    printf("请输入%d个权值：\n", n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &((*HT)[i].weight));
    }
    // 构建哈夫曼树
    for (int i = n + 1; i <= m; i++) {
        // 找出权值最小的两个节点
        int min1 = 0, min2 = 0;
        for (int j = 1; j < i; j++) {
            if ((*HT)[j].parent == 0) {
                if (min1 == 0 || (*HT)[j].weight < (*HT)[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == 0 || (*HT)[j].weight < (*HT)[min2].weight) {
                    min2 = j;
                }
            }
        }
        // 合并节点
        (*HT)[min1].parent = i;
        (*HT)[min2].parent = i;
        (*HT)[i].leftChild = min1;
        (*HT)[i].rightChild = min2;
        (*HT)[i].weight = (*HT)[min1].weight + (*HT)[min2].weight;
    }
}

// 构建哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode *HC, int n) {
    *HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));
    char *cd = (char *)malloc(n * sizeof(char)); // 临时存放编码
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; i++) {
        int start = n - 1;
        for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
            if (HT[f].leftChild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
        }
        (*HC)[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}

// 计算带权路径长度
int WeightedPathLength(HuffmanTree HT, int n) {
    int wpl = 0;
    for (int i = 1; i <= n; i++) {
        int c = i;
        int f = HT[i].parent;
        while (f != 0) {
            if (HT[f].leftChild == c) {
                wpl += HT[f].weight;
            }
            c = f;
            f = HT[f].parent;
        }
    }
    return wpl;
}

int main() {
    HuffmanTree HT;
    HuffmanCode HC;
    int n;
    printf("请输入叶子节点个数：\n");
    scanf("%d", &n);
    CreateHuffmanTree(&HT, n);
    CreateHuffmanCode(HT, &HC, n);
    printf("哈夫曼编码如下：\n");
    for (int i = 1; i <= n; i++) {
        printf("%d: %s\n", i, HC[i]);
    }
    int wpl = WeightedPathLength(HT, n);
    printf("带权路径长度为：%d\n", wpl);
    free(HT);
    free(HC);
    return 0;
}

上述代码中，CreateHuffmanTree函数用于构建哈夫曼树，CreateHuffmanCode函数用于构建哈夫曼编码，WeightedPathLength函数用于计算带权路径长度。在主函数中，先输入叶子节点个数，然后调用上述三个函数完成哈夫曼树的生成、编码的构建和带权路径长度的计算。

其中，CreateHuffmanTree函数中，先输入叶子节点的权值，然后采用贪心算法逐步合并节点，直到最后得到哈夫曼树。

CreateHuffmanCode函数中，先申请足够的内存空间，然后采用递归的方式，从叶子节点到根节点，逆序求得每个叶子节点的哈夫曼编码。

WeightedPathLength函数中，采用从叶子节点到根节点的逆序遍历方式，计算出每个叶子节点的带权路径长度，最后累加起来即可得到整棵树的带权路径长度。