下面是用C语言实现的简单的哈夫曼编码实现，要实现编码，首先得创建哈夫曼树(也叫最优二叉树)。
哈夫曼树就是带权路径长度(WPL)最小的二叉树，而权路径长度(WPL)指的是出现频率*其到根节点的长度。最后使出现平率高的越靠近根节点。
哈夫曼编码的优点便是降低重复的码值，实现无损压缩。
#include <stdio.h> #include <stdlib.h> //结构体创建节点 typedef struct{ char word; int weight,left,right,parent; int *code; }HuffNode; //初始化森林(对节点与权值进行初始化) int n; void StartHuffTree(HuffNode * F){ int i,w; char ch; printf("请输入字符与权重(空格间隔，回车结束)：\n"); for(i=0;i<n;i++){ printf("第%d个节点:",i+1); scanf("%s",&ch); scanf("%d",&w); F[i].word=ch; F[i].weight=w; F[i].left=F[i].right=F[i].parent=-1; F[i].code=NULL; } printf("----------------------------------------------------\n"); } //创建哈夫曼树 (创建哈夫曼树，最优二叉树) void CreatHuffTree(HuffNode * F){ printf("创建哈弗曼树:\n"); int i,j,k1,k2; //循环n-1次创建树的双亲 for(i=0;i<n-1;i++){ //k1,k2找到可以作为子树的树 for(k1=0;k1<n+i&&F[k1].parent!=-1;k1++); for(k2=k1+1;k2<n+i&&F[k2].parent!=-1;k2++); //循环 整个森林，使得k1,k2为最小的次小的2颗树 for(j=k2;j<n+i;j++){ if(F[j].parent==-1){ if(F[j].weight<F[k1].weight){ k2=k1; k1=j; } else if(F[j].weight<F[k2].weight){ k2=j; } } } //在第n+i节点 上创建k1,k2的双亲 F[n+i].word='x'; F[n+i].weight=(F[k1]).weight+(F[k2]).weight; F[n+i].left=k1; F[n+i].right=k2; F[n+i].parent=-1; F[n+i].code=NULL; F[k1].parent=n+i; F[k2].parent=n+i; // printf("%d",F[n+i].parent); // getchar(); // } //判断创建的树是否正确 for(j=0;j<7;j++){ printf("L",F[j].word); printf("M",F[j].weight); printf("M",F[j].left); printf("M",F[j].right); printf("M\n",F[j].parent); } printf("-----------------------------------------------------\n"); } //对哈弗曼树进行编码 void CreatCode(HuffNode * F){ printf("哈弗曼树编码:............\n"); int i,pa,c; int *p; for(i=0;i<n;i++){ F[i].code=p=(int *)malloc(n*sizeof(int)); p[0]=0; c=i; while(F[c].parent!=-1){ pa=F[c].parent; if(F[pa].left==c){ p[++p[0]]=0; }else{ p[++p[0]]=1; } c=pa; } } } void PrintHuffTree(HuffNode * F){ printf("输出哈夫曼编码:\n"); for(int i=0;i<n;i++){ printf("L",F[i].word); printf(" "); for(int j=F[i].code[0];j>0;j--){ printf("%d",F[i].code[j]); } printf("\n"); } } int main(void) { printf("输入叶子节点个数："); scanf("%d",&n); //初始化 HuffNode * F=(HuffNode *)malloc((2*n-1)*sizeof(HuffNode)); StartHuffTree(F); //创建哈夫曼树 CreatHuffTree(F); //编码 CreatCode(F); //输出 PrintHuffTree(F); return 0; }