文档介绍：哈夫曼树
LT
北京邮电大学信息与通信工程学院
第3页/共9页
北京邮电大学电信工程学院
第1页
数据结构实验报告
实验名称： 实验三——哈夫曼树
学生姓名： 吴淳
班 级： 2011211106班
班内序号： 27
学 号： 2011210180
日 期： 2012年11月29日
实验要求
一、实验目的：
掌握二叉树基本操作的实现方法；
了解哈夫曼树的思想和相关概念；
培养使用二叉树解决实际问题的能力。
二、实验内容：
利用二叉树结构实现哈夫曼编/解码器
（Init）：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
(CreatTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
北京邮电大学信息与通信工程学院
第3页/共9页
北京邮电大学电信工程学院
第1页
(Print)：以直观的方式打印哈夫曼树(选作)。
，并进行分析，讨论哈夫曼编码的压缩效果。
测试数据如下：
I love data love will try my best to study data structure.
“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。且哈夫曼树是一棵只有度为0和2的结点的正则二叉树。一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一位数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以可以使用一个静态三叉链表来存储哈夫曼树。
class Huffman
北京邮电大学信息与通信工程学院
第4页/共9页
北京邮电大学电信工程学院
第1页
北京邮电大学信息与通信工程学院
第5页/共9页
北京邮电大学电信工程学院
第1页
【图三】示意图2
一．关键算法：
(1).初始化函数（void Huffman::Init(int weight[],int n)）
算法伪代码：
1. 创建一个长度为2n-1的三叉链表；
，并赋予其相应权值，同时将其双亲、左孩子、右孩子值赋为-1;
；
：i=n；Selectmin(HTree,i,x,y)；合成HTree[x]和 HTree[x]。
5. 若满足i<2*n-1，重复上一步，每次i++。
(2)．创建编码表void Huffman::CreatTable(char character[],int n)
算法伪代码：
北京邮电大学信息与通信工程学院
第6页/共9页
北京邮电大学电信工程学院
第1页
=0；HcodeTable[i].data=character[i]；child=i；parent=HTree[i].parent；k=0;
. 3 .如果parent!=-1;
，则其对应的编码为0，否则为1;
++;
将当前结点的parent值赋给child值，child的parent值赋给parent值;
；
<n,重复2和3；
5. 最后一位编码=’\0’;
6. 将已完成的编码倒序
7．输出编码表
(3). 选择两个最小权值（void Huffman::Selectmin(HNode*HTree,int n,int &i1,int &i2)
北京邮电大学信息与通信工程学院
第8页/共9页
北京邮电大学电信工程学院
第1页
）
算法语言描述：
从下标为0的结点开始，寻找第一个没用过的结点
从第一个没用过