生成哈夫曼树,输出wpl,输出各节点权值,输出层数的c语言代码
时间: 2024-05-03 09:22:06 浏览: 11
以下是生成哈夫曼树的C语言代码,其中包括输出wpl、各节点权值和层数的功能:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 1000
typedef struct Node {
int data;
int weight;
int left_child;
int right_child;
} Node;
int get_min_index(Node nodes[], int n) {
int min_index = -1;
int min_weight = __INT_MAX__;
for (int i = 0; i < n; i++) {
if (nodes[i].weight < min_weight && nodes[i].data == -1) {
min_index = i;
min_weight = nodes[i].weight;
}
}
return min_index;
}
void huffman_tree(Node nodes[], int n) {
for (int i = n; i < 2 * n - 1; i++) {
int min1 = get_min_index(nodes, i);
nodes[min1].data = i;
int min2 = get_min_index(nodes, i);
nodes[min2].data = i;
nodes[i].left_child = min1;
nodes[i].right_child = min2;
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
}
}
void print_tree(Node nodes[], int n) {
printf("权值信息:\n");
for (int i = 0; i < n; i++) {
printf("%d: %d\n", i, nodes[i].weight);
}
printf("哈夫曼树层次信息:\n");
int queue[MAX_NODES];
int head = 0, tail = 0;
queue[tail++] = 2 * n - 2;
int current_level = 0;
while (head < tail) {
int queue_size = tail - head;
printf("第%d层:", current_level++);
for (int i = 0; i < queue_size; i++) {
int index = queue[head++];
printf("%d ", index);
if (nodes[index].left_child != -1) {
queue[tail++] = nodes[index].left_child;
}
if (nodes[index].right_child != -1) {
queue[tail++] = nodes[index].right_child;
}
}
printf("\n");
}
printf("WPL:%d\n", nodes[2 * n - 2].weight);
}
int main() {
int n;
printf("请输入节点数:");
scanf("%d", &n);
Node nodes[MAX_NODES];
for (int i = 0; i < n; i++) {
printf("请输入第%d个节点的权值:", i);
scanf("%d", &nodes[i].weight);
nodes[i].data = -1;
nodes[i].left_child = -1;
nodes[i].right_child = -1;
}
huffman_tree(nodes, n);
print_tree(nodes, n);
return 0;
}
```
注意:本段代码中省略了输入节点权值的部分。