哈夫曼树实训报告

《哈夫曼树实训报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法》实训报告专业名称：软件工程所在班级：卓越计Y111学号：201100403235姓名：徐向阳日期：2013.1.5哈夫曼编／译码器目录1、实训要求........................................................................................22、系统分析与设计............................................................................53、算法设计说明...................

2、.............................................................54、算法实现.........................................................................................64.1程序代码..................................................................................64.2调试结果.............................

3、...................................................195、调试经验......................................................................................236、实训体会......................................................................................237、参考文献.....................................

4、.................................................23-1-一、实训要求—基于哈夫曼树的编码与译码系统哈夫曼树又称最优二叉树，它是一类带权路径长度最短的树，有着广泛的应用，如JPEG中就应用了哈夫曼编码。在给出哈夫曼树的定义之前，首先给出路径和路径长度的概念。从树中的一个节点到另一个节点之间的分支构成这两个节点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到树中每一节点的路径长度之和。根据树的路径长度，可知在节点数目相同的二叉树中，完全二叉树的路径长度最短。在树中还可以为树的节点添加权形成带权二叉树

5、。在一些应用中，这些权值可以是一个具有某种意义的实数。对于带权二叉树，定义节点的带权路径长度为节点到树根之间的路径长度与该节点权值的乘积。树的带权路径长度(weightedpathlengthoftree)为树中所有叶子节点的带权路径长度之和，记为：nWPL=∑wilii=1其中，n表示叶子节点的数目；wi和li分别表示叶子节点ki的权值和根到节点岛之间的路径长度。树的带权路径长度也称为树的代价。所谓最优二叉树是指带权路径长度最小的二叉树，下图给出了3种不同路径长度的带权二叉树。具有不同带权路径长度的二叉树由此可知，图(c)所示的树的WPL最小，它就是一棵最优二

6、叉树，即哈夫曼树。可以看出，对于最优二叉树，权值越大的节点越接近树的根节点，权值越小的节点越远离树的根节点。根据这一特点，可以得到最优二叉树的构造算法的步骤如下：�根据给定的n个权值（w1，w2，....，wn）构成n棵二叉树的集合（即森林）F=（T1，T2，...，Tn），其中每棵二叉树Ti中只有一个带权为wi的根节点，其左、右子树均为空。�在F中选取两棵根节点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。-2-�在F中删除这两棵树，同时将得到的二叉树加入F中。�重复第一步和第二步，直到F只有一棵树

7、为止，这棵树则为哈夫曼树。上面给出的最优二叉树的构造算法，是由哈夫曼在20世纪50年代提出来的，为了纪念哈夫曼，因此又将最优二叉树称为哈夫曼树。在构造哈夫曼树的过程中常会遇到这样的情况，根节点权值最小的树不止两棵。对于这种情况，只要任选两棵即可。选出的两棵树谁做新节点的左孩子或右孩子均可。从上例所示的构造过程可以看出，经过一次合并，森林中就少一棵树，具有n棵树的森林，经过n-1次合并才能得到一棵哈夫曼树，并且每次合并时都会产生一个新节点，一共会产生n-1个新节点。因此，得到的哈夫曼树具有2n-1个节点，并且，所得到的哈夫曼树中没有度为1的节点。根据这一特点，可以

8、采用一个大小为2n-1的