哈夫曼树毕业论文修改版.doc

本科毕业论文本科毕业论文 论文题目论文题目 哈哈夫夫曼曼树树及及其其应应用用 学生姓名学生姓名 专业班级专业班级 信息与计算科学专业信息与计算科学专业 20082008 级级 1 1 班班 指导教师指导教师 20122012 年年 5 5 月月 2020 日日 教学单位教学单位 数数 学学 系系 学生学号学生学号 编编 号号 目 录 一 、论文正文 .(1) 1 哈夫曼树 .(1) 1.1 哈夫曼树的基本概念.(1) 1.2 哈夫曼算法证明.(2) 2 哈夫曼算法构造 .(4) 2.1 哈夫曼树的构造算法.(4) 2.2 举例说明其构造过程.(5) 3 哈夫曼树的应用 .(6) 3.1 用于最佳判断过程.(6) 3.2 用于通信编码.(7) 4 C+程序实现(8) 5 总结 .(11) 参考文献 .(11) 二、附录 1. 开题报告(13) 2. 结题报告(14) 3. 答辩报告(15) 哈夫曼树及其应用哈夫曼树及其应用 （宝鸡文理学院 数学系,陕西 宝鸡 721013） 摘摘 要要: :简要介绍了哈夫曼树的相关概念,阐述了哈夫曼树的基本原理,探讨 了它在相关领域的实际应用,并采用 C+对其进行了算法实现. 关键词关键词: :哈夫曼树;二叉树;带权路径长度;根结点;叶结点 哈夫曼树是由哈夫曼于 1951 年所创立并改进的,他本人也根据哈夫曼树提 出了相应的编码.由于哈夫曼树是具有最小加权路径长度的二叉树,故哈夫曼编 码能产生较短的码文.基于这个优势,在信息化高度发达的当今社会,对信息的传 递也有着较高要求的我们,希望信息在传递过程中,能够保持节省性和保密性,哈 夫曼编码则很好的满足了这方面的要求,因而对其的研究是相当有必要的. 1 哈夫曼树哈夫曼树 1.1 哈夫曼树的基本概念哈夫曼树的基本概念 首先要了解树的概念.树是一种数据结构,是由一个或多个结点组成的有限 集合.因其存放方式颇像一棵树又有树杈,因而称其为树.现简要介绍一下相关概 念. 定义定义 1.1 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路, 称为路径. 定义定义 1.2 若将树中结点都赋给一个具有某种含义的数值,则这个数值称为该结 点的权. 定义定义 1.3 由根结点到所有叶结点的路径长度之和称为二叉树的路径长度. 定义定义 1.4 从根结点到叶结点的路径长度与相应结点权值之积的和叫做二叉树的 带权路径长度. 定义定义 1.5 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构 造的具有最小带权路径长度的二叉树. 如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树 有个带权值的叶结点,那么,二叉树的带权路径长度应记为:n , n k kk LWWPL 1 其中为第个叶结点的权值;为第个叶结点的路径长度. k Wk k Lk 现用下图解释上述相关概念 1 . 1 . 1 图1 . 1 . 1 2 在图中,即为根结点,而则为叶结点,若的权值分别为则1 . 1 . 1ACB,CB,4 , 3 二叉树路径长度为 2,二叉树的带权路径长度为 7,即.71413WPL 例例 下面我们结合实例来说明哈夫曼树.如果我们给定叶子结点的个数及每个叶 子结点的权值构造出若干棵形态各异的二叉树如图所示,其中根结点和叶结点之 间的数字表示各叶子结点的权值. )(a)(b)(c 2 . 2 . 1图 ;4922351638 3 ;4132352618 2 ;4222252628 1 WPL WPL WPL 按照的计算方法,经过计算比较后,我们发现,图的值最WPL2 . 2 . 1)(bWPL 小,它即为哈夫曼树. 由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同 的带权路径长度.那么如何找到带权路径长度最小的二叉树呢？根据哈夫曼树的 定义,一棵二叉树要使其值最小,必须使权值越大的叶结点越靠近根结点,WPL 而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具 有最小的带权路径长度,这是生成算法的一种基本思想. 1.2 哈夫曼算法证明哈夫曼算法证明 定理定理 1 如果是带权的哈夫曼树,其中我们有下述T n WW, 1 . 21n WWW 结论成立. (1)若和是兄弟,则; i W j W ji WLWL (2)和是兄弟,且在所有分支点中,的层数最大; 1 W 2 W 21 WW (3)将带权的分支点改为带权的树叶,得带权为 21 WW 21 WW 的树,则也是哈夫曼树. n WWWW, 321 T T 证明证明: :(1) 由顶点的层数定义即知结论显然成立. 3 (2) 若只有 2 片树叶,则,和是兄弟,是T 1 2 WLWL i1 W 2 W 21 WW 和的父亲,也是根,是唯一的分支点. 1 W 2 W 设,在所有分支点中, 的层数最大, 的两个儿子分别是和,3nvv i W j W 则 ,. 1 WLWL i 2 WLWL i 1 WLWL j 2 WLWL j 假如,将和互换,得到新的树,记为, 1 WLWL i i W 1 W T 则 1111 WWLWWLWWLWWLTWTW iiii 111 WWWLWWWL iii ii WWWLWL 11 因为,当时,此时显然是兄弟,从 i WW 1i WW 1ii WWWW 132 21,W W 而只需考虑的情形,于是有 i WW 1 TWTWTWTW , 0 这与是哈夫曼树矛盾,所以.T 1 WLWL i 同理可证明,因此.这样分 2 WLWL j ji WLWLWLWL 2121,W W 别是和,否则将分别与互换,得到一棵树,但 i W j W 21,W W ji WW , jjii WLWWLWWLWWLW 2211 与是哈夫曼树矛盾.T (3) 首先可知.假设不是哈夫曼树,是带权 21 WWTWTW T 1 T 的哈夫曼树.在中以的两个儿子和为树叶, n WWWW, 321 T 21 WW 1 W 2 W 成为分支点,得到一棵带权的二叉树,则 21 WW n WWW, 212 T 2112 WWTWTW 因为和都是带权的二叉树,而是哈夫曼树,所以 T 1 T n WWWW, 321 1 T . TWTW 1 4 假如,则 TWTW ) ( 1 . TWWWTWWWTWTW 212112 这与是带权的哈夫曼树矛盾,因此.即为带权T n WWW, 21 TWTW 1 T 的哈夫曼树. n WWWW, 321 2 哈夫曼算法构造哈夫曼算法构造 哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径 长度的二叉树.尽管哈夫曼树可以通过比较后得出,可是在运算过程中往往WPL 会出现一些问题,使其实现起来并不容易,因而我们可以应用编程来有效地解决 这个问题. 2.1 哈夫曼树的构造算法哈夫曼树的构造算法 为了构造权值为的哈夫曼树,哈夫曼提出了一种构造算法,现 n WWWW, 321 将其陈述如下: 步骤步骤 1 根据题目给定的个权值构造有下列棵二叉树的集合 n n WWWW, 321 n ,其中每棵二叉树中只有一个带权为的根结点,其 n TTTTF, 321 i T i W 左右树均为空; 步骤步骤 2 在中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二 F 叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之 和; 步骤步骤 3 在中删除这两棵树,同时将新得到的二叉树加入中;FF 步骤步骤 4 重复步骤 2 和步骤 3,直到只含有一棵树为止,这棵树便是哈夫曼树.F 2.2 举例说明其构造过程举例说明其构造过程 假设叶结点权值集合为的哈夫曼树的构造4 , 3 , 2 , 1W 第一步 我们根据给定的 4 个权值来构造 4 棵二叉树的集合.F 第二步 在找出权值中最小的两个作为新二叉树的左右子树,且置新的二F 叉树根结点权值是其左右结点权值之和. 5 第三步 将次小的树与新生成的树再作为左右子树生成权值为 6 的新树; 第四步 再次将权值为 4 的树在同上一个权值为 6 的树再次生成新树即可. 从以上过程可以计算出这棵二叉树的带权路径长度为 19. 3 哈夫曼树的应用哈夫曼树的应用 3.1 用于最佳判断过程用于最佳判断过程 在考查课记分时往往把百分制转换成优秀,良好 ,中90x9080 x 等 ,及格,不及格五个等级.若不考虑学生考试8070 x7060 x60x 分数的分布概率,程序判定过程很容易写成所示的方法.一般来讲学生考1 . 1 . 3图 分大多分布在 70 至 80 分之间,从可看出这种情况的值要比较 2 至 3 次1 . 1 . 3图x 才能确定等级.而学生中考试不及格的人数很少,值比较一次即可定等级.能否x 使出现次数多的在 70 至 80 分之间的值比较次数减少,而使很少出现的低于 60x 分的值比较次数多一些,以便提高程序的运行效率是一个问题.x 6 YY Y Y Y Y Y Y N N N N N N N N Y Y YYN N N N 1 . 1 . 3图2 . 1 . 3图 假设学生成绩对于不及格,及格,中等,良好和优秀的分布概率分别为 5%,15%,40%, 30%,10%,以它们做为叶子的权值来构造哈夫曼树,如图所示.2 . 1 . 3 此时带权路径长最短,其值 210%.它可以使大部分的分数值经过较少的比较次数 得到相应的等级.但是,事物往往不是绝对的,此时每个判断的框内条件都较为复 杂,需比较两次,反而降低运行效率.所以我们采用折中作法,调整后得图判3 . 1 . 3 定树,更加切合实际. X #include #include #define Max 32767 /*int 型最大可取值*/ typedef struct Node int weight; /*定义权值*/ int parent,Lchild,Rchild; /*定义双亲结点,左、右孩子结点*/ HTNode; typedef char *HuffmanCode; /*双重指针存储哈夫曼编码*/ void select(int w,int n,int /*min1 最小,min2 次小*/ min1=w1;xb1=1; min2=w2;xb2=2; if(min1min2) min1=w2;xb1=2; min2=w1;xb2=1; /*安排第一和第二个数的显示顺序 */ for(int i=3;i2 的数组元素*/ if(wixb2) /*保证 下标小 的做左孩子*/ hti.Lchild=xb2; hti.Rchild=xb1; wxb1=Max; wxb2=Max; /*修改选过的节点的权值,避免下次再 被选中 */ /*输出所有节点的下标、权值、双亲、左孩子、右孩子的下标*/ cout #define N 14 /* N 代表数组长度,要改变数组长度时 ,只需要将 14 改为 想要的数*/ 11 void main() int w7; /*w 中的数不是固定的可以根据需要改变*/ printf(“ please input number for w n“); for(int j = 1;j =7;+j) scanf(“%d“, int n=7; /*n 是可以修改的*/ int m=2*n-1; HTNode ht14;/*哈夫曼树成员数组 从 1-13;0 下标不用.用于 双亲表示法存储 Huffman 树*/ HuffmanCode hc8;/*7 个叶子节点也就是 w14里面的,从 1-7;0 下 标不用 其中 HuffmanCode 被自定义为 char 型指针数据类型*/ createHTree(ht,hc,w,n); coutendlendl“各叶子节点的编码如下:“endl; for(int i=1;i=n;i+) couti“ :“hciendl; 5 总结总结 程序经运行得到很好的实现,但程序中仍存在一些不足之处,需要再加以改 进.通过此次论文设计很好的增强了我对编程及二叉树理论的认识和对 C+软件 的应用能力,也是将理论知识运用于解决实际问题的一次新尝试. 致谢:本文在写作过程中得到安海龙老师的指导. 参考文献参考文献: : 1 (美)John A. Dossey.离散数学 M.北京:清华大学出版社,2005:207-219. 2 方世昌.离散数学 M .西安:西安电子科技大学出版社,2010:304-310. 3 陈火旺.数据结构与算法 M.湖南:中南大学出版社,2005:125-127. 4 王宏生,宋继红.数据结构 M .北京:国防工业出版社,2006:183-187. 5 严蔚敏.数据结构 M .北京:清华大学出版社,1995:145-147. 6 谭浩强.C+面向对象程序设计 M.北京:清华大学出版社,2007:134-231. 7 李俊峰,冯刚.离散数学 M .北京:清华大学出版社,2006:341-345. Huffman tree and its application (Department of mathematics, Baoji University of Arts and Sciences, Baoji 721013,Shaanxi, China) Abstract: