问题: 哈夫曼编码,英文名称 Huffman Coding,有时也翻译为霍夫曼编码,在1952年提出的,是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用,同时也广泛应用于数据压缩,其压缩率通常在20% 90%之间 赫夫曼码是可变字长编码(VLC)的一种。哈夫曼树是最优二叉树, 带权路径长度最小的二叉树。
原理:
假设有几个数字40,10,20,16,14。
首先将这五个数字按照从小到大的顺序排列:10, 14,16,20, 40。
构建哈夫曼树:
1.首先选取10,14
2.重新排序:16,20,24,40
3.重新排序24,36,40,60
4.按照二叉树左0右1,构建哈夫曼树
所以最终得到数字10的编码为100,数字14的编码为101,数字16的编码为110,数字20的编码为111,数字40的编码为0。
代码:
运行结果: