二叉树的应用 - 哈夫曼树和哈夫曼编码 - 图文

哈夫曼树和哈夫曼编码

一、基本概念

1.

文本由字符构成，字符用编码表示，ASCII编码是一种等长的编码，每个字符的编码长度是相同的。哈夫曼树和哈夫曼编码使得频率高的字符有较短的编码，使用频率较高的字符有较长的编码。

2.前缀编码

字符编码可以有不同的长度，只要每个字符的编码和其它字符的编码的前缀不同即可，这种编码称为：前缀编码。

3.最小代价的二叉树

所有字符都包含在叶结点上，权值大的叶子应该尽量靠近树根，使它的编码尽可能短。权值小的叶子可以适当离树根远一点。

二、哈夫曼算法

1.目的

构成一棵最优二叉树，每个结点的权值就是它出现的频率，每棵树的权值由它所有叶结点的出现频率的和组成。

2.

一旦构成哈夫曼树，每个字符的哈夫曼编码就是从根到存储该字符的叶结点的路径，如定义左枝为0，右枝为1.

三、哈夫曼算法的实现

1.原理

（1）

哈夫曼树类的对象可以接收一组符号以及对应的权值，并返回每个符号对应的哈夫曼编码。 构造函数接收一组代编码的符号以及对应的权值，构造一棵哈夫曼树；返回编码的函数getCode根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。

（2）

哈夫曼树可以用一个规模为2n的数组来存储，n为待编码元素的个数。下标为0的数组元素不用，根存放在下标为1的元素中；叶结点存放在n到2n-1的位置。每个数组元素保存的信息为：结点的值、权值、父结点、左右儿子的位置。

初始时，将待编码的元素和响应的权值放入数组的第n到2n-1的位置，所有的结点的父结点和左右儿子的位置的字段置为0，表示所有树都只是根结点。

第一次归并，在第n到2n-1的元素中查找权值最小的树，即权值最小且父结点都为0的数组元素，归并后的树的根保存在n-1的元素中，并设置父子关系。

第二次归并，在第n-1到2n-1的元素中查找权值最小的树，归并后的树的根保存在n-2的元素中，并设置父子关系。

最后一次归并的结果放在下标为1的元素中，至此，完成哈夫曼树的生成。

2.代码

5-13 哈夫曼树类的定义 代码分析 template //模板类 class hfTree{//哈夫曼树类

Node *elem;//定义一个数组,elem是数组的起始位置，哈夫曼树被保存在一个数组中 int length;//数组的规模长度，根据待编码的结点预先静态分配空间 public: //公有成员函数

struct hfCode{//保存哈夫曼编码的类型 };

hfTree(const Type*x, const int*w, int size);//构造函数，构造函数接收一组

Type data;//待编码的字符值 string code;//对应的哈夫曼编码

private: //私有成员变量

struct Node//数组中的元素类型：结点类 { Type data;//结点值 int weight;//结点的权值

int parent,left,right;//父结点以及左右儿子的下标地址 };

待编码的字符以及对应的权值，构造一棵哈夫曼树

};

void getCode(hfCode result[]);//返回哈夫曼编码的函数 ~hfTree(){delete []elem;}//析构函数，释放存储空间

5-14 哈夫曼树的构造函数 代码分析 template

hfTree::hfTree(const Type*v, const int *w, int size)//哈夫曼树的构造函数，有3个参数，一组待编码的符号，符号对应的权值，前面两个数组的数组规模 { const int MAX_INT=32767;

int min1,min2;//最小树、次小树的权值，权值最小的两棵树 int x, y;//最小树、次小树的下标

length=2*size; //待编码的符号有n个，哈夫曼树的规模就为2n-1，由于数组是从0开始，所以数组规模为2n，根结点保存在下标为1的元素中 elem=new Node[length];//申请一个保存哈夫曼树的数组

for(int i=size;i

elem[i].parent=elem[i].left=elem[i].right=0;//将符号的父结点以及左右儿子都设为

0，表明它们都是只有根结点的树 }

for(i=size-1;i>0;--i)//for循环完成size-1次的归并

{ min1=min2=MAX_INT;x=y=0;// min1,min2分别保存两棵权值最小的数的权值，x、y分别表示这两棵树的树根在数组中的下标

for(int j=i+1;j

if(elem[j].parent==0)

if(elem[j].weight

{min2=min1;min1=elem[j].weight;x=y;y=j;} else if(elem[j].weight

{min2=elem[j].weight;x=j;}

elem[i].weight=min1+min2;//归并这两棵树，形成新树i，i这棵树的权值=min1+min2（分

别保存挑选出的两棵权值最小的树的权值）

elem[i].left=x;elem[i].right=y;elem[i].parent=0;//将挑选出来的两个结点作为左、

右子树，构建一棵新树，i为根结点 }

elem[x].parent=i;elem[y].parent=i;//i是挑选出来的两个结点的父结点

}

5-15 哈夫曼的getCode函数 代码分析 template

void hfTree::getCode(hfCode result[])//哈夫曼树的getCode函数，返回的是一个数组，数组元素类型是hfCode，每一个元素包含待编码的符号和它对应的编码，编码是一个比特串，用字符串类型表示

{ int size=length/2;//符号数组规模=哈夫曼数组规模/2

int p,s;//s是追溯过程中正在处理结点的下标，p是s的父结点下标 for(int i=size;i

{result[i-size].data=elem[i].data; // result数组中第一个元素符号是哈夫曼数组elem

中间的元素符号，因为哈夫曼数组elem包含了元素符号数组和元素符号权值数组，而符号数组规模=权值数组规模，所以哈夫曼数组elem数组是它们的两倍。现在要取出符号，所以从哈夫曼数组elem一半开始取

result[i-size].code=\//当前结点对应的哈夫曼编码 p=elem[i].parent;s=i; while(p){//向根追溯

if(elem[p].left==s)//若发现当前结点是根结点的左儿子

result[i-size].code='0'+result[i-size].code;//则在字符串前添加0

else result[i-size].code='1'+result[i-size].code; //若发现当前结点是根结点的右

儿子，则在字符串前添加1

s=p;p=elem[p].parent;//继续往上一层移动，p为更大树的根结点，s取代原先p的位置

} } }

5-16 哈夫曼树的使用实例 代码分析 int main()

{ char ch[]={\//待编码的字符

int w[]={10,15,12,3,4,13,1};//待编码的字符对应的权值

hfTreetree(ch,w,7);//构造函数，字符数组ch，权值数组w,数组规模7

hfTree::hfCode result[7];//定义一个存放编码的数组hfCode tree.getCode(result);//调用getCode函数

for(int i=0;i<7;++i)//for循环，输出字符以及字符对应的哈夫曼编码 cout<