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

生成哈夫曼树的算法有很多种，其中最常用的就是贪心算法。以下是用C语言实现时间复杂度为O(n)的生成哈夫曼树的代码，并计算带权路径的长度： ```c #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函数中，采用从叶子节点到根节点的逆序遍历方式，计算出每个叶子节点的带权路径长度，最后累加起来即可得到整棵树的带权路径长度。