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

本科毕业论文 论文题目 哈夫曼树及其应用 学生姓名　 专业班级　 信息与计算科学专业2008级1班 指导教师　 2012年 5月 20日 目 录 一 、论文正文 (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 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树. 如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树有个带权值的叶结点,那么,二叉树的带权路径长度应记为: , 其中为第个叶结点的权值;为第个叶结点的路径长度. 现用下图解释上述相关概念 图 在图中,即为根结点,而则为叶结点,若的权值分别为则二叉树路径长度为2,二叉树的带权路径长度为7,即. 例 下面我们结合实例来说明哈夫曼树.如果我们给定叶子结点的个数及每个叶子结点的权值构造出若干棵形态各异的二叉树如图所示,其中根结点和叶结点之间的数字表示各叶子结点的权值. 按照的计算方法,经过计算比较后,我们发现,图的值最小,它即为哈夫曼树. 由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度.那么如何找到带权路径长度最小的二叉树呢？根据哈夫曼树的定义,一棵二叉树要使其值最小,必须使权值越大的叶结点越靠近根结点,而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具有最小的带权路径长度,这是生成算法的一种基本思想. 1.2 哈夫曼算法证明 定理1 如果是带权的哈夫曼树,其中我们有下述结论成立. (1)若和是兄弟,则; (2)和是兄弟,且在所有分支点中,的层数最大; (3)将带权的分支点改为带权的树叶,得带权为的树,则也是哈夫曼树. 证明:(1) 由顶点的层数定义即知结论显然成立. (2) 若只有2片树叶,则,和是兄弟,是和的父亲,也是根,是唯一的分支点. 设,在所有分支点中,的层数最大,的两个儿子分别是和, 则 ,,,. 假如,将和互换,得到新的树,记为, 则 因为,当时,,此时显然是兄弟,从而只需考虑的情形,于是有 这与是哈夫曼树矛盾,所以. 同理可证明,因此.这样分别是和,否则将分别与互换,得到一棵树,但 与是哈夫曼树矛盾. (3) 首先可知.假设不是哈夫曼树,是带权的哈夫曼树.在中以的两个儿子和为树叶,成为分支点,得到一棵带权的二叉树,则 因为和都是带权的二叉树,而是哈夫曼树,所以 . 假如,则 . 这与是带权的哈夫曼树矛盾,因此.即为带权的哈夫曼树. 2 哈夫曼算法构造 哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权