一组权值 8,2,5,3,2,17,4 求由此生成的哈夫曼树

如题所述

举报该问题

其他回答

第1个回答 2022-09-26

哈弗曼树就是每回将2个最小的并1个。

过程大约如下：

8,2,5,3,2,17,4

2+2=4

3,4,4,5,8,17

3+4=7

4,5,7,8,17

4+5=9

7,8,9,17

7+8=15

9,15,17

9+15=24

17,24

17+24=41

这个树大概是这样的，分号是某个点的两个子节点写完了的意思，意会下：

24 17

15 9;

7 8; 4 5;

3 4; 2 2;

哈弗曼树的形态是不一定唯一的

因此这个也是可以的

24 17

15 9;

7 8; 4 5;

3 4;

2 2；

她们的带权路径长度分别是

3*4+4*4+8*3+2*4+2*4+5*3+17*1=100

3*4+2*5+2*5+8*3+4*3+5*3+17*1=100

都是带全路径长度最短的生成树

扩展资料：

简介

在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（比如文件中的1个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

哈夫曼编码的起源：

哈夫曼编码是 1952 年由 David A. Huffman 提出的一种无损数据压缩的编码算法。哈夫曼编码先统计出每种字母在字符串里出现的频率，根据频率建立一棵路径带权的二叉树，也就是哈夫曼树，树上每个结点存储字母出现的频率，根结点到结点的路径即是字母的编码，频率高的字母使用较短的编码，频率低的字母使用较长的编码，使得编码后的字符串占用空间最小。

参考资料来源：百度百科-哈夫曼树