哈夫曼树的算法
‘壹’ 哈夫曼树的空指针域怎么计算
哈夫曼树只有2度节点与0度节点，所以只有0度节点（即叶子）又空指针域，且叶子节点数的两倍。假设他有N个节点，n个叶子，m个2度节点，则有N=2n-1，n=m-1；所以只要知道任意一个量都能计算出哈夫曼树的空指针域，即2n。
50个叶子结点，51个空指针。因为是二叉链表，就是孩子兄弟表示法，不是一般的二叉树那样画，要转化一下。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码。
(1)哈夫曼树的算法扩展阅读：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
‘贰’ 哈夫曼树算法
题目的阐述：以N进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入0，1，2，．．．，N－1构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如：N＝3英文原串为ABBCBADDACE其对应的一种编码方式为A：00B：01C：020D：021E：022原串对译后的编码为000101020010002102100020022其码长为27若输入编码串0102002200则对应的英文原串为BCEA 分析： 假设英文原串中的字符存放于字符集S中，‖S‖＝X，每个字符在字串中出现的概率为W［i］，L［i］为字符i的编码长．依题意得，对S集合中的不同字符进行N进制编码后要求1）新字串的码长最短WPL＝∑W［i］＊L［i］
（i∈1．．X）使得在WPL是所有编码方式中的最小值2）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．N为此哈夫曼树的分叉数，S字符集里的元素即为此N叉哈夫曼树的叶子，概率W［i］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长L［i］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此N叉哈夫曼树呢？我们首先以N＝2为例：S＝｛A，B，C，D｝W＝［3，1，2，1］首先从W中选出两个最小权，1，1，将其删去，并以2（即1＋1）替代W＝［3，2，2］；再从新的W中取出两个最小权，2，2，将其删去，并以4（即2＋2）替代W＝［3，4］；依此类推，直到W中只一个值时合并结束，此时W＝［7］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： m0åæ1mmA0åæ1mmC0åæ1mmBD MIN－WPL＝3＊1＋1＊3＋2＊2＋1＊3＝13 从某一根结点出发走向其左子树标记为0，走向其右子树标记为1，则可以得到以下编码A，B，C，D对应的编码为A：0B：110C：10D：111
N＝3时又是怎样一种情况呢？设S＝｛A，B，C，D，E｝W＝［7，4，2，5，3｝则按权重排序可得S＝｛D，B，E，C，A｝W＝［7，5，4，3，2］那么此哈夫曼树的树形应为怎样呢？是以下的左图，还是右图，或是两者均不是mmåâæåæmmllmåæåæCAåælllllmADBEDåæ
lmBåællEC 显然，要带权路径长WPL最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满N叉树是最合理的，于是我们尽量使树每一层都为N个分枝．对于这道题的情况，我们具体来分析．按照哈夫曼树的思想，首先从W中取出权最小的三个值，即2，3，4，并以9（2＋3＋4）来代替，得到新的W＝［9，7，5］；再将这三个值合并成9＋7＋5＝21这个结点．于是得到三叉哈夫曼树如下：måâællmDBåâælllECAWPL＝1＊7＋1＊5＋2＊2＋2＊3＋2＊4＝30以0．．N－1依次标记每个根结点的N个分枝，则可以得到每个字符相对应的编码：A：22B：1C：21D：0E：20我们发现对于这种情况恰巧每层均为N个分枝，但事实上并非所有的N叉哈夫曼树都可得到每层N个分枝．例于当N＝3，‖S‖＝6时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？最简单的处理方式就是添加若干出现概率为0的空字符填补在N叉树的最下一层，这些权为0的虚结点并无实际意义但却非常方全便于这棵N叉树的建立．空字符的添加个数add的计算如下：Y＝‖S‖mod（n－1）add＝0（Y＝1）add＝1（Y＝0）add＝N－Y（Y＞1） 虚结点的加入使得权重最小的N－add个字符构成了距根结点最远的分枝，使其它字符构成的N叉树保持了丰满的N叉结构．例：N＝3S＝｛A，B，C，D，E，F｝W＝［1，2，3，4，5，6｝则y：＝6mod（3－1）＝0add＝1于是构成N叉树如下：为虚结点¡åâællmFEåâællmDCåâæBAWPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33对应编码为：A：221B：220C：21D：20E：1F：0
‘叁’ 什么是哈夫曼算法
有一种树形结构叫哈夫曼树，用哈夫曼树的方法解编程题的算法就叫哈夫曼算法，其实也没有哈夫曼算法这个专有名词了拉，你这么问我就这么跟你讲把。它产生的代码是
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // save the information of the symbolizes;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1)
return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;++i)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
{
if((*HT)[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
} // end of else if
} // end of if
} // end of for
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
return;
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
‘肆’ 哈夫曼树算法
题目的阐述：以Ｎ进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入０，１，２，．．．，Ｎ－１构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如：Ｎ＝３英文原串为ＡＢＢＣＢＡＤＤＡＣＥ其对应的一种编码方式为Ａ：００Ｂ：０１Ｃ：０２０Ｄ：０２１Ｅ：０２２原串对译后的编码为０００１０１０２００１０００２１０２１０００２００２２其码长为２７若输入编码串０１０２００２２００则对应的英文原串为ＢＣＥＡ 分析： 假设英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝Ｘ，每个字符在字串中出现的概率为Ｗ［ｉ］，Ｌ［ｉ］为字符ｉ的编码长．依题意得，对Ｓ集合中的不同字符进行Ｎ进制编码后要求１）新字串的码长最短ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ （ｉ∈１．．Ｘ）使得在ＷＰＬ是所有编码方式中的最小值２）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．Ｎ为此哈夫曼树的分叉数，Ｓ字符集里的元素即为此Ｎ叉哈夫曼树的叶子，概率Ｗ［ｉ］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长Ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此Ｎ叉哈夫曼树呢？我们首先以Ｎ＝２为例：Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ｝Ｗ＝［３，１，２，１］首先从Ｗ中选出两个最小权，１，１，将其删去，并以２（即１＋１）替代Ｗ＝［３，２，２］；再从新的Ｗ中取出两个最小权，２，２，将其删去，并以４（即２＋２）替代Ｗ＝［３，４］；依此类推，直到Ｗ中只一个值时合并结束，此时Ｗ＝［７］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： m０�0�2�0�3１mmＡ０�0�2�0�3１mmＣ０�0�2�0�3１mmＢＤ ＭＩＮ－ＷＰＬ＝３＊１＋１＊３＋２＊２＋１＊３＝１３ 从某一根结点出发走向其左子树标记为０，走向其右子树标记为１，则可以得到以下编码Ａ，Ｂ，Ｃ，Ｄ对应的编码为Ａ：０Ｂ：１１０Ｃ：１０Ｄ：１１１ Ｎ＝３时又是怎样一种情况呢？设Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝Ｗ＝［７，４，２，５，３｝则按权重排序可得Ｓ＝｛Ｄ，Ｂ，Ｅ，Ｃ，Ａ｝Ｗ＝［７，５，４，３，２］那么此哈夫曼树的树形应为怎样呢？是以下的左图，还是右图，或是两者均不是mm�0�2�0�9�0�3�0�2�0�3mmllm�0�2�0�3�0�2�0�3ＣＡ�0�2�0�3lllllmＡＤＢＥＤ�0�2�0�3 lmＢ�0�2�0�3llＥＣ 显然，要带权路径长ＷＰＬ最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满Ｎ叉树是最合理的，于是我们尽量使树每一层都为Ｎ个分枝．对于这道题的情况，我们具体来分析．按照哈夫曼树的思想，首先从Ｗ中取出权最小的三个值，即２，３，４，并以９（２＋３＋４）来代替，得到新的Ｗ＝［９，７，５］；再将这三个值合并成９＋７＋５＝２１这个结点．于是得到三叉哈夫曼树如下：m�0�2�0�9�0�3llmＤＢ�0�2�0�9�0�3lllＥＣＡＷＰＬ＝１＊７＋１＊５＋２＊２＋２＊３＋２＊４＝３０以０．．Ｎ－１依次标记每个根结点的Ｎ个分枝，则可以得到每个字符相对应的编码：Ａ：２２Ｂ：１Ｃ：２１Ｄ：０Ｅ：２０我们发现对于这种情况恰巧每层均为Ｎ个分枝，但事实上并非所有的Ｎ叉哈夫曼树都可得到每层Ｎ个分枝．例于当Ｎ＝３，‖Ｓ‖＝６时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？最简单的处理方式就是添加若干出现概率为０的空字符填补在Ｎ叉树的最下一层，这些权为０的虚结点并无实际意义但却非常方全便于这棵Ｎ叉树的建立．空字符的添加个数ａｄｄ的计算如下：Ｙ＝‖Ｓ‖ｍｏｄ（ｎ－１）ａｄｄ＝０（Ｙ＝１）ａｄｄ＝１（Ｙ＝０）ａｄｄ＝Ｎ－Ｙ（Ｙ＞１） 虚结点的加入使得权重最小的Ｎ－ａｄｄ个字符构成了距根结点最远的分枝，使其它字符构成的Ｎ叉树保持了丰满的Ｎ叉结构．例：Ｎ＝３Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝Ｗ＝［１，２，３，４，５，６｝则ｙ：＝６ｍｏｄ（３－１）＝０ａｄｄ＝１于是构成Ｎ叉树如下：�0�2为虚结点�0�3�0�2�0�9�0�3llmＦＥ�0�2�0�9�0�3llmＤＣ�0�2�0�9�0�3ＢＡ�0�2ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３对应编码为：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０
‘伍’ 哈夫曼树译码的算法思路，语言描述即可
你讲的是实现时的语言注释，还是他的实现过程
‘陆’ 哈夫曼树&带权路径计算
——即最短带权路径二叉树，即最优二叉树。将树的节点值升序排序，由叶至根构建二叉树，每次选两个最小的节点连接，加法得到其父节点值。最终根节点权为0，向叶子节点依次递增1。
eg：w={1,4,9,16,25,36,49,64,81,100}
最终哈夫曼树：
最终带权路径长度：
WPL=2*100+2*81+3*64+3*36+3*49+4*25+5*16+6*9+7*1+7*4=1078
‘柒’ 哈夫曼树的构造算法
/*-------------------------------------------------------------------------
*Name:哈夫曼编码源代码。
*Date:2011.04.16
*Author:JeffreyHill+Jezze(解码部分)
*在Win-TC下测试通过
*实现过程：着先通过HuffmanTree()函数构造哈夫曼树，然后在主函数main()中
*自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
*父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1
typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*编码结构体*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*结点结构体*/
/*构造一颗哈夫曼树*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//实际值，可根据情况替换为字母
}/*endfor*/
/*输入n个叶子结点的权值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d: ",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/
/*循环构造Huffman树*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*设置找到的两个子结点x1、x2的父结点信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
printf("x1.weightandx2.weightinround%d:%d,%d ",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用于测试*/
printf(" ");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d ",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
}/*endHuffmanTree*/
//解码
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
intmain(void)
{
HNodeTypeHuffNode[MAXNODE];/*定义一个结点结构体数组*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn: ");
scanf("%d",&n);
HuffmanTree(HuffNode,n);
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父结点存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求编码的低一位*/
c=p;
p=HuffNode[c].parent;/*设置下一循环条件*/
}/*endwhile*/
/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/
/*输出已保存好的所有存在编码的哈夫曼编码*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);
printf(" ");
}
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf(" ");
}*/
printf("Decoding?PleaseEntercode: ");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}
http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html
‘捌’ 请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。
1. 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
2. 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在F中删除这两棵树，并将新的二叉树加入F中。
4. 重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树
帮你贴过来了，网络
这东西实际用法是可以减少树的访问次数，因为他把频率高的点放在比较靠近根节点的地方，频率低的在下面，这样访问速度快。举个例子，比如四个点，他们的使用频率分别是1,2,3,4，然后构成的树就是
4
0 3
0 2
0 1
补：打不出树形结构...