- 浏览: 80237 次
- 性别:
- 来自: 成都
文章分类
最新评论
1.树的路径长度
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。
2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。
结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度(Weighted Path Length of Tree):定义为树中所有叶结点的带权路径长度之和,通常记为:
其中:
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
树的带权路径长度亦称为树的代价。
3.最优二叉树或哈夫曼树
在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
【例】给定4个叶子结点a,b,c和d,分别带权7,5,2和4。构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为:
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)树的WPL最小,可以验证,它就是哈夫曼树。
注意:
① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。
② 最优二叉树中,权越大的叶子离根越近。
③ 最优二叉树的形态不唯一,WPL最小。
4.哈夫曼算法
哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法,故称其为哈夫曼算法。其基本思想是:
(1)根据给定的n个权值wl,w2,…,wn构成n棵二叉树的森林F={T1,T2,…,Tn},其中每棵二叉树Ti中都只有一个权值为wi的根结点,其左右子树均空。
(2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时,可以从中任选两棵),将这两棵树合并成一棵新树,为了保证新树仍是二叉树,需要增加一个新结点作为新树的根,并将所选的两棵树的根分别作为新根的左右孩子(谁左,谁右无关紧要),将这两个孩子的权值之和作为新树根的权值。
(3)对新的森林F重复(2),直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。
注意:
① 初始森林中的n棵二叉树,每棵树有一个孤立的结点,它们既是根,又是叶子
② n个叶子的哈夫曼树要经过n-1次合并,产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。
③ 哈夫曼树是严格的二叉树,没有度数为1的分支结点。
5.哈夫曼树的存储结构及哈夫曼算法的实现
(1) 哈夫曼树的存储结构
用一个大小为2n-1的向量来存储哈夫曼树中的结点,其存储结构为:
#define n 100 //叶子数目 #define m 2*n-1//树中结点总数 typedef struct { //结点类型 float weight; //权值,不妨设权值均大于零 int lchild,rchild,parent; //左右孩子及双亲指针 }HTNode; typedef HTNode HuffmanTree[m]; //HuffmanTree是向量类型
注意:
因为C语言数组的下界为0,故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时,它们分别是该结点的左、右孩子和双亲结点在向量中的下标。
这里设置parent域有两个作用:其一是使查找某结点的双亲变得简单;其二是可通过判定parent的值是否为-1来区分根与非根结点。
(2)哈夫曼算法的简要描述
在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree):
(1)初始化
将T[0..m-1]中2n-1个结点里的三个指针均置为空(即置为-1),权值置为0。
(2)输人
读人n个叶子的权值存于向量的前n个分量(即T[0..n-1])中。它们是初始森林中n个孤立的根结点上的权值。
(3)合并
对森林中的树共进行n-1次合并,所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步:
①在当前森林T[0..i-1]的所有结点中,选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象,这里0≤p1,p2≤i-1。
② 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树,新树的根是新结点T[i]。具体操作:
将T[p1]和T[p2]的parent置为i,
将T[i]的lchild和rchild分别置为p1和p2
新结点T[i]的权值置为T[p1]和T[p2]的权值之和。
注意:
合并后T[pl]和T[p2]在当前森林中已不再是根,因为它们的双亲指针均已指向了T[i],所以下一次合并时不会被选中为合并对象。
(3)哈夫曼算法的求精
void CreateHuffmanTree(HuffmanTree T) {//构造哈夫曼树,T[m-1]为其根结点 int i,p1,p2; InitHuffmanTree(T); //将T初始化 InputWeight(T); //输入叶子权值至T[0..n-1]的weight域 for(i=n;i<m;i++){//共进行n-1次合并,新结点依次存于T[i]中 SelectMin(T,i-1,&p1,&p2); //在T[0..i-1]中选择两个权最小的根结点,其序号分别为p1和p2 T[p1].parent=T[p2].parent=i; TIi].1child=p1; //最小权的根结点是新结点的左孩子 T[j].rchild=p2; //次小权的根结点是新结点的右孩子 T[i].weight=T[p1].weight+T[p2].weight; } // end for }
6. 编码和解码
数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。
数据解压过程称为解码。即将二进制位串转换为对应的字符。
7. 等长编码方案和变长编码方案
给定的字符集C,可能存在多种编码方案。
(1) 等长编码方案
等长编码方案将给定字符集C中每个字符的码长定为[lg|C|],|C|表示字符集的大小。
【例】设待压缩的数据文件共有100000个字符,这些字符均取自字符集C={a,b,c,d,e,f},等长编码需要三位二进制数字来表示六个字符,因此,整个文件的编码长度为300000位。
(2)变长编码方案
变长编码方案将频度高的字符编码设置短,将频度低的字符编码设置较长。
【例】设待压缩的数据文件共有100000个字符,这些字符均取自字符集C={a,b,c,d,e,f},其中每个字符在文件中出现的次数(简称频度)见表6.5。
表6.5 字符编码问题
-----------------------------------------------------------------
字符 a b c d e f
频度(单位:千次) 45 13 12 16 9 5
定长编码 000 001 010 011 100 101
变长编码 0 101 100 111 1101 1100
-----------------------------------------------------------------
根据计算公式:
(45*1+13*3+12*3+16*3+9*4+584)*1000=224000
整个文件被编码为224000位,比定长编码方式节约了约25%的存储空间。
注意:
变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。
【例】设E、T、W分别编码为00、01、0001,则解码时无法确定信息串0001是ET还是W。
8. 前缀码方案
对字符集进行编码时,要求字符集中任一字符的编码都不是其它字符的编码的前缀,这种编码称为前缀(编)码。
注意:
等长编码是前缀码
9.最优前缀码
平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩效果亦最佳。
其中:
pi为第i个字符得概率,
li为码长
【例】若将表6.5所示的文件作为统计的样本,则a至f六个字符的概率分别为0.45,0.13,0.12,0.16,0.09,0.05,对变长编码求得的平均码长为2.24,优于定长编码(平均码长为3)。
利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20%至90%,其压缩效率取决于被压缩文件的特征。
10. 具体做法
(1)用字符ci作为叶子,pi或fi做为叶子ci的权,构造一棵哈夫曼树,并将树中左分支和右分支分别标记为0和1;
(2)将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。该编码即为最优前缀码(也称哈夫曼编码)。
11. 哈夫曼编码为最优前缀码
由哈夫曼树求得编码为最优前缀码的原因:
① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li,平均码长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树,因此编码的平均码长(或文件总长)亦最小。
② 树中没有一片叶子是另一叶子的祖先,每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。
12. 求哈夫曼编码的算法
(1)思想方法
给定字符集的哈夫曼树生成后,求哈夫曼编码的具体实现过程是:依次以叶子T[i](0≤i≤n-1)为出发点,向上回溯至根为止。上溯时走左分支则生成代码0,走右分支则生成代码1。
注意:
① 由于生成的编码与要求的编码反序,将生成的代码先从后往前依次存放在一个临时向量中,并设一个指针start指示编码在该向量中的起始位置(start初始时指示向量的结束位置)。
② 当某字符编码完成时,从临时向量的start处将编码复制到该字符相应的位串bits中即可。
③ 因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符'\0',bits的大小应为n+1。
(2)字符集编码的存储结构及其算法描述
typedef struct { char ch; //存储字符 char bits[n+1]; //存放编码位串 }CodeNode; typedef CodeNode HuffmanCode[n]; void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H) {//根据哈夫曼树T求哈夫曼编码表H int c,p,i;//c和p分别指示T中孩子和双亲的位置 char cd[n+1]; //临时存放编码 int start; //指示编码在cd中的起始位置 cd[n]='\0'; //编码结束符 for(i=0,i<n,i++){ //依次求叶子T[i]的编码 H[i].ch=getchar();//读入叶子T[i]对应的字符 start=n; //编码起始位置的初值 c=i; //从叶子T[i]开始上溯 while((p=T[c].parent)>=0){//直至上溯到T[c]是树根为止 //若T[c]是T[p]的左孩子,则生成代码0;否则生成代码1 cd[--start]=(T[p).1child==C)?'0':'1'; c=p; //继续上溯 } strcpy(H[i].bits,&cd[start]); //复制编码位串 }//endfor }//CharSetHuffmanEncoding
有了字符集的哈夫曼编码表之后,对数据文件的编码过程是:依次读人文件中的字符c,在哈夫曼编码表H中找到此字符,若H[i].ch=c,则将字符c转换为H[i].bits中存放的编码串。
对压缩后的数据文件进行解码则必须借助于哈夫曼树T,其过程是:依次读人文件的二进制码,从哈夫曼树的根结点(即T[m-1])出发,若当前读人0,则走向左孩子,否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发继续译码,直至文件结束。
发表评论
-
红黑树简介
2011-09-08 15:35 1386一、红黑树介绍 红黑树由Rudolf Bayer于1 ... -
排 序
2011-07-31 21:17 10401. 排序的分类 在 ... -
散列技术
2011-07-27 14:26 6821. 前言 散列方法不同于顺序查找、二分查找、二叉排 ... -
查 找
2011-07-21 20:04 11021. 前言 由于查找 ... -
图的遍历
2011-07-12 23:48 3092与树类似,遍历也 ... -
图——图的基础
2011-06-08 15:39 8001. 前言 图是一种非线性数据结构,是一种更为复杂的 ... -
树——树的转换
2011-05-23 16:53 15261. 树的存储结构 通常,树的存储结构有三种,双亲表 ... -
树——线索二叉树
2011-05-17 13:28 14571. 前言 n个结点的二叉链表中含有n+1个空指针域 ... -
树——二叉树的遍历
2011-05-16 16:36 10651. 前言 所谓遍历( ... -
树——二叉树基础
2011-05-05 15:32 16931. 前言 二叉树 ... -
树——基础
2011-05-05 15:30 8261. 前言 树形结构 ... -
广义表
2011-05-05 14:14 15031. 广义表的定义 ... -
矩阵的存储
2011-05-04 14:25 17361. 前言 矩阵是许多科学与工程计算中经常遇到的问题 ... -
串基础
2011-05-03 14:15 8301. 串的定义 串( ... -
队列基础
2011-04-30 20:55 10651. 队列的定义 队列是一种特殊的线性表,它包含一个 ... -
栈基础
2011-04-29 14:06 12471. 栈的基础 栈,也成为堆栈,是一种重要的线性结构。 ...
相关推荐
树的应用——哈夫曼编码 二、 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 从...
重庆大学数据结构项目2——哈夫曼编码树.用MFC实现界面。界面良好,程序结构清晰
数据结构课程的课程设计,实现哈夫曼树,压缩文件
这是哈夫曼树源代码的源代码。可以编码,解码。是用VS2005编写的。
这是大二时的数据结构的课设,今天与大家分享。可以读写文件,编码译码,以及对输入的异常处理。
哈夫曼树 基本功能: (1) 从文件中读出一篇英文文章,包含字母和空格等字符。 (2) 统计各个字符出现的频度。 (3) 根据出现的频度,为每个出现的字符建立一个哈夫曼编码,并输出。 (4) 输入一个字符串,为其...
设计内容: 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。
构建Huffman树,详细展示Huffman的初态和终态,通过Huffman树生成Huffman编码。
二叉树的应用——哈夫曼树和哈夫曼编码.pdf二叉树的应用——哈夫曼树和哈夫曼编码.pdf
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。
有以下功能: ...打印哈夫曼树 将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中 附带详细的设计报告(最后的课程设计等级被评定为优秀)
哈夫曼编码的演示程序 可以由用户指定每个字符的权值进行编码 也可以输入一段字符串,程序自动计算每个字符的权值。...建立哈夫曼树之后,可以对一段字符串进行相应的加密。结果输出到文本文件中。
《数据结构》实验,(人民邮电出版社)哈夫曼编码部分
数据结构中很重要的——哈夫曼树\哈夫曼编码。VC6.0调试通过。
哈夫曼树的应用——数据结构课程设计
c++实现:动态查找——二叉排序树及查找,哈夫曼树与哈夫曼编码,栈的应用——括号匹配检验,含数据结构课程设计报告和截图
树的应用——哈夫曼编/译码 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入字符及权值的基础上求哈夫曼编码。...
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,请设计这样的一个简单编/译码系统。
用树结构构造出哈弗曼树,然后再求出哈弗曼编码,实现求解的过程
数据结构实验课本中的一道实验题——哈夫曼编译码,希望对大家有所帮助。