[数据结构]哈夫曼树和哈夫曼编码
发布时间
阅读量：
阅读量
哈夫曼树
基本概念
称其为最优二叉树之后，在信息论中被定义为其具有最小带权路径长度的特点。对于每个结点而言其至根节点的距离与其权重相乘的结果构成了该结点的贡献值而所有这样的贡献值之和则构成了整个树的空间复杂度计算依据。在所有的可能二叉结构中拥有最小空间复杂度特征的就是我们所说的哈夫曼树而这一数值通常用符号WPL来表示即：
WPL = Σ wiLi
其中WPL表示空间复杂度wi代表各结点权重Li则代表各结点至根节点的距离。
哈夫曼树的构造
算法描述：
根据给定的n个权值{w₁, w₂, …, wₙ}初始化时将每棵二叉树T_i设为仅包含一个权值w_i的根节点，并且左右子 树均为空。
从集合F中选择两棵具有最小权值的二叉 树作为左子 树和右子 树，并生成一个新的 二 叉 树。
从集合F中移除这两棵被选中的 二 叉 树，并将生成的新 二 叉 树重新加入到集合 F 中。
重复上述步骤直至集合 F 仅剩一棵完整的哈夫曼编码 二 叉 树。
由n个叶子节点构成的起始集合中,经过n−1次合并操作,能够得到n−1个新中间节点。构建得到的哈夫曼树结构中包含总计2n−1个节点。
#define N 6 //叶子结点个数
#define M 2N-1 //结点总数
#define EPS 1e-5
typedef char datatype;
typedef struct{
float weight; //结点权值
datatype data; //结点内容
int lchild,rchild,parent; //parent可用来指示进行了合并操作
}hufmtree;
hufmtree tree[M];
void Huffmantree(hufmtree tree[]){
int i,j,p1,p2;
char ch;
float small1,small2,f;
for(i=0;i<M;i++){ //初始化
tree[i].lchild=-1;
tree[i].rchild=-1;
tree[i].parent=-1;
tree[i].weight=0.0;
tree[i].data='0';
}
for(i=0;i<N;i++){ //输入每个点的内容和权值
scanf("%f",%f);
tree[i].weight=f;
scanf("%c",&ch);
tree[i].data=ch;
}
for(i=0;i<M;i++){
p1=p2=0;
small1=small2=Maxval; //Maxval是float类型的最大值
for(j=0;j<i;j++){
if(tree[j].parent==-1){
if(tree[j].weight-small1<EPS){ //改变最小值和次小值
small2=small1;
small1=tree[j].weight;
p2=p1;
p1=j;
}
else if(tree[j].weight-small2<EPS){ //改变次小值
small2=tree[j].weight;
p2=j;
}
}
}
tree[p1].parent=i;
tree[p2].parent=i;
tree[i].lchild=p1; //i是新生成的子树 权值为p1p2权值相加
tree[i].rchild=p2;
tree[i].parent=-1;
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}
AI写代码哈夫曼树的应用：哈夫曼编码
让高频使用的字符与其编码尽可能简短，并且确保任意一个字符的编码都不是另一个字符编码的前缀（以此避免混淆）。因此可以采用二叉树结构来构建相应的二进制前缀码。约定左分支代表字符0，右分支代表字符1，则从根节点到叶子结点路径上的各分支所标记的字符串即作为该叶子节点对应字符的编码。寻求能够使电文传输所需总长度最短的二进制前缀码设计方案，则等价于基于各字符出现频率构建相应的哈夫曼树。
算法描述：
以叶子节点tree[i]为基础开始, 通过获取父节点地址确定父节点树p. 进一步检查其父节点树p的lchild和rchild字段来确定是否为左子树或右子树, 并根据此确定分配值为0或1. 随后以上层父节点为基准点持续向上追溯直至根节点.
具体算法（接上部分）
typedef struct{
char bits[N]; //编码数组位串，N为叶子结点个数
int start;
datatype data;
}codetype;
codetype code[N];
void Huffmancode(codetype code[],hufmantree tree[]){ //hufmantree 接上篇
int i,c,p;
codetype cd; //缓冲变量
for(i=0;i<N;i++){
cd.start=N;
c=i;
p=tree[c].parent;
while(p!=-1){
cd.start--;
if(tree[p].lchild==c) cd.bits[cd.start]='0'; //如果是左孩子则分配0
else cd.bits[cd.start]='1'; //如果是右孩子分配1
c=p;
p=tree[c].parent;
}
code[i]=cd;
}
}
AI写代码哈夫曼树译码
void huffmandecode(codetype code[], hufmtree tree[]){
int i,c,p,b;
int endflag=-1; //电文结束标志-1
i=m-1; //从根节点开始向下搜索
scanf("%d",&b); //读入二进制代码
while(b!=endflag){
if(b==0) i=tree[i].lchild; //其中一位为0，走向左孩子，为1则走向右孩子
else i=tree[i].rchild;
if(tree[i].lchild==-1){ //tree[i]是叶子节点
putchar(code[i].data);
i=m-1; //回到根节点
}
scanf("%d",&b); //输入下一个二进制代码
}
if((tree[i].lchild!=0)&&(i!=m-1)) printf("error\n"); //输入电文有误
}
AI写代码例题：在通信领域中的一份电文包含十个不同类型的符号，在电文中出现的频率分别为8, 21, 37, 24, 6, 18, 23, 41, 56和14，请为这十个符号设计相应的哈夫曼编码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 10 //叶子结点个数
#define M (2*N-1) //结点总数
#define EPS 1000000
typedef char datatype;
typedef struct{
float weight; //结点权值
datatype data; //结点内容
int lchild,rchild,parent; //parent可用来指示进行了合并操作
}hufmtree;
hufmtree tree[M];
typedef struct{
char bits[N]; //编码数组位串，N为叶子结点个数
int start;
datatype data;
}codetype;
codetype code[N];
void Huffmantree(hufmtree tree[]){
int i,j,p1,p2;
char ch;
float small1,small2,f;
for(i=0;i<M;i++){ //初始化
tree[i].lchild=-1;
tree[i].rchild=-1;
tree[i].parent=-1;
tree[i].weight=0;
tree[i].data='0';
}
for(i=0;i<N;i++){ //输入每个点的内容和权值
scanf("%c %f",&tree[i].data,&tree[i].weight);
}
for(i=N;i<M;i++){
p1=p2=0;
small1=small2=10000000000.0 ;
for(j=0;j<i;j++){
if(tree[j].parent==-1){
if(tree[j].weight-small1<EPS){ //改变最小值和次小值
small2=small1;
small1=tree[j].weight;
p2=p1;
p1=j;
}
else if(tree[j].weight-small2<EPS){ //改变次小值
small2=tree[j].weight;
p2=j;
}
}
}
tree[p1].parent=i;
tree[p2].parent=i;
tree[i].lchild=p1; //i是新生成的子树 权值为p1p2权值相加
tree[i].rchild=p2;
tree[i].parent=-1;
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}
void Huffmancode(codetype code[],hufmtree tree[]){ //hufmantree 接上篇
int i,c,p,j;
codetype cd; //缓冲变量
for(i=0;i<N;i++){
cd.start=N;
c=i;
p=tree[c].parent;
while(p!=-1){
cd.start--;
if(tree[p].lchild==c) cd.bits[cd.start]='0'; //如果是左孩子则分配0
else cd.bits[cd.start]='1'; //如果是右孩子分配1
c=p;
p=tree[c].parent;
}
code[i]=cd;
}
for(i=0;i<N;i++) {
printf("%s ",code[i].data);
for(j=code[i].start;j<N;j++){
printf("%c",code[i].bits[j]);
}
}
}
int main(){
hufmtree tree[M];
codetype code[N];
Huffmantree(tree);
Huffmancode(code,tree);
}
AI写代码全部评论 (0)
还没有任何评论哟~