对于给定的w={2,3,4,7,8,9}权值,试构造一棵哈夫曼树,并给出各个节点的huffman编码及huffman数组的值,写出它的c语言代码
时间: 2023-06-16 22:07:25 浏览: 149
构造哈夫曼树的步骤如下:
1. 将w数组按权值从小到大排序
2. 取出权值最小的两个节点作为左右子节点构造一棵树,节点值为两个子节点权值之和,将这棵树的根节点重新加入到w数组中,并将w数组按权值从小到大排序
3. 重复步骤2,直至w数组中只剩下一棵树,即为哈夫曼树
对于给定的w={2,3,4,7,8,9},其构造的哈夫曼树如下:
```
33
/ \
14 19
/ \ / \
6 8 9 10
/ \ /
2 4 3
```
在哈夫曼树中,从根节点到每个叶子节点的路径上的左右方向可以表示为0和1,根据这个规律可以得到每个节点的哈夫曼编码:
| 节点 | 权值 | 哈夫曼编码 |
|-----|-----|---------|
| 33 | - | - |
| 14 | - | - |
| 19 | - | - |
| 6 | 2 | 110 |
| 8 | 4 | 111 |
| 9 | 3 | 100 |
| 10 | 7 | 1010 |
| 2 | 8 | 1011 |
| 4 | 9 | 00 |
| 3 | 4 | 01 |
其中,根节点、内部节点的权值为-,因为它们并不代表一个具体的字符。
根据哈夫曼编码的规则,对于每个字符,其对应的哈夫曼编码为从根节点到该字符所在叶子节点路径上的所有0和1,例如,字符2的哈夫曼编码为1011。
下面是该哈夫曼树的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 哈夫曼树的节点结构体
typedef struct HuffmanNode {
int weight; // 权值
char code[10]; // 编码
struct HuffmanNode *left; // 左子节点
struct HuffmanNode *right; // 右子节点
} HuffmanNode;
// 构造哈夫曼树
HuffmanNode *buildHuffmanTree(int *w, int n) {
// 创建n个节点
HuffmanNode **nodes = (HuffmanNode **) malloc(n * sizeof(HuffmanNode *));
for (int i = 0; i < n; i++) {
nodes[i] = (HuffmanNode *) malloc(sizeof(HuffmanNode));
nodes[i]->weight = w[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}
// 构造哈夫曼树
for (int i = 0; i < n - 1; i++) {
// 找到权值最小的两个节点
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int j = 2; j < n - i; j++) {
if (nodes[j]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = j;
} else if (nodes[j]->weight < nodes[min2]->weight) {
min2 = j;
}
}
// 构造新节点
HuffmanNode *newNode = (HuffmanNode *) malloc(sizeof(HuffmanNode));
newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
// 将新节点加入到节点数组中
nodes[min1] = newNode;
nodes[min2] = nodes[n - i - 1];
}
// 返回根节点
return nodes[0];
}
// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *root, char *code, int len) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
// 叶子节点,输出编码
printf("%d: %s\n", root->weight, code);
strcpy(root->code, code);
return;
}
// 左子节点编码为0,右子节点编码为1
code[len] = '0';
generateHuffmanCode(root->left, code, len + 1);
code[len] = '1';
generateHuffmanCode(root->right, code, len + 1);
}
int main() {
int w[] = {2, 3, 4, 7, 8, 9};
int n = sizeof(w) / sizeof(int);
// 构造哈夫曼树
HuffmanNode *root = buildHuffmanTree(w, n);
// 生成哈夫曼编码
char code[10] = "\0";
generateHuffmanCode(root, code, 0);
return 0;
}
```