什么是哈夫曼树呢？

什么是哈夫曼树呢~

权值就是定义的路径上面的值。可以这样理解为结点间的距离。通常指字符对应的二进制编码出现的概率。

至于哈夫曼树中的权值可以理解为：权值大表明出现概率大！

哈夫曼树（霍夫曼树）又称为最优树。
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
多叉哈夫曼树
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。于是对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式,然后再按照哈夫曼树的方法进行构造即可。

夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。

哈夫曼编码哈夫曼树应用哈夫曼编码应用广泛JPEG应用哈夫曼编码
首先介绍哈夫曼树哈夫曼树称优二叉树种带权路径度短二叉树所谓树带权路径度树所叶结点权值乘其根结点路径度(若根结点0层叶结点根结点路径度叶结点层数)树带权路径度记WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)N权值Wi(i=1,2,...n)构棵N叶结点二叉树相应叶结点路径度Li(i=1,2,...n)证明哈夫曼树WPL
哈夫曼世纪五十代初提种编码根据字符现概率构造平均度短编码种变编码编码若各码字度严格按照码字所应符号现概率逆序排列则编码平均度(注:码字即符号经哈夫曼编码编码其度符号现概率同所说哈夫曼编码变编码)
、给定n权值{W1,W2,W3,...,Wi,...,Wn}构n棵二叉树初始集合F={T1,T2,T3,...,Ti,...,Tn}其每棵二叉树Ti权值Wi根结点左右树均空(便计算机实现算般要求Ti权值Wi升序排列)
二、F选取两棵根结点权值树作新构造二叉树左右树新二叉树根结点权值其左右树根结点权值
三、F删除两棵树并棵新二叉树同升序排列加入集合F
四、重复二三两步直集合F棵二叉树止
用C语言实现述算用静态二叉树或态二叉树若用态二叉树用数据结构:
struct
tree{
float
weight;
/*权值*/
union{
char
leaf;
/*叶结点信息字符*/
struct
tree
*left;
/*树左结点*/
};
struct
tree
*right;
/*树右结点*/
};
struct
forest{
/*F集合链表形式表示*/
struct
tree
*ti;
/*
F树*/
struct
forest
*next;
/*
结点*/
};
例:若字母ABZC现概率:0.75,0.54,0.28,0.43;则相应权值:75542843
构造哈夫曼树根据哈夫曼树进行编码例:面字符根据其现概率作权值构造棵哈夫曼树经哈夫曼编码应码值要使用同棵哈夫曼树编码原原组字符显哈夫曼编码前缀编码即任字符编码都另字符编码前缀否则编码能进行翻译例:a,b,c,d编码:01010111于编码串:1010翻译bb或cab编码c编码前缀刚才进行哈夫曼编码规则根结点叶结点(包含原信息)路径向左孩前进编码0向右孩前进编码1反规定
种编码静态哈夫曼编码需要编码数据进行两遍扫描:第遍统计原数据各字符现频率利用频率值创建哈夫曼树并必须树信息保存起即字符0-255(2^8=256)频率值2-4BYTES度顺序存储起(用4Bytes度存储频率值频率值表示范围0--2^32-1已足够表示文件字符现频率)便解压创建同哈夫曼树进行解压;第二遍则根据第遍扫描哈夫曼树进行编码并编码码字存储起
静态哈夫曼编码些缺点:、于短文件进行编码意义光4BYTES度存储哈夫曼树信息需1024Bytes存储空间;二、进行哈夫曼编码存储编码信息若用与通讯网络引起较延;三、较文件进行编码频繁磁盘读写访问降低数据编码速度
提种态哈夫曼编码态哈夫曼编码使用棵态变化哈夫曼树第t+1字符编码根据原始数据前t字符哈夫曼树进行编码解码使用相同初始哈夫曼树每处理完字符编码解码使用相同修改哈夫曼树所没必要解码保存哈夫曼树信息编码解码字符所需间与该字符编码度比所态哈夫曼编码实进行态哈夫曼编码比静态哈夫曼编码复杂兴趣读者参考关数据结构与算书籍
前面提JPEG用哈夫曼编码并说JPEG用哈夫曼编码幅图片经步骤列数值些数值进行哈夫曼编码便存储或传输哈夫曼编码比较易懂家根据编码自编写哈夫曼编码解码程序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>a
#include<graphics.h>
#define MAXVALUE 200 /*权值的最大值*/
#define MAXBIT 30 /*最大的编码位数*/
#define MAXNODE 30 /*初始的最大的结点数*/
struct haffnode
{char data;
int weight;
int flag;
int parent; /*双亲结点的下标*/
int leftchild; /*左孩子下标*/
int rightchild; /*右孩子下标*/
};
struct haffcode
{int bit[MAXNODE];
int start; /*编码的起始下标*/
char data;
int weight; /*字符权值*/
};

/*函数说明*/
/************************************************************************/
void pprintf(struct haffcode haffcode[],int n);
/*输出函数*/
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[]);
/*建立哈夫曼树*/
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[]);
/*求哈夫曼编码*/
void test(struct haffcode haffcode[],int n);
/*测试函数*/
void end();
/*结束界面函数*/
/************************************************************************/

void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立叶结点个数为n，权值数组为weight[]的哈夫曼树*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼树hafftree[]初始化，n个叶结点共有2n-1个结点*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*叶结点*/
}
else {hafftree[i].weight=0; /*非叶结点*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化没有双亲结点*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*构造哈夫曼树n-1个非叶结点*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;

}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n个结点的哈夫曼树hafftree[]构成的哈夫曼编码haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n个结点的哈夫曼编码*/
{cd->start=MAXBIT-1; /*不等长编码的最后一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得编码对应值的字符*/
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{if(hafftree[parent].leftchild==child)
cd->bit[cd->start]=0; /*左孩子编码为0*/
else
cd->bit[cd->start]=1; /*右孩子编码为1*/
cd->start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd->start+1;j<MAXBIT;j++) /*保存每个叶结点的编码和等长编码的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}
void pprintf(struct haffcode myhaffcode[],int n)
{int i,j,count=0;
clrscr();
for(i=0;i<n;i++)
{textcolor(YELLOW);
cprintf("字符=%c",myhaffcode[i].data);
printf(" ");
textcolor(YELLOW);
cprintf("weight=%3d",myhaffcode[i].weight);
printf(" ");
textcolor(YELLOW);
cprintf("haffcode=");
for(j=myhaffcode[i].start+1;j<MAXBIT;j++)
cprintf("%d",myhaffcode[i].bit[j]);
printf("\n");
count++;
if(count==21)
getch();

}
}
void test(struct haffcode haffcode[],int n)
{int i,j,k,s;
char sstring[MAXNODE];
struct haffcode newhaffcode[MAXNODE];
j=0;
clrscr();
textcolor(YELLOW);
cprintf("请输入哈夫曼编码测试数据，在此建议为'this programme is my favorite'");
printf("\n");
cprintf("注意小写,空格由大写字母T代替，并且字符数小于27.\n");
scanf("%s",sstring);
if(strlen(sstring)>=MAXNODE)
{printf("you input the data number >=MAXNODE.");
exit(1);
}
for(i=0;i<strlen(sstring);i++)
{
for(j=0;j<MAXBIT;j++)
if(sstring[i]==haffcode[j].data)
{
k=j;
break;
}
if(k<0||k>MAXNODE-1)
{printf("在系统中找不到与第个%d字符相匹配的编码\n",i+1);
continue;
}
newhaffcode[i].start=haffcode[k].start;
newhaffcode[i].weight=haffcode[k].weight;
newhaffcode[i].data=haffcode[k].data;
for(s=haffcode[k].start+1;s<MAXBIT;s++)
newhaffcode[i].bit[s]=haffcode[k].bit[s];
}

pprintf(newhaffcode,strlen(sstring));
}
void end()
{int driver,mode;
driver=VGA;
mode=VGAHI;
initgraph(&driver,&mode," ");
setlinestyle(0,0,2);
setfillstyle(1,9);
bar(120,60,520,80);
setfillstyle(1,9);
bar(90,100,550,350);
moveto(121,65);
settextstyle(5,0,6);
setcolor(7);
outtext("This programme is designed by Dou Zheren");
settextstyle(3,0,3);
setcolor(7);
moveto(150,200);
outtext("thank you use this programme.");
moveto(100,300);
settextstyle(3,0,2);
setcolor(7);
outtext("please press anykey to end this programme.");
}
void main()
{
int i,j,n=27;
int driver=VGA,mode=VGAHI;
char ch;
int weight[27]={186,64,13,22,32,103,21,15,47,
57,1,5,32,20,57,63,15,1,48,
51,80,23,8,18,1,16,1};
char data[28]={'T','a','b','c','d','e','f','g','h',
'i','j','k','l','m','n','o','p','q',
'r','s','t','u','v','w','x','y','z'};
struct haffnode newhaffnode[2*MAXNODE-1];
struct haffcode newcode[MAXNODE];
struct haffnode *myhafftree=newhaffnode;
struct haffcode *myhaffcode=newcode;
if(n>MAXNODE)
{printf("you input the haffnode > MAXNODE,so you input the data is wrong");
printf("\n");
exit(1);
}
clrscr();
textcolor(YELLOW);
cprintf("WELCOME!这是一个求哈夫曼编码的问题");
printf("\n");
cprintf("即对所有的字母进行编码后，在根据用户的需要，对用户的要求进行编码。");
printf("\n");
cprintf("注意：本程序只支持小写字母，空格用大写字母T代替! ");
printf("\n");
getch();
textcolor(YELLOW);
cprintf("Ready?Enter,if you want to begin!\n");
printf("\n");
getch();
cprintf("Now，开始演示哈夫曼编码.");
getch();
haffmantree(weight,n,myhafftree,data);
haffmancode(myhafftree,n,myhaffcode);
pprintf(myhaffcode,n);
clrscr();
printf("若执行自定义编译，请输入y继续。否则程序将结束.");
if((ch=getch())=='y'||ch=='Y')
test(myhaffcode,n);
getch();
clrscr();
end();
getch();
exit(1);
}

---

息烽县19249407575： 哈夫曼树(计算机术语) - 搜狗百科？
刁文业立：[答案] 哈夫曼树也称最优二叉树.哈夫曼树是完全二叉树,只有度为0和度为2的结点.给定n个值,可以构造出多棵具有n个叶节点且权值分别为这n个给定值的二叉树,其中加权通路长最小的那棵就是哈夫曼树.也就是说权值大的更靠近根节点.

息烽县19249407575： 什么是哈夫曼树呢? - ？
刁文业立： 夫曼树是带权路径长度最小的二叉树,用途是平均查找信息的代价最小. 普通二叉树的用途也普通,比较通用,就是信息存储和查找. 普通二叉树可能有的只有一个子节点,而哈夫曼树一定有两个.

息烽县19249407575： 到底什么是哈夫曼树啊,求例子 - ？
刁文业立： 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...

息烽县19249407575： 哈夫曼树是什么?求解 - ？
刁文业立： 哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码.首先介绍什么是哈夫曼树.哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树.所谓树的带权路径长度,就是树中所有的叶结点的权值乘上...

息烽县19249407575： 哈夫曼树的定义是:带权路径长度最小的二叉树.我先请问:为何它是带全路径长度最小的二叉树?最小是哈夫曼树的定义是:带权路径长度最小的二叉树.我... - ？
刁文业立：[答案] 只有带权路径长度最小的二叉树,才是哈夫曼树.当然是可以证明带权路径长度最小

息烽县19249407575： 什么是带权最优二元树 - ？
刁文业立：[答案] 一棵带权二元树的代价就是树中所有根结点权之和.代价最小的带权二元树称为最优二元树.问题转化为求最优带权二元树. 那么,什么是最优带权二元树呢? 最优二叉树,又称哈夫曼树,是一类带权路径长度最短的树,有着广泛的应用. 我们首先给出...

息烽县19249407575： 哈夫曼树是二叉树吗? - ？
刁文业立： 哈夫曼树不一定是二叉树,也有可能有度为m的哈弗曼树,度为m的哈弗曼树只有度为m的结点和度为0的结点.

息烽县19249407575： 最优二叉树算法的基本概念 - ？
刁文业立： 最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.那么什么是二叉树的带权路径长度呢?在前面我们介绍过路径和结点的路径长度的概念,而二叉树的路径长度则是...

息烽县19249407575： 数据结构题 名词解释 树 哈夫曼树 数据 栈 数据元素 队列 排序 图的遍历 - ？
刁文业立： 树:逻辑结构的一种.n个节点的有限集,数据间存在一对多的关系.在任意一颗非空树中1.有且仅有一个根节点2.当n>1时,其余节点可分为m个互不相交的有限集,其中每个集合本身又是一棵树. 哈夫曼树:亦称最优二叉树,是带权路径最短的二叉树 数据:对客观事物的描述,在计算机中可以输入并被识别的有效字符 栈:操作受限的线性表,具有后进先出的特点 数据元素:数据的基本单位,计算机中通常做整体处理 队列:和栈一样是操作受限制的线性结构的一种,先进先出 排序:顾名思义,是将一个无序记录按关键字序列有序排列.分为内部排序和外部排序 图的遍历:访问图中的每个节点