哈夫曼树的构造c语言
时间: 2023-07-01 12:19:52 浏览: 96
以下是一个简单的C语言实现哈夫曼树的构造过程:
```c
#include <stdio.h>
#include <stdlib.h>
//定义哈夫曼树结构体
typedef struct HuffmanTreeNode {
int weight; //权值
int parent; //父节点下标
int left; //左子节点下标
int right; //右子节点下标
} HuffmanTreeNode;
//构造哈夫曼树
void createHuffmanTree(HuffmanTreeNode *huffmanTree, int n) {
int i, j, k, min1, min2;
int *weight; //存储每个节点的权值
int *parent; //存储每个节点的父节点
int *left; //存储每个节点的左子节点
int *right; //存储每个节点的右子节点
//动态分配内存
weight = (int*)malloc(sizeof(int) * n);
parent = (int*)malloc(sizeof(int) * n);
left = (int*)malloc(sizeof(int) * n);
right = (int*)malloc(sizeof(int) * n);
//初始化哈夫曼树
for (i = 0; i < n; i++) {
huffmanTree[i].weight = weight[i];
huffmanTree[i].parent = -1;
huffmanTree[i].left = -1;
huffmanTree[i].right = -1;
}
//输入每个节点的权值
printf("请输入每个节点的权值:\n");
for (i = 0; i < n; i++) {
scanf("%d", &weight[i]);
}
//构造哈夫曼树
for (i = 0; i < n - 1; i++) {
min1 = min2 = 9999;
k = 0;
//找出权值最小的两个节点
for (j = 0; j < n + i; j++) {
if (huffmanTree[j].parent == -1) {
if (huffmanTree[j].weight < min1) {
min2 = min1;
min1 = huffmanTree[j].weight;
k = j;
} else if (huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
}
}
}
//将找出的两个节点合并为一个节点
huffmanTree[k].weight = min1 + min2;
//将权值较小的节点作为左子节点
huffmanTree[k].left = min1;
//将权值较大的节点作为右子节点
huffmanTree[k].right = min2;
//将合并后的节点的父节点设置为-1
huffmanTree[min1].parent = k;
huffmanTree[min2].parent = k;
}
//释放动态分配的内存
free(weight);
free(parent);
free(left);
free(right);
}
int main() {
int n;
printf("请输入节点个数:\n");
scanf("%d", &n);
HuffmanTreeNode *huffmanTree;
huffmanTree = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode) * (2 * n - 1));
createHuffmanTree(huffmanTree, n);
return 0;
}
```
以上代码仅提供了一个简单的哈夫曼树构造的示例,实际上,哈夫曼树还有很多变种,如带权路径长度(WPL)最小的哈夫曼树、基于贪心算法的哈夫曼树等等。具体实现方法可以根据需求进行调整。
阅读全文