从周五开始学习霍夫曼树，一直到今天终于完成，期间遇到了各类各样的棘手的问题，经过一遍遍在纸上分析每一步的具体状态得以解决。如今对学习霍夫曼树的过程加以记录web
首先介绍霍夫曼树数组
霍夫曼树(Huffman Tree)，又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,…,wn}，若是构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,…,wn}，则所构造出的带权路径长度最小的二叉树就被称为赫夫曼树。svg
这里补充下树的带权路径长度的概念。树的带权路径长度指树中全部叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，若是在一棵二叉树中共有n个叶子节点，用Wi表示第i个叶子节点的权值，Li表示第i个也叶子节点到根节点的路径长度，则该二叉树的带权路径长度 WPL=W1*L1 + W2*L2 + … Wn*Ln。函数
根据节点的个数以及权值的不一样，赫夫曼树的形状也各不相同，赫夫曼树具备以下特性：学习
对于同一组权值，所能获得的霍夫曼树不必定是惟一的。
赫夫曼树的左右子树能够互换，由于这并不影响树的带权路径长度。
带权值的节点都是叶子节点，不带权值的节点都是某棵子二叉树的根节点。
权值越大的节点越靠近赫夫曼树的根节点，权值越小的节点越远离赫夫曼树的根节点。
赫夫曼树中只有叶子节点和度为2的节点，没有度为1的节点。
一棵有n个叶子节点的赫夫曼树共有2n-1个节点。ui
赫夫曼树的构建步骤以下：
一、将给定的n个权值看作n棵只有根节点(无左右孩子)的二叉树，组成一个集合HT，每棵树的权值为该节点的权值。
二、从集合HT中选出2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这2棵二叉树的权值之和。
三、将步骤2中选出的2棵二叉树从集合HT中删去，同时将步骤2中新获得的二叉树加入到集合HT中。
四、重复步骤2和步骤3，直到集合HT中只含一棵树，这棵树即是赫夫曼树。
编码
假如给定以下5个权值：
则按照以上步骤，能够构造出以下面左图所示的赫夫曼树，固然也可能构造出以下面右图所示的赫夫曼树，这并非惟一的。
Huffman编码
赫夫曼树的应用十分普遍，好比众所周知的在通讯电文中的应用。在等传送电文时，咱们但愿电文的总长尽量短，所以能够对每一个字符设计长度不等的编码，让电文中出现较多的字符采用尽量短的编码。为了保证在译码时不出现歧义，咱们能够采起以下图所示的编码方式：spa
即左分支编码为字符0，右分支编码为字符1，将从根节点到叶子节点的路径上分支字符组成的字符串做为叶子节点字符的编码，这即是赫夫曼编码。咱们根据上面左图能够获得各叶子节点的赫夫曼编码以下：
权值为5的也本身节点的赫夫曼编码为：11
权值为4的也本身节点的赫夫曼编码为：10
权值为3的也本身节点的赫夫曼编码为：00
权值为2的也本身节点的赫夫曼编码为：011
权值为1的也本身节点的赫夫曼编码为：
而对于上面右图，则能够获得各叶子节点的赫夫曼编码以下：
权值为5的也本身节点的赫夫曼编码为：00
权值为4的也本身节点的赫夫曼编码为：01
权值为3的也本身节点的赫夫曼编码为：10
权值为2的也本身节点的赫夫曼编码为：110
权值为1的也本身节点的赫夫曼编码为：111
下面给出C语言实现设计
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*定义霍夫曼树节点*/
typedef struct HTNode{
int parent;/*记录双亲*/
int Lchild;/*左右子树*/
int Rchild;
int Weight;/*记录权重*/
}HTNode;
typedef struct HTNode * HuffmanTree;
typedef char ** HuffmanCode;
/*在前k棵树种找到权重最小的树*/
int Min(HuffmanTree HT,int k){
int i=0,min_weight=0,min=0;
/*找出第一个双亲存在的节点，将其权值赋值给min_weight*/
/*注意此处不能直接将HT[0].weight赋给min_weight，缘由是若是HT[0].weight最小，那么在第一次构造二叉树时就会被选走，然后续的每一轮选择最小权值构造二叉树的比较
仍是先用HT[0].weight的值来进行判断，这样又会再次将其选走，从而产生逻辑上的错误。*/
while(HT[i].parent!=-1)
i++;
min_weight=HT[i].Weight;
min=i;
for(i;i
if(HT[i].Weight
min_weight=HT[i].Weight;
min=i;
}
}
/*找到最小权重的树，将其双亲置为1*/
/*！！！！！注意这的HT的下标！！！！！一夜才找出这个小问题，别写成HT[i]!!!!!!*/
HT[min].parent=1;
return min;
}
/*从前k棵树中选出权重最小的两棵树,将其序号赋给min1和min2*/
Status SelectMin(HuffmanTree HT,int k,int &min1,int &min2){
min1=Min(HT,k);
min2=Min(HT,k);
return OK;
}
/*建立一课霍夫曼树，-1表示不存在*/
/*wet为一个记录权重的数组，类型为int*/
HuffmanTree CreateHuffmanTree(HuffmanTree HT,int *wet,int n){
int i=0;
int total=2*n-1;/*有n个数据须要编码，即有n个叶子节点，也就有n-1个度为2的节点，总节点数为n+n-1=2*n-1*/
/*初始状态下，前n个节点的双亲，左右子树应该均为-1，权重为对应的权重*/
/*用HT的前n个份量存储n棵树(由n个待编码的数据组成)的森林*/
/*申请total个int组成的动态数组*/
HT=(HuffmanTree)malloc(total*sizeof(HTNode));
if(!HT)
return ERROR;
for(i=0;i
HT[i].Lchild=-1;
HT[i].parent=-1;
HT[i].Rchild=-1;
HT[i].Weight=*wet;
wet++;
}
/*对n到total的份量进行初始化*/
for(i;i
HT[i].Lchild=-1;
HT[i].Rchild=-1;
HT[i].parent=-1;
HT[i].Weight=0;
}
/*用HT的后n-1个份量存储霍夫曼树*/
/*调用函数SelectMin找出森林中两棵权重最小的树*/
int min1=0,min2=0;
for(i=n;i
SelectMin(HT,i,min1,min2);
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].Lchild=min1;
HT[i].Rchild=min2;
HT[i].Weight=HT[min1].Weight+HT[min2].Weight;
}
return HT;
}
/*从叶子节点开始逆向进行霍夫曼编码*/
/*HC用来储存霍夫曼编码值*/
Status HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){
/*HC自己是一个char类型数组的指针,其指向n个char类型的地址，因此给HC分配内存应该写成下面那样*/
HC=(HuffmanCode)malloc(n*sizeof(char *));
if(!HC)
return ERROR;
/*声明一个动态数组code，用来临时存储霍夫曼编码,数组含有n-1个霍夫曼码，加上一个'\0'终止符正好是n个元素，因此分配内存时*/
char *code;
code=(char *)malloc(n*sizeof(char));
if(!code)
return ERROR;
code[n-1]='\0';/*让最后一个元素为终止符*/
int i=0;
for(i=0;i
int current=i;
int father=HT[i].parent;
int start=n-1;
while(father!=-1){
if(current==HT[father].Lchild)
code[--start]='0';
else
code[--start]='1';
current=father;
father=HT[father].parent;
}
/*HC[i]用于最终存储霍夫曼码，是char类型的数组，有n个char类型的数据*/
HC[i]=(char *)malloc((n-start)*sizeof(char));
if(!HC[i])
return ERROR;
/*从临时空间中复制到HC[i]中*/
strcpy(HC[i],code+start);
}
/*释放临时存储空间*/
free(code);
code=NULL;
return OK;
}
int main(void){
int amount=0,i=0;
int *wet=(int *)malloc(amount*sizeof(int));
printf("请输入要编码的字符个数(个数为整型且>1)");
scanf("%d",&amount);
while(amount<=1){
printf("字符个数必须大于1\n");
scanf("%d",&amount);
}
printf("请输入要编码的字符的权值");
for(i=0;i
scanf("%d",wet+i);
}
HuffmanTree HT;
HT=CreateHuffmanTree(HT,wet,amount);
HuffmanCode HC;
HuffmanCoding(HT,HC,amount);
for(i=0;i
puts(HC[i]);
}
free(wet);
return OK;
}
-05-09更新:
今日在复习霍夫曼树的过程当中，发现本身忽视了一些细节问题，形成了一些错误，下面加以记录并反思
问题一:出如今函数Min中
int Min(HuffmanTree HT,int k){
int min=0,min_weight=0,i=0;
/*注意此处是先寻找双亲不存在的节点再赋值，给min_weight赋值应该在循环之外*/
while(HT[i].parent!=-1)
i++;
min_weight=HT[i].weight;
min=i;
for(i;i
if(HT[i].weight
min_weight=HT[i].weight;
min=i;
}
}
/*赋值以后切记要将其双亲赋值为1，不然会出现错误*/
HT[min].parent=1;
return min;
}
问题二:出如今CreateHuffmanTree函数中
HuffmanTree CreateHuffmanTree(HuffmanTree HT,int * wet,int amount){
int i=0,min_weight=0,min=0;
int total=2*amount-1;
/*注意此处分配内存时，sizeof()中应该是HTNode！！要对HT的本质进行理解，HT是一棵树！*/
HT=(HuffmanTree)malloc(total*sizeof(HTNode));
if(!HT)
return ERROR;
for(i=0;i
HT[i].Lchild=-1;
HT[i].parent=-1;
HT[i].Rchild=-1;
HT[i].weight=*wet;
wet++;
}
for(i;i
HT[i].Lchild=-1;
HT[i].Rchild=-1;
HT[i].parent=-1;
HT[i].weight=0;
}
int min1=0,min2=0;
/*注意此处i的初始值，要对这个过程加以理解，霍夫曼树是用amount以后的份量来存储的，故不能写i=0*/
for(i=amount;i
SelectMin(HT,min1,min2,i);
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].Lchild=min1;
HT[i].Rchild=min2;
HT[i].weight=HT[min1].weight+HT[min2].weight;/*注意新生成的节点的权值为选出的两个最小的节点的权值之和*/
}
return HT;
}
这个问题主要是对创建霍夫曼树的过程理解不够透彻，致使在为HT分配内存时写错大小，和循环过程当中将i的初始值误写为0，从此应当注意。
问题三:出如今HuffmanCoding函数中
Status HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int amount){
int i=0;
/*要先给HC分配内存。HC存储了amount个指向霍夫曼码的指针*/
HC=(HuffmanCode)malloc(amount*sizeof(char *));
if(!HC)
return ERROR;
char * code;
code=(char *)malloc(amount*sizeof(char));
if(!code)
return ERROR;
code[amount-1]='\0';
for(i=0;i
int current=i;
int start=amount-1;
int father=HT[i].parent;
while(father!=-1){
if(current==HT[father].Lchild)
code[--start]='0';
else
code[--start]='1';
current=father;
father=HT[father].parent;
}
/*HC[i]是HC中若干个存储单元之一，存储着一个具体字符的霍夫曼码，因此分配内存空间时sizeof()中为char*/
HC[i]=(char *)malloc((amount-start)*sizeof(char));
if(!HC[i])
return ERROR;
strcpy(HC[i],code+start);
}
free(code);
code=NULL;
}
对HC的用途理解不够到位，再次强调，HC是一个存储了若干个指向霍夫曼码的指针的数组，HC[i]则用于存储具体字符的霍夫曼码
问题四:反复出如今主函数之中，必须加以记录，认真检讨
int main(void){
HuffmanTree HT;
int amount=0;
printf("请输入须要编码的字符个数");
scanf("%d",&amount);
int i=0;
int * wet=(int *)malloc(amount*sizeof(int));
printf("请输入每一个字符的权重");
for(i=0;i
scanf("%d",wet+i);
}
/*此处忘记写HT=，致使未能成功创建霍夫曼树，因为这里要改变函数形参的值，通常状况考虑传入指针变量，但这个函数若是写成指针又太复杂，
很容易出错，故这里使用return把创建好的霍夫曼树直接返回，会方便许多，可是切记要把返回值赋给HT！！！*/
HT=CreateHuffmanTree(HT,wet,amount);
HuffmanCode HC;
HuffmanCoding(HT,HC,amount);
for(i=0;i
puts(HC[i]);
}
free(wet);
}
