最优二叉树之哈弗曼树
哈弗曼树是一类带全路径最短的树,所以又称为最优二叉树。构造这种树的算法最早是由哈弗曼提出,这种树在现在有着广泛的应用。例如文件压缩啦,信息检索啦...
下面先谈谈哈弗曼树的构建,举个例子来说吧。根据一段字符串构建一棵哈夫曼树,出现的每个字符都代表着树叶的值,字符出现的次数代表其权值,下面是具体的步骤:
1.根据字符和出现的次数(权值)创建节点,并把节点都存放到一个队列中。
2.每次从队列中取出2个权值最小的节点作为左,右子数构建一个新的节点,新的节点的权值为他们两个权值的和。
3.将新的节点加入到刚才的队列中,删除原来两个权值最小的节点。
4.重复2,3的步骤直到队列中只有一个节点为止,把这个节点作为树根,这棵哈夫曼树就构建成功了。
接下来说说关于哈弗曼码表的获取,其实很简单啦,从树根开始往下走直到最底下的叶,
路过左树枝的就加0,路过右树枝的就加1,就这样每个叶(字符)对应的码表就获取到了。
然后聊聊哈弗曼压缩到底是怎么实现的呢?哈夫曼编码是01串组合,这样我们就可以通过编码先把文件转换成相应的01串再存进去,8个01串才占一个字节而一个汉字占4个字节,一个字符占2个字节,因此可以节约很多空间,实现压缩。
分享到:
相关推荐
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入...
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if...
1)哈夫曼树类型、select()函数(求两最小权值结点)、哈夫曼树构建、求编码函数、字符串输入处理函数等的声明放在huffman.h文件; 2)select()函数、哈夫曼树构建、求编码函数的实现可放在huffman.c文件; 3)输入...
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
c++ 源代码 哈夫曼树 哈夫曼编码 部分代码如下: #include"Huffman.h" #include"hfmTree.h" #include using namespace std; int main() { cout~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~...
哈夫曼树构造 输出
如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
利用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并将它存于文件hfmTree中; 2) 编码(EnCoding)。利用已建好的哈夫曼树(若不在内存中,则从文件hfmTree中读入),对以下报文进行编码,结果存入文件...
这是我做的一个基于哈夫曼树思想的压缩算法程序源码,希望大家指正
将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。 3. 测试数据 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:...
C语言实现的哈夫曼树
(1) 读入一个 ASCII 文件,统计文档中字符出现的频度,构造哈夫曼树; (2) 在构造好的哈夫曼树中对每个字符进行 Huffman 编码; (3) 要求打印出原始数据、每个字符对应的Huffman 编码和总编码长度。
首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码,另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
一、课程设计题目:哈夫曼树应用 二、课程设计要求: 1) 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2) 利用...
实现哈夫曼算法的前提是要考虑用什么样的存储结构来存储一棵哈夫曼树。在哈夫曼树中,没有度为1的结点,结点总数是n0+n2(其中n0表示二叉树中度为0的结点数,n2表示度为2的结点数),而由二叉树的性质知道n0=n2+1,...
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
利用已建好的哈夫曼树(如不在内存,则从文件 hfmtree 中读入),对文件 tobetrans 中的正文进行编码,然后将结果存入文件 codefile 中。 (3)D:解码(Decoding)。利用已建好的哈夫曼树将文件 codefile 中的代码进行...
编码:利用建立好的哈夫曼树对源文件进行编码,实现文件压缩,然后将结果以文件形式保存,如编码文件codefile。 d.译码:利用建立好的哈夫曼树对codefile中的代码进行译码。结果存入译码文件decofile中。 e.输出:...
数据结构课程设计:哈夫曼树及其应用 文档 ++代码 构建哈夫曼树,编码,译码