霍夫曼树_实验报告讲述教程.doc

西安交通大学实验报告 课程 数据结构 实验名称 树的遍历及霍夫曼树 第 1 页 共 页 系别__ 自动化 实 验 日 期 / 2014 年 11 月 22 日 专业班级 自动化43班 实 验 报 告 日 期 2014 年 12月 7 日 姓名 李欣阳 学号 2140504066 报 告 退 发 ( 订正 、 重做 ) 同 组 人 无 教 师 审 批 签 字 一、实验目的 1. 掌握结构体、指针及二叉树的生成、遍历等基本操作； 2. 掌握霍夫曼树编码译码的原理； 3. 熟练掌握树的基本操作。 二、实验内容与要求 1. 通过键盘输入一段字符（长度≥20），构建霍夫曼树； 2. 根据该树求每个字符的编码，并对该字符串进行编码； 3.将获得的编码进行译码； 4.基于该霍夫曼树，实现非递归的先序遍历算法来输出该树中的叶子节点； 三、问题分析 对于固定的叶子节点数和权值，带权路径最短的二叉树称为霍夫曼树或者最优二叉树，霍夫曼树可以用来设计二进制的前缀编码。假设有一棵二叉树，其叶子节点分别为A、B、C、D构建一棵有四个叶子节点的二叉树二叉树，使这四个字母分别处于四个叶子节点的位置。约定连接左子树与根节点的树枝为1，连接根节点与右子树的树枝为0，则在对树进行先序遍历时，记录下经过的边即可得到一个二进制序列，这个二进制序列可以作为相应叶子节点字母的霍夫曼编码，这就是霍夫曼编码的基本思路。 3.1 霍夫曼树的创建 利用二叉树进行编码译码，并且使编码具有最佳的使用效果，就要满足以下两个基本条件： 任何两个不同的字符或者字符串不能有相同的编码，这就要求每个字符都有其独特的唯一的编码，即任意一个字符的编码都不能是另一个字符编码的前缀； 字符串的编码要尽可能的短，以便于存储和解码。 基于以上编码要求，选择霍夫曼树作为字符编码译码的工具是合理的。霍夫曼树的构建方法如下： 根据给定的n个权值构成n棵二叉树的集合F，其中没课二叉树中只有一个 带权的根节点，其左右子树均为空； 在F中选取两棵根节点最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和； 在F中删除这两棵树，同时将构建的新的二叉树加入F中； 重复（2）和（3）知道F中只含一棵树为止，这棵树就是霍夫曼树。 3.2 字符权值的确定 基于以上霍夫曼树的构建方法，进行编码操作的前提就是获取待编码的字符串的中各字符的权值，因此要设计算法求得各字符权值。 首先以字符数组的方式存储字符串构造字符数组char Letter[]用于存储字符串中出现的字符，以及整形数组int Weight[]用于存储对应字符的权重。先取字符串的第一个字符存入char Letter[]的第一个位置并设置该字符对应的标志flag=1，把char Letter[]的第一个位置和字符串的各位置依次进行比较，如果相同则flag=1表明该字符已记录同时int Weight[]相应位置增加1，如果不同则flag=0表明出现新字符；以此类推知道所有字符的flag标记都为1。此时每个不同的字符都已经存入char Letter[]并且其权重已经记录在int Weight[]数组中。char Letter[]和int Weight[]数组就可以作为构建霍夫曼树的依据了。 3.3 字符串编码方法 在已经创建好霍夫曼树的前提下，要对字符串进行编码，本文采取单一字符编码连接的方法进行字符串编码，即先对字符串中的每个字符进行编码，然后把这些编码按照原字符串顺序进行简单连接即可构成完整的霍夫曼编码。 求单一字符的霍夫曼编码思路很简单，就是找到根节点到字符所在的叶子节点的一条树枝。为了寻找树枝有方向可寻，本算法采取逆向寻取得方法对字符进行编码，即先找到对应的叶子节点，然后向上寻找叶子节点，逆向记录所走路径即可。求得单一字符的霍夫曼编码之后，利用字符串连接函数strcat对单一字符编码进行有次序的简单连接即可。 3.4 霍夫曼译码算法 在已知霍夫曼编码的情况下进行译码则要简单的多，其过程类似于二叉树的遍历却稍有不同。按照所给出的霍夫曼二进制序列从根节点出发依次寻访下一个节点，遇见1则寻访左子树，遇到0则寻访右子树，如果到达叶子节点则说明找到了一个字符，记录后从根节点重新开始寻访过程，直到此过程进行到霍夫曼编码的最后一位。 3.5 霍夫曼树的先序遍历 采用二叉树现需遍历算法即可，按照先根后左后右的顺序进行遍历此处不再展开。 四、树结构及基本操作 4.1 树的说明及抽象数据类型 本实验采用树这一结构来实现。树是若干个存在相