572369写出哈夫曼树
时间: 2023-07-01 12:19:04 浏览: 28
首先根据权值从小到大排序,得到以下8个节点:
```
3 2 9 5 6 7 4 1
```
然后按照哈夫曼树的构建过程,依次合并权值最小的两个节点,直到只剩下一个根节点为止。过程如下:
1. 合并3和2,得到5节点,权值为5,左子节点为3,右子节点为2。
2. 合并5和9,得到14节点,权值为14,左子节点为5,右子节点为9。
3. 合并14和5,得到19节点,权值为19,左子节点为14,右子节点为6。
4. 合并7和4,得到11节点,权值为11,左子节点为7,右子节点为4。
5. 合并1和11,得到12节点,权值为12,左子节点为1,右子节点为11。
6. 合并19和12,得到31节点,权值为31,左子节点为19,右子节点为12。
7. 合并31和6,得到37节点,权值为37,左子节点为31,右子节点为6。
8. 37节点为根节点,哈夫曼树构建完成。
下面是哈夫曼树的结构:
```
37
/ \
/ \
31 6
/ \
19 12
/ \ /
5 9 7
/ \
3 2
```
相关问题
由哈夫曼树写出对应的哈夫曼树编码
哈夫曼编码是一种前缀编码,它利用哈夫曼树来构造编码,使得编码最短且唯一性得到保证。下面是由哈夫曼树写出对应的哈夫曼编码的步骤:
1. 对于哈夫曼树中的每个叶子节点,标记其对应的字符。
2. 从根节点开始遍历哈夫曼树,当遇到一个叶子节点时,记录下从根节点到该叶子节点的路径上的所有分支,将其转换为0或1,得到该叶子节点对应的哈夫曼编码。
3. 重复步骤2,直到遍历完整个哈夫曼树,得到所有字符的哈夫曼编码。
下面是一个示例,假设有4个字符a、b、c、d,它们的权值分别为2、3、4、5。首先根据这些权值构造哈夫曼树,如下图所示:
```
14
/ \
/ \
7 7
/ \ / \
3 4 2 5
/ \ / \
a b c d
```
从根节点开始遍历哈夫曼树,当遇到一个叶子节点时,记录下从根节点到该叶子节点的路径上的所有分支,将其转换为0或1,得到该叶子节点对应的哈夫曼编码。例如,字符a对应的哈夫曼编码为00,字符b对应的哈夫曼编码为01,字符c对应的哈夫曼编码为10,字符d对应的哈夫曼编码为11。
因此,由哈夫曼树写出对应的哈夫曼编码为:a-00,b-01,c-10,d-11。
用C语言写出哈夫曼树的代码和注释
以下是用C语言实现哈夫曼树的代码和注释:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 //定义最大节点数
typedef struct node {
int weight; //权值
int parent; //双亲节点下标
int left; //左孩子节点下标
int right; //右孩子节点下标
} Node, *HuffmanTree;
//初始化哈夫曼树
void InitHuffmanTree(HuffmanTree ht, int n) {
int i;
for (i = 0; i < 2 * n - 1; i++) {
ht[i].weight = ht[i].parent = ht[i].left = ht[i].right = 0;
}
}
//构建哈夫曼树
void CreateHuffmanTree(HuffmanTree ht, int n) {
int i, j, p1, p2, min1, min2;
for (i = 0; i < n; i++) { //初始化叶子节点
printf("请输入第%d个权值: ", i + 1);
scanf("%d", &ht[i].weight);
}
for (i = n; i < 2 * n - 1; i++) { //初始化非叶子节点
ht[i].weight = ht[i].parent = ht[i].left = ht[i].right = 0;
}
for (i = n; i < 2 * n - 1; i++) { //构建哈夫曼树
min1 = min2 = 32767; //初始化最小值为最大整数
p1 = p2 = 0;
for (j = 0; j < i; j++) { //找出权值最小的两个节点
if (ht[j].parent == 0) { //父节点为0表示未被选择过
if (ht[j].weight < min1) {
min2 = min1;
p2 = p1;
min1 = ht[j].weight;
p1 = j;
} else if (ht[j].weight < min2) {
min2 = ht[j].weight;
p2 = j;
}
}
}
ht[p1].parent = i; //将找出的两个节点合并为一个新节点
ht[p2].parent = i;
ht[i].left = p1;
ht[i].right = p2;
ht[i].weight = min1 + min2;
}
}
//输出哈夫曼编码
void PrintHuffmanCode(HuffmanTree ht, int n) {
int i, j, c, p;
char *code = (char*)malloc(n * sizeof(char)); //分配存储编码的空间
code[n - 1] = '\0'; //结束符
for (i = 0; i < n; i++) {
printf("第%d个节点的哈夫曼编码为: ", i + 1);
c = i;
p = ht[i].parent;
while (p != 0) { //从叶子节点开始向上遍历
if (ht[p].left == c) { //左子树为0
code[--n] = '0';
} else { //右子树为1
code[--n] = '1';
}
c = p;
p = ht[p].parent;
}
printf("%s\n", &code[n]); //输出编码
}
free(code); //释放空间
}
int main() {
int n;
printf("请输入节点数: ");
scanf("%d", &n);
HuffmanTree ht = (HuffmanTree)malloc((2 * n - 1) * sizeof(Node)); //分配存储节点的空间
InitHuffmanTree(ht, n); //初始化哈夫曼树
CreateHuffmanTree(ht, n); //构建哈夫曼树
PrintHuffmanCode(ht, n); //输出哈夫曼编码
free(ht); //释放空间
return 0;
}
```
注释已在代码中添加。以上是一个简单的哈夫曼树实现,仅供参考。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)