常见哈夫曼树算法

1. 请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。

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
补：打不出树形结构...

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

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åâæBA­WPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33对应编码为：A：221B：220C：21D：20E：1F：0

4. 请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。

这个讲的相当清楚。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为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; /* 下一个结点*/
};
例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。 静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

5. 哈夫曼树译码的算法思路，语言描述即可

你讲的是实现时的语言注释，还是他的实现过程

6. 数据结构求赫夫曼树的算法

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree;

typedef char **huffmancode;

int min1(huffmantree t,int i)
{
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值(即unsigned int类型的最大值)
for(j = 1; j <= i; j++)
if(t[j].weight < k && t[j].parent == 0)
k = t[j].weight,flag = j;
t[flag].parent=1;
return flag;
}

// s1为最小的两个值中序号小的那个
void select(huffmantree t,int i,int *s1,int *s2)
{
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1 > *s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void huffmancoding(huffmantree *HT,huffmancode *HC,int *w,int n)
{
int m,i,s1,s2,start;
unsigned c,f;
huffmantree p;
char *cd;

if(n<=1)
return;
m=2*n-1;
*HT=(huffmantree)malloc((m+1)*sizeof(htnode));
for(p=*HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i)
{
select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
*HC=(huffmancode)malloc((n+1)*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]);
}
free(cd);
}

int main()
{
huffmantree HT;
huffmancode HC;
int *w,n,i;

printf("请输入权值的个数(>1)：\n");
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整型)：\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
huffmancoding(&HT,&HC,w,n);
for(i=1;i<=n;i++)
puts(HC[i]);
return 0;
}

不知道是不是你要的

7. 哈夫曼树算法

题目的阐述：以Ｎ进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入０，１，２，．．．，Ｎ－１构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如：Ｎ＝３英文原串为ＡＢＢＣＢＡＤＤＡＣＥ其对应的一种编码方式为Ａ：００Ｂ：０１Ｃ：０２０Ｄ：０２１Ｅ：０２２原串对译后的编码为０００１０１０２００１０００２１０２１０００２００２２其码长为２７若输入编码串０１０２００２２００则对应的英文原串为ＢＣＥＡ 分析： 假设英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝Ｘ，每个字符在字串中出现的概率为Ｗ［ｉ］，Ｌ［ｉ］为字符ｉ的编码长．依题意得，对Ｓ集合中的不同字符进行Ｎ进制编码后要求１）新字串的码长最短ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ （ｉ∈１．．Ｘ）使得在ＷＰＬ是所有编码方式中的最小值２）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．Ｎ为此哈夫曼树的分叉数，Ｓ字符集里的元素即为此Ｎ叉哈夫曼树的叶子，概率Ｗ［ｉ］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长Ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此Ｎ叉哈夫曼树呢？我们首先以Ｎ＝２为例：Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ｝Ｗ＝［３，１，２，１］首先从Ｗ中选出两个最小权，１，１，将其删去，并以２（即１＋１）替代Ｗ＝［３，２，２］；再从新的Ｗ中取出两个最小权，２，２，将其删去，并以４（即２＋２）替代Ｗ＝［３，４］；依此类推，直到Ｗ中只一个值时合并结束，此时Ｗ＝［７］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： 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ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３对应编码为：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０

8. 哈夫曼算法的概述

1.初始化： 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
2. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。
4. 判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树

9. 哈夫曼树的构造算法

/*-------------------------------------------------------------------------
*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