用C++实现一个哈夫曼树
时间: 2024-05-02 20:16:12 浏览: 14
哈夫曼树是一种特殊的二叉树,用于数据压缩中,它可以按照某种规则压缩数据,使得压缩后的数据长度更短。下面是用C语言实现哈夫曼树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
// 定义哈夫曼树的节点结构体
typedef struct HuffmanNode {
int weight; // 权值
int parent; // 父节点
int left; // 左子节点
int right; // 右子节点
} HuffmanNode, *HuffmanTree;
// 选择两个权值最小的节点
void Select(HuffmanTree HT, int n, int *s1, int *s2) {
int i, min1 = MAXSIZE, min2 = MAXSIZE;
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < min1) {
*s2 = *s1;
*s1 = i;
min2 = min1;
min1 = HT[i].weight;
} else if (HT[i].weight < min2) {
*s2 = i;
min2 = HT[i].weight;
}
}
}
}
// 建立哈夫曼树
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n) {
int m = 2 * n - 1;
*HT = (HuffmanTree) malloc((m + 1) * sizeof(HuffmanNode));
int i;
for (i = 1; i <= n; i++) {
(*HT)[i].weight = w[i];
(*HT)[i].parent = 0;
(*HT)[i].left = 0;
(*HT)[i].right = 0;
}
for (i = n + 1; i <= m; i++) {
(*HT)[i].weight = 0;
(*HT)[i].parent = 0;
(*HT)[i].left = 0;
(*HT)[i].right = 0;
}
int s1, s2;
for (i = n + 1; i <= m; i++) {
Select(*HT, i - 1, &s1, &s2);
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
(*HT)[i].left = s1;
(*HT)[i].right = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
}
// 哈夫曼编码
void HuffmanEncoding(HuffmanTree HT, char **HC, int n) {
*HC = (char *) malloc((n + 1) * sizeof(char));
(*HC)[n] = '\0';
int i;
for (i = 1; i <= n; i++) {
int start = n - 1;
int c = i;
int f = HT[i].parent;
while (f != 0) {
if (HT[f].left == c) {
(*HC)[--start] = '0';
} else {
(*HC)[--start] = '1';
}
c = f;
f = HT[f].parent;
}
HC[i - 1] = (char *) malloc((n - start) * sizeof(char));
strcpy(HC[i - 1], &(*HC)[start]);
}
}
int main() {
int n, i;
printf("请输入节点个数:");
scanf("%d", &n);
int *w = (int *) malloc(n * sizeof(int));
printf("请输入每个节点的权值:");
for (i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
HuffmanTree HT;
CreateHuffmanTree(&HT, w, n);
char **HC;
HuffmanEncoding(HT, HC, n);
printf("哈夫曼编码如下:\n");
for (i = 0; i < n; i++) {
printf("%d:%s\n", w[i], HC[i]);
}
return 0;
}
```
运行该程序,输入节点个数和每个节点的权值,即可得到哈夫曼编码。