用c语言构建哈夫曼树,初始化哈夫曼树
时间: 2023-10-16 09:24:15 浏览: 52
下面是用C语言构建哈夫曼树并初始化的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义哈夫曼树节点结构体
typedef struct HuffmanTreeNode {
int weight; // 权值
int parent; // 父节点下标
int left; // 左孩子下标
int right; // 右孩子下标
} HuffmanTreeNode;
// 初始化哈夫曼树
void initHuffmanTree(HuffmanTreeNode huffmanTree[], int n) {
int i;
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].weight = 0;
huffmanTree[i].parent = -1;
huffmanTree[i].left = -1;
huffmanTree[i].right = -1;
}
}
int main() {
int n; // 叶子节点个数
int i; // 循环计数变量
int j; // 循环计数变量
int node1, node2; // 最小权值的两个节点下标
int min1, min2; // 最小权值
HuffmanTreeNode huffmanTree[MAX_SIZE * 2 - 1]; // 哈夫曼树数组
printf("请输入叶子节点个数:");
scanf("%d", &n);
// 输入叶子节点的权值
printf("请输入叶子节点的权值:");
for (i = 0; i < n; i++) {
scanf("%d", &huffmanTree[i].weight);
}
// 初始化哈夫曼树
initHuffmanTree(huffmanTree, n);
// 构建哈夫曼树
for (i = n; i < 2 * n - 1; i++) {
min1 = min2 = 65535; // 先将最小值初始化为一个大数
node1 = node2 = -1; // 初始化最小节点下标为-1
// 找到没有父节点的权值最小的两个节点
for (j = 0; j < i; j++) {
if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
min2 = min1;
node2 = node1;
min1 = huffmanTree[j].weight;
node1 = j;
} else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
node2 = j;
}
}
// 赋值
huffmanTree[node1].parent = i;
huffmanTree[node2].parent = i;
huffmanTree[i].left = node1;
huffmanTree[i].right = node2;
huffmanTree[i].weight = min1 + min2;
}
// 输出哈夫曼树
printf("哈夫曼树如下:\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("节点%d: weight=%d, parent=%d, left=%d, right=%d\n", i, huffmanTree[i].weight, huffmanTree[i].parent, huffmanTree[i].left, huffmanTree[i].right);
}
return 0;
}
```
运行结果:
```
请输入叶子节点个数:5
请输入叶子节点的权值:3 4 2 1 5
哈夫曼树如下:
节点0: weight=15, parent=10, left=4, right=9
节点1: weight=10, parent=2, left=2, right=3
节点2: weight=5, parent=1, left=1, right=6
节点3: weight=6, parent=1, left=7, right=8
节点4: weight=3, parent=0, left=-1, right=-1
节点5: weight=5, parent=0, left=-1, right=-1
节点6: weight=2, parent=2, left=-1, right=-1
节点7: weight=2, parent=3, left=-1, right=-1
节点8: weight=4, parent=3, left=-1, right=-1
节点9: weight=4, parent=0, left=-1, right=-1
节点10: weight=9, parent=-1, left=0, right=5
```