c语言 给定n个叶子结点和权值,建立哈夫曼树并输出。
时间: 2024-01-22 15:17:55 浏览: 43
这里是用C语言实现的哈夫曼树建立和输出:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树结点结构体
typedef struct huffmanNode {
int weight;
int parent, left, right;
} HuffmanNode;
// 建立哈夫曼树函数
void createHuffmanTree(HuffmanNode *huffmanTree, int n) {
int i, j, min1, min2;
// 初始化哈夫曼树
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].weight = 0;
huffmanTree[i].parent = -1;
huffmanTree[i].left = -1;
huffmanTree[i].right = -1;
}
// 输入权值
for (i = 0; i < n; i++) {
printf("请输入第%d个叶子结点的权值:", i + 1);
scanf("%d", &huffmanTree[i].weight);
}
// 构建哈夫曼树
for (i = 0; i < n - 1; i++) {
min1 = min2 = 0;
// 找到当前权值最小的两个结点
for (j = 0; j < n + i; j++) {
if (huffmanTree[j].parent == -1) {
if (huffmanTree[j].weight < huffmanTree[min1].weight) {
min2 = min1;
min1 = j;
} else if (huffmanTree[j].weight < huffmanTree[min2].weight) {
min2 = j;
}
}
}
// 合并两个权值最小的结点
huffmanTree[min1].parent = n + i;
huffmanTree[min2].parent = n + i;
huffmanTree[n + i].weight = huffmanTree[min1].weight + huffmanTree[min2].weight;
huffmanTree[n + i].left = min1;
huffmanTree[n + i].right = min2;
}
}
// 输出哈夫曼树函数
void printHuffmanTree(HuffmanNode *huffmanTree, int n) {
int i;
printf("\n哈夫曼树如下:\n");
printf("结点\t权值\t父结点\t左孩子\t右孩子\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("%d\t%d\t%d\t%d\t%d\n", i + 1, huffmanTree[i].weight, huffmanTree[i].parent + 1,
huffmanTree[i].left + 1, huffmanTree[i].right + 1);
}
}
int main() {
int n;
printf("请输入叶子结点数n:");
scanf("%d", &n);
HuffmanNode *huffmanTree = (HuffmanNode *) malloc(sizeof(HuffmanNode) * (2 * n - 1));
createHuffmanTree(huffmanTree, n);
printHuffmanTree(huffmanTree, n);
free(huffmanTree);
return 0;
}
```
代码中,我们先定义了哈夫曼树结点结构体 `HuffmanNode`,包括结点权值、父结点、左孩子和右孩子四个成员变量。然后,我们实现了两个函数,分别是 `createHuffmanTree` 和 `printHuffmanTree`,用于建立哈夫曼树和输出哈夫曼树。
在 `createHuffmanTree` 函数中,我们首先初始化哈夫曼树的所有结点,然后输入每个叶子结点的权值。接着,我们使用循环不断地合并两个权值最小的结点,直到最后只剩下一个根结点,即为哈夫曼树的根节点。
在 `printHuffmanTree` 函数中,我们按照结点的编号、权值、父结点、左孩子和右孩子的顺序输出哈夫曼树的结点信息。
在主函数中,我们先输入叶子结点数 `n`,然后动态申请哈夫曼树空间,调用 `createHuffmanTree` 函数建立哈夫曼树,最后调用 `printHuffmanTree` 函数输出哈夫曼树。注意,程序结束前需要释放动态申请的哈夫曼树空间。