哈夫曼树,第一行输入一个数n,表示叶结点的个数。 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。C语言代码
时间: 2023-06-20 09:03:30 浏览: 83
以下是哈夫曼树的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
typedef struct node {
int weight;
int parent, lchild, rchild;
} Node;
Node nodes[MAX_N * 2]; // 哈夫曼树结点数组
void create_tree(int n) {
int i, j, p1, p2, min1, min2;
for (i = 0; i < 2 * n - 1; i++) {
if (i < n) {
scanf("%d", &nodes[i].weight);
} else {
nodes[i].weight = 0;
}
nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;
}
for (i = n; i < 2 * n - 1; i++) {
min1 = min2 = 0x7fffffff; // 初始化为最大值
p1 = p2 = -1;
for (j = 0; j < i; j++) {
if (nodes[j].parent == -1) {
if (nodes[j].weight < min1) {
min2 = min1;
min1 = nodes[j].weight;
p2 = p1;
p1 = j;
} else if (nodes[j].weight < min2) {
min2 = nodes[j].weight;
p2 = j;
}
}
}
nodes[p1].parent = i;
nodes[p2].parent = i;
nodes[i].lchild = p1;
nodes[i].rchild = p2;
nodes[i].weight = min1 + min2;
}
}
int calc_wpl(int n) {
int i, wpl = 0;
for (i = 0; i < n; i++) {
int j = i;
while (nodes[j].parent != -1) {
if (nodes[nodes[j].parent].lchild == j) {
wpl += nodes[nodes[j].parent].weight;
}
j = nodes[j].parent;
}
}
return wpl;
}
int main() {
int n;
scanf("%d", &n);
create_tree(n);
printf("%d\n", calc_wpl(n));
return 0;
}
```
输入格式为:第一行为叶结点的个数n,接下来一行为n个叶结点的权值。输出为哈夫曼树的带权路径长度(WPL)。