先看看赫夫曼树
假设有n个权值{w1,w2,…,wn},构造一个有n个叶子结点的二叉树,每个叶子结点权值为wi,则其中带权路径长度WPL最小的二叉树称作赫夫曼树或最优二叉树。
赫夫曼树的构造,赫夫曼最早给出了带有一般规律的算法,俗称赫夫曼算法。如下:
(1)根据给定的n个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空。
(2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
(3)在F中删除这两棵树,同时将新得到的二叉树加入到F中。
(4)重复(2)和(3)直到F中只含一棵树为止,这棵树就是赫夫曼树。
例如下图便是赫夫曼树的构造过程。其中,根节点上标注的是所赋的权值。
设计一棵赫夫曼树,由此得到的二进制前缀编码就是赫夫曼编码。那么什么是前缀编码呢?所谓前缀编码,就是若要设计长短不等的编码,则必须是任意一个字符的编码都不是另一个字符编码的前缀。所以我们可以利用二叉树来设计二进制的前缀编码。
假设需要传送的字符为:A B A C C D A。如下图就是一个前缀编码的示例。
说了这么多理论,总该实践一下了,下面是赫夫曼编码的具体实现代码:
分享到:
相关推荐
赫夫曼编码(Huffman)的matlab实现,自己编写,有详细注释,可以学习交流。
构造一颗有n个叶子节点的二叉树,每个叶子节点带权为wi, 其中带权路径长度WPL最小的二叉树称作最优二叉树或者赫夫曼树。
数据结构课程设计需要,对赫夫曼编码的应用,加密解密。
赫夫曼编码是一种将信息转换成二进制编码有效的方法之一,赫夫曼编码是利用赫夫曼树求得的用于通信的二进制编码。而这次我们的课程设计对编码译码的要求不是太高,只是将大写字母或小写字母转化成二进制编码,或将二...
赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码
huffman编码,根据输入进行权重计算并编码,还实现了解码。
数据结构实验实验报告Huffman赫夫曼编码及应用.pdf数据结构实验实验报告Huffman赫夫曼编码及应用.pdf数据结构实验实验报告Huffman赫夫曼编码及应用.pdf数据结构实验实验报告Huffman赫夫曼编码及应用.pdf数据结构实验...
利用赫夫曼树的编码思想,构造一个完整的赫夫曼编码系统。源代码还附赠了详细的PPT讲解。 ①从键盘读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,然后对赫夫曼树进行编码,输出结果。 ②使用上述字符集创建...
Huffman编码(二叉树的应用)其中包含了源代码及实验截图
读取一篇英文文章,并对其中的小写字母进行频数统计,并构造赫夫曼树和赫夫曼编码,输出每个 字母的编码
数据结构课程设计-huffman编码,用C语言编写,适用于清华大学等数据结构教程 huffman 赫夫曼编码 数据结构 课程设计 C语言
小弟写的赫夫曼树的构建及赫夫曼编码算法,可以实现根据字母频率对字母进行编码; 每一个字母的Huffman编码进文章进行编码;根据文章的Huffman序列,进行解码。
数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码
利用c语言来实现赫夫曼树的编码,解码。适合初学者参照学习
赫夫曼编码 压缩算法 数据结构课程设计 源代码 压缩文本文件,,,
赫夫曼树构建 赫夫曼编码 数据结构 C语言 动画 用C语言动画演示赫夫曼树的构建以及赫夫曼编码的实现
在VS2013下运行 包里面有相应的说明
C语言实现赫夫曼树的构建及赫夫曼编码的源代码,配合我的CSDN博客:http://blog.csdn.net/ns_code/article/details/19174553中的讲解,帮助你掌握Huffman编码的算法实现
问题描述:对任意输入的一段英文,为每个字符编制其相应的赫夫曼编码;并利用该编码为任意输入的0、1序列进行解码. 基本要求:一个完整的系统应具有以下功能: (1)初始化 从终端读入一段英文字符,统计每个字符...
根据严蔚敏数据结构书上的伪码实现的赫夫曼编码译码程序。对26个英文字母加上逗号,句号,空格以及回车进行赫夫曼编码。然后对给定的txt文件(英文文章)进行赫夫曼编码和译码。