//* * * * * * * * * * * * * * * * * * * * * * * *//哈夫曼树的构造哈夫曼树,哈夫曼编码 *//* * * * * * * * * * * * * * * * * * * * * * * *#include 《dos.h》#include 《conio.h》#include 《stdio.h》#include 《stdlib.h》#include 《string.h》typedef struct{unsigned int weight; //结点权值 unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼树void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点void main(){HuffmanTree HT; //哈夫曼树HT HuffmanCode HC; //哈夫曼编码表HC int n,i; //n是哈夫曼树叶子结点数 unsigned int *w; //w存放叶子结点权值 char j=’y’; textbackground(3); //设定屏幕颜色 textcolor(15); clrscr(); //程序解说 printf(“本程序将演示构造哈夫曼树.\n“); printf(“首先输入叶子结点数目.\n例如:8\n“); printf(“然后输入每个叶子结点的权值.\n“); printf(“例如:5 29 7 8 14 23 3 11\n“); printf(“程序会构造一棵哈夫曼树并显示哈夫曼编码.\n“); printf(“ 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n“); printf(“ 23---00\n 3---0111\n 11---010\n“); while(j!=’N’&&j!=’n’) {printf(“请输入叶子结点数目:“); scanf(“%d“,&n); //输入叶子结点数 if(n《=1) {printf(“该数不合理!\n“);continue;} w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值 printf(“请输入各叶子结点的权值:\n“); for(i=0;i《n;i++) scanf(“%d“,&w); //输入各叶子结点权值 CreateHuffmanTree(HT,w,n); //生成哈夫曼树 HuffmanCoding(HT,HC,n); //进行哈夫曼编码 PrintHuffmanCode(HC,w,n); //显示哈夫曼编码 printf(“哈夫曼树构造完毕，还要继续吗?(Y/N)“); scanf(“ %c“,&j); }}void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n){//w存放n个结点的权值，将构造一棵哈夫曼树HT int i,m; int s1,s2; HuffmanTree p; if(n《=1) return; m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用 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-》weight=0; p-》parent=0; p-》lchild=0; p-》rchild=0; } for(i=n+1;i《=m;++i) //建哈夫曼树 {Select(HT,i-1,s1,s2); //从HT中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 HT.parent=i; //修改s1和s2结点的父指针parent HT.rchild=s2; //修改i结点的左右孩子指针 HT.weight; //修改权值 }}void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针向量 cd=(char *)malloc(n*sizeof(char)); //开辟一个求编码的工作空间 cd=’\0’; //编码结束符 for(i=1;i《=n;++i) //逐个地求哈夫曼编码 {start=n-1; //编码结束位置 for(c=i,f=HT.parent) //从叶子到根逆向求编码 if(HT=’0’; //若是左孩子编为’0’ else cd=’1’; //若是右孩子编为’1’ HC=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC); //将编码从cd复制到HC中 } free(cd); //释放工作空间}void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n){//显示有n个叶子结点的哈夫曼树的编码表 int i; printf(“HuffmanCode is :\n“); for(i=1;i《=n;i++) {printf(“ %3d---“,w); puts(HC); } printf(“\n“);}void Select(HuffmanTree HT,int t,int&s1,int&s2){//在HT中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2 int i,m,n; m=n=10000; for(i=1;i《=t;i++) {if(HT.weight《n)) if(m《n) {n=HT.weight;s2=i;} else {m=HT.weight;s1=i;} } if(s1》s2) //s1放较小的序号 {i=s1;s1=s2;s2=i;}}

#include《stdio.h》#include《stdlib.h》#include《string.h》#include 《ctype.h》#include《limits.h》int function1(char ch,char *s){ int i; for(i=0; s!=’\0’; i++) { if(ch==s)return 0; } return 1;}typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild;} HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表// algo6-1.cpp 求赫夫曼编码。实现算法6.12的程序int min(HuffmanTree t,int i){ // 函数void select()调用 int j,flag; unsigned int k=UINT_MAX; // 取k为不小于可能的值 for(j=1; j《=i; j++) if(t.parent==0) k=t.weight,flag=j; t.parent=1; return flag;}void select(HuffmanTree t,int i,int &s1,int &s2){ // s1为最小的两个值中序号小的那个 s1=min(t,i); s2=min(t,i); /* if(s1》s2) { j=s1; s1=s2; s2=j; }*/}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12{ // w存放n个字符的权值(均》0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC 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)); // 0号单元未用 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) // 建赫夫曼树 { // 在HT中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HT.parent=i; HT.rchild=s1; HT.lchild=s2; HT.weight; // printf(“HT.rchild:%d\n“,i,s2,i,s1); } // 从叶子到根逆向求每个字符的赫夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); // 分配n个字符编码的头指针向量(不用) cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间 cd=’\0’; // 编码结束符 for(i=1; i《=n; i++) { // 逐个字符求赫夫曼编码 start=n-1; // 编码结束符位置 for(c=i,f=HT.parent) // 从叶子到根逆向求编码 if(HT.lchild==c) cd=’1’; else cd=’0’; HC=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间 strcpy(HC); // 从cd复制编码(串)到HC } free(cd); // 释放工作空间}void swap1(int *a ,int *b){ int t; t=*a; *a=*b; *b=t;}void swap2(char *a,char *b){ char ch; ch=*a; *a=*b; *b=ch;}int main(void){ HuffmanTree HT; HuffmanCode HC; char *s1,*s2; int i,j=0,n,count,*m,t,flag=1; scanf(“%d“,&n); getchar(); s1=(char*)malloc((n+n)*sizeof(char)); s2=(char*)malloc(n*sizeof(char)); memset(s2,’\0’,n*sizeof(char)); gets(s1); count=strlen(s1); for(i=0; i《count; i++) { if(!isspace(*(s1+i))) { if(function1(*(s1+i),s2)) { *(s2+j)=*(s1+i); j++; } } else; } m=(int*)malloc(j*sizeof(int)); for(i=0; i《j; i++) *(m+i)=0; for(t=0; t《j; t++) { for(i=0; i《count; i++) { if(*(s2+t)==*(s1+i)) *(m+t)+=1; } } for(i=0;i《j;i++) while(flag) { flag = 0; for (t=0; t《j-1; t++) { if(*(m+t)《*(m+t+1)) { swap1(m+t,m+t+1); swap2(s2+t,s2+t+1); flag=1; } } } HuffmanCoding(HT,HC,m,j); for(i=1,t=0; i《=j; i++,t++) { printf(“%c %d %s\n“,*(s2+t),*(m+t),HC); } return 0;}

这是以前写的，可是我不想加注释了，Huffman编码其实原理很简单的，你自己好好学下吧，一句一句注释也太夸张了啊。#include《string.h》 #include《stdlib.h》 #include《stdio.h》int m,s1,s2;typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;typedef char ** HuffmanCode;void Select(HuffmanTree HT,int n) { int i,j; for(i=1;i《=n;i++) if(HT.parent==0) {s1=i; break; } for(j=i+1;j《=n;j++) if(HT.parent==0) { s2=j; break; } for(i=1;i《=n;i++) { if(HT.parent==0) if(HT.weight) if(s2!=i) s1=i; } for(j=1;j《=n;j++) { if(HT.parent==0) if(HT.weight) if(s1!=j) s2=j; } if(s1》s2){ int temp=s1; s1=s2; s2=temp;}}void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {int i,j;char *cd;int p;int cdlen;if (n《=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); for (i=1; i《=n; i++) { HT; HT.parent=0; HT.lchild=0; HT.rchild=0; } for (i=n+1; i《=m; i++) { HT.weight=0; HT.parent=0; HT.lchild=0; HT.rchild=0; }

//添加查看，便于调试printf(“构造过程显示：\n“); for(i=1;i《=m;i++) printf(“%4d%4d%4d%4d%4d\n“,i,HT.rchild);system(“pause“);for(i=n+1;i《=m;i++){ Select(HT,i-1); HT.parent = i; HT.rchild = s2; HT.weight; //添加查看，便于调试 /*printf(“s1=%d,s2=%d\n“,s1,s2); for(j=1;j《=i;j++) printf(“%d%4d%4d%4d“,j,HT.rchild); system(“pause“); */}cd = (char *)malloc(n*sizeof(char));p=m;cdlen=0;for(i=1;i《=m;i++) HT.weight=0;while(p){ if(HT.weight==0) { HT.weight=1; if(HT.lchild!=0) { p=HT.lchild; cd=’0’; } else if(HT.rchild==0) { HC=(char *)malloc((cdlen+1)*sizeof(char)); cd=’\0’; strcpy(HC,cd); } } else if(HT.weight==1) { HT.weight=2; if(HT.rchild!=0) { p=HT.rchild; cd=’1’; } } else { HT.weight=0; p=HT.parent; --cdlen; }}}int main(){HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf(“请输入节点数：\n“);scanf(“%d“,&n);HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));w=(int *)malloc(n*sizeof(int));printf(“请输入节点的权值：\n“);for(i=0;i《n;i++) scanf(“%d“,&w);HuffmanCoding(HT,HC,w,n); printf(“输出编码：\n“);for(i=1;i《=n;i++) printf(“%2d(%4d):%s\n“,i,w); return 0;system(“pause“);}

有6个字符,分别是A,B,C,D,E,F,对应的权值分别是6,5,4,3,2,1,也就是说字符A的权值是6,字符B的权值是5,按此顺序,最后的字符F的权值是1.求这6个字符的哈夫曼编码.运行程序:输入叶子结点的总个数(n): 6输入6个叶子结点的字符(Data)和权值(Weight):No.1=》Data:A      Weight:6No.2=》Data:B      Weight:5No.3=》Data:C      Weight:4No.4=》Data:D      Weight:3No.5=》Data:E      Weight:2No.6=》Data:F      Weight:1输出哈夫曼编码:A (6): 10B (5): 01C (4): 00D (3): 110E (2): 1111F (1): 1110对应的哈夫曼树(带权值):         N21      /       \     N9       N12                /  \     /   \   4    5   6    N6                /  \               3   N3                  /  \                 1    2 对应的哈夫曼树(带字符):( 注:哈夫曼树的左分支代表0,右分支代表1 )         N21      /       \     N9       N12                /  \     /   \   C    B   A    N6                /  \               D   N3                  /  \                 F    E 例如:从根结点N21到结点A,先经历右分支,后经历左分支,结点A的编码就是10从根结点N21到结点F,先经历三次右分支,最后经历左分支,结点F的编码就是1110#include《stdio.h》#define max 21struct huffnode{    char data;    int weight;    int parent;    int left;    int right;};struct huffcode{    char cd;    int start;};int main()  //原代码main(){    struct huffnode ht;    struct huffcode hcd,d;    int i,k,f,l,r,n,c,m1,m2;    //printf(“please input n \n“);    printf(“输入叶子结点的总个数(n): “);    scanf(“%d“,&n);    printf(“输入%d个叶子结点的字符(Data)和权值(Weight):\n“,n);    for(i=1;i《=n;i++)    {        getchar(); //吸收掉回车符’\n’        //原代码printf(“NO.&d=》Data:“,i);        printf(“NO.%d=》Data:“,i);        scanf(“%c“,&ht.data);        printf(“\t Weight:“);        scanf(“%d“,&ht.weight);    }    for(i=1;i《=2*n-1;i++) //所有结点初始化    {        ht.right=0;    }    //创建“哈夫曼树“    //原代码for(i=1;i《=2*n-1;i++)    for(i=1;i《n;i++)    {        //查找“最小值“和“次最小值“的下标        //l是最小值的下标,r是次最小值的下标        m1=32767;        l=r=0;        //原代码for(k=1;k《=i-1;k++)        for(k=1;k《=n+i-1;k++)        {            //原代码if(ht.weight==0)            if(ht.parent==0)            {                if(ht.weight《m1)                {                    m2=m1;                    r=l;  //原代码r=1;                    m1=ht.weight;                    l=k;                }                else if(ht.weight《m2)                {                    m2=ht.weight;                    r=k;                }            }        }        //原代码ht.parent=i;        //原代码ht.parent=i;        //原代码ht.weight;        //原代码ht.left=l;        //原代码ht.right=r;        ht.parent=n+i;        ht.parent=n+i;        ht.weight; //新结点        ht.left=l;        ht.right=r;    }    //编码过程    for(i=1;i《=n;i++)    {        d.start=n;        c=i;        f=ht.parent;        while(f!=0)        {            if(ht.left==c)            {               d.cd=’0’;            }            else            {               d.cd=’1’;            }            d.start=d.start-1;            c=f;            f=ht.parent;        }        //原代码hcd=d;        hcd.start=d.start;        for(k=d.start+1; k《=n; k++)        {            hcd;        }    }    //输出每个叶子结点的哈夫曼编码    //printf(“output huff_code:\n“);    printf(“输出哈夫曼编码:\n“);    for(i=1;i《=n;i++)    {        printf(“%c (%d): “,ht.weight);        //原代码for(k=hcd.start;k《=n;k++)        for(k=hcd.start+1;k《=n;k++)        {            printf(“%c“,hcd);        }        printf(“\n“);    }    return 0;  //int main()要有返回值}

去年做的课程设计，有什么不合要求的自己改改 #include《string.h》 #include《stdlib.h》 #include《stdio.h》 int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i 《= n;i++) if(!HT.parent){s1 = i;break;} for(j = i+1;j 《= n;j++) if(!HT.parent){s2 = j;break;} for(i = 1;i 《= n;i++) if((HT.parent)&&(s2!=i))s1=i; for(j = 1;j 《= n;j++) if((HT.parent)&&(s1!=j))s2=j; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC, int *w, int n) { // 算法6.13 // w存放n个字符的权值(均》0)，构造哈夫曼树HT， // 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; if (n《=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i《=n; i++) { //初始化 HT; HT.parent=0; HT.lchild=0; HT.rchild=0; } for (i=n+1; i《=m; i++) { //初始化 HT.weight=0; HT.parent=0; HT.lchild=0; HT.rchild=0; } puts(“\n哈夫曼树的构造过程如下所示：“); printf(“HT初态:\n 结点 weight parent lchild rchild“); for (i=1; i《=m; i++) printf(“\n%4d%8d%8d%8d%8d“,i,HT.weight, HT.rchild); printf(“ 按任意键，继续 ...“); getchar(); for (i=n+1; i《=m; i++) { // 建哈夫曼树 // 在HT中选择parent为0且weight最小的两个结点， // 其序号分别为s1和s2。 Select(HT, i-1); HT.parent = i; HT.rchild = s2; HT.weight; printf(“\nselect: s1=%d s2=%d\n“, s1, s2); printf(“ 结点 weight parent lchild rchild“); for (j=1; j《=i; j++) printf(“\n%4d%8d%8d%8d%8d“,j,HT.weight, HT.rchild); printf(“ 按任意键，继续 ...“); getchar(); } //------无栈非递归遍历哈夫曼树，求哈夫曼编码 cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间 p = m; cdlen = 0; for (i=1; i《=m; ++i) // 遍历哈夫曼树时用作结点状态标志 HT.weight = 0; while (p) { if (HT.weight==0) { // 向左 HT.weight = 1; if (HT =’0’; } else if (HT.rchild == 0) { // 登记叶子结点的字符的编码 HC = (char *)malloc((cdlen+1) * sizeof(char)); cd, cd); // 复制编码(串) } } else if (HT.weight==1) { // 向右 HT.weight = 2; if (HT =’1’; } } else { // HT.weight==2，退回退到父结点，编码长度减1 HT.parent; --cdlen; } } } // HuffmanCoding void main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts(“输入结点数:“); scanf(“%d“,&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf(“输入%d个结点的权值\n“,n); for(i = 0;i 《 n;i++) scanf(“%d“,&w); HuffmanCoding(HT,HC,w,n); puts(“\n各结点的哈夫曼编码:“); for(i = 1;i 《= n;i++) printf(“%2d(%4d):%s\n“,i,w); getchar(); }

手打的,你最好编译一下以免我哪里敲错了 (百度不能显示行首空格真是不爽) //哈夫曼树和~编码的存储表示 typedef struct{ unsigned int weight;//权值 unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树 typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表 void HoffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //w存放n个字符的权值(均》0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC if (n《=1) return; m=2*n-1; HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0号单元未采用 for (p=HT,i=1;i《=n;++i,++p,++w) *p={*w,0,0,0}; for (;i《=m;++i;++p) *p={0,0,0,0} for (i=n+1;i《=m;++i){//建哈夫曼树 //在HT选择parent为0且weight最小的两个结点编号分别为s1,s2 Select(HT,i-1,s1,s2); HT.parent=i; HT.rchild=s2; HT.weight; } //从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间 cd=“\0“;//编码结束符 for (i=1;i《=n;++i){//逐个字符求哈夫曼编码 start=n-1;//编码结束符位置 for (c=i,f=HT.parent)//从叶子逆向向根求编码 if (HT=“0“; else cd=“1“; HC=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 strcpy(HC);//从cd复制编码(串)到HC } free(cd);//释放工作空间 }//HuffmanCoding

#include《stdio.h》#include《string.h》#define N 50 //叶子结点数#define M 2*N-1 //树中结点总数typedef struct{ char data; } printf(“\n“); createht(ht,n); createhcode(ht,hcd,n); disphcode(ht,hcd,n); printf(“\n“);}

我写了一个注释较为完整且压缩、解压缩比较全面的：#include 《stdio.h》#include 《conio.h》#define MAX_FILE 5000/* 假设的文件最大长度 */#define MAXLIST 256/* 最大MAP值 */#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */char dictionary为字符 */char fileContent;/* 处理的字符串大小 */int Hoffman={2};/* 哈夫曼编码序列 */char HoffmanList={0};/* 哈夫曼编码对应的字符有序序列 */char HoffFileCode={0};/* 哈夫曼编码字符串序列 */char HoffFile={0};/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */char GetFile={0};/* 解码序列 */void ShellSort(char pData,int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */{ int step={9,5,3,1};/* 增量序列 */ int iTemp,cTemp; int k,s,w,i,j; for(i=0;i《4;i++) { k=step; s=-k; for(j=k;j《Count;j++) {iTemp=pData; cTemp=pData; w=j-k; if(s==0) { s=-k; s++; pData=iTemp; pData=cTemp; } while((iTemp《pData)&&(w》=0)&&(w《=Count)) { pData;/* 权值交换 */ pData;/* 字符交换 */ w=w-k; } pData=iTemp; pData=cTemp; } }}struct TNode/* 哈夫曼树结点 */{ struct TNode* pNode; struct TNode* lNode; struct TNode* rNode; char dictionary; char weight; };void TNode_init(struct TNode*tn,char dic,char wei) { tn-》pNode=0; tn-》lNode=0; tn-》rNode=0; tn-》dictionary=dic; tn-》weight=wei; }struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */{ struct LNode* prev; struct LNode* next; struct TNode* tnode;};void LNode_init(struct LNode* ln){ ln-》prev=ln-》next=0; ln-》tnode=0;}int len=0;/* 哈夫曼编码数 */int deep=-1;/* 深度 */void Preorder(struct TNode * p);/* 前序遍历 */void byLeft(struct TNode*p)/* 经由左结点 */{ deep++; Hoffman=0; Preorder(p); Hoffman=2; deep--;}void byRight(struct TNode*p)/* 经由右结点 */{ deep++; Hoffman=1; Preorder(p); Hoffman=2; deep--;}void Preorder(struct TNode * p){ int i; if(p-》lNode!=0)/* 当左子结点非空则遍历 */ { byLeft(p-》lNode); } if(p-》rNode!=0)/* 当右子结点非空则遍历 */ { byRight(p-》rNode); }if((p-》lNode==0)&&(p-》rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */ { Hoffman=2; i=0; for(;Hoffman!=2;i++) { Hoffman; } Hoffman=2; HoffmanList=p-》dictionary;len++; }}char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */{ char c=0; for(;k!=0;k--) { c|=(1《《(k-1)); } return c;}int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */{ unsigned char t=(((((0x00ff&b1)《《8)|(0x00ff&b2))》》(8-d))&0x00ff); return (((t)&((generateOne(l)《《(8-l))&0xff))==((c《《(8-l))&0xff));}int main(){ struct LNode* t,*p; struct LNode* head; struct TNode *tempTNode,*k1; int i=0,j,k; unsigned short fileLen=0; int len=0,l,b1,b2,d; char c; int code,h=0; int codeLen=0,total=0; /* 或许假定的文件字符串向量中的字符串 */ printf(“please Enter string to be pressed:“); scanf(“%s“,&fileContent);/* Hash进dictionary */ for(;fileContent!=’\0’;i++,fileLen++) { ++dictionary; dictionary; }/* 把Hash了的dictionary向前靠拢 */{ for(i=0;i!=MAXLIST;i++) { if(dictionary!=0) { dictionary; dictionary; len++; } } } printf(“the number of Huffman’s codes:%d\n“,len); /* 对dictionary按权值进行排序 */ ShellSort(dictionary,len); /* 构造链表,链表中放有序dictionary权值的树结点 */ head=(struct LNode*)malloc(sizeof(struct LNode)),p=head; LNode_init(head); head-》next=(struct LNode*)malloc(sizeof(struct LNode)); LNode_init(head-》next); tempTNode=(struct TNode*)malloc(sizeof(struct LNode)); TNode_init(tempTNode,dictionary); head-》tnode=tempTNode;{ for(i=0;i!=len-1;i++) { p-》next-》prev=p-》next; p=p-》next; p-》next=(struct LNode*)malloc(sizeof(struct LNode)); LNode_init(p-》next); tempTNode=(struct TNode*)malloc(sizeof(struct TNode)) ; TNode_init(tempTNode,dictionary); p-》tnode=tempTNode; } } free(p-》next); p-》next=0; /* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/ for(p=head;p-》next!=0;) { p-》tnode-》pNode=(struct TNode*)malloc(sizeof(struct TNode)) ; TNode_init(p-》tnode-》pNode,’\0’,(p-》tnode-》weight)+(p-》next-》tnode-》weight));p-》next-》tnode-》pNode=p-》tnode-》pNode; p-》tnode-》pNode-》lNode=p-》tnode; p-》tnode-》pNode-》rNode=p-》next-》tnode; head=p-》next; free(p); p=head; p-》tnode=p-》tnode-》pNode; for(t=head;t-》next!=0;t=t-》next) { if(t-》tnode-》weight》t-》next-》tnode-》weight) { k1=t-》tnode; t-》tnode=t-》next-》tnode; t-》next-》tnode=k1; } } }/* 前序遍历构造哈夫曼编码 */ Preorder(p-》tnode); { for(i=0;i!=len;i++) dictionary=i; } /* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */ { for(i=0;i!=fileLen;i++) { int j=dictionary; for(k=0;Hoffman!=2;k++) { HoffFileCode《《(7-total%8)); code; if(((total+1)%8)==0) { HoffFile; codeLen++; } total++; }} } HoffFile; HoffFile=(fileLen);/* 解压缩假定的文件HoffFile成为原字符串序列 */ printf(“Huffman’s code list:\n“); HoffFile=len; { for(i=0,j=0;i!=len;i++,j=0) { for(;Hoffman!=2;j++); HoffFile=j; HoffFile;for( k=0;k!=j;k++) { printf(“%d“,Hoffman); HoffFile《《(j-1-k)); } printf(“:%d\n“,HoffmanList);} }{ for(i=0,j=0;i!=(HoffFile&0xff);i++) { for(k=0;k!=HoffFile;k++) { l=HoffFile; c=HoffFile; if(compareBits(b1,b2,c,l,d)) { j+=HoffFile; GetFile; break; } } } } { printf(“Huffman code List Pressed :\n“); for(i=0;i!=h;i++) { printf(“%c“,code); if((i+1)%8==0) printf(“ “); } } printf(“\n“); { printf(“Huffman code packaged:\n“); for(i=0;i!=HoffFile*3;i++) { printf(“%c“,HoffFile); } printf(“\n“); } printf(“The initial len :%d\n“,fileLen); printf(“The string len pressed:%d\n“,(h)/8+1); printf(“The rate%.2f\%“,((h/8.0+1)/fileLen)*100);{ printf(“The number of bytes:%d\n“,(HoffFile&0xff)); printf(“The string decoded:“); for(i=0;i!=(HoffFile&0xff);i++) { printf(“%c“,GetFile); }printf(“\n“); } getch(); return 1;}

#include《stdio.h》#defineMAXBIT10/*定义哈夫曼编码的最大长度*/#defineMAXVALUE10000/*定义最大权值*/#defineMAXLEAF30/*定义哈夫曼树中最多叶子节点个数*/#defineMAXNODEMAXLEAF*2-1/*哈夫曼树最多结点数*/typedefstruct{/*哈夫曼编码信息的结构*/intbit;intstart;}Hcodetype;typedefstruct{/*哈夫曼树结点的结构*/intweight;intparent;intlchild;intrchild;}Hnodetype;voidhuffmantree(Hnodetypehuffnode,intn)/*构造哈夫曼树的函数*/{inti,j,m1,m2,x1,x2;for(i=0;i《2*n-1;i++)/*存放哈夫曼树结点的数组huffnode初始化*/{huffnode.weight=0;huffnode.parent=-1;huffnode.lchild=-1;huffnode.rchild=-1;}for(i=0;i《n;i++)/*输入入N个叶子节点的权值*/{printf(“pleaseinput%dcharacter’sweight\n“,i);scanf(“%d“,&huffnode.weight);}for(i=0;i《n-1;i++)/*开始循环构造哈夫曼树*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j《n+i;j++){if(huffnode.parent==-1){m2=m1;x2=x1;m1=huffnode.weight;x1=j;}elseif(huffnode.parent==-1){m2=huffnode.weight;x2=j;}}huffnode.parent=n+i;huffnode.parent=n+i;huffnode.weight;huffnode.lchild=x1;huffnode.rchild=x2;}}voidmain(){Hnodetypehuffnode;Hcodetypehuffcode,cd;inti,j,c,p,n;printf(“pleaseinputn\n“);scanf(“%d“,&n);/*输入叶子节点个数*/huffmantree(huffnode,n);/*建立哈夫曼树*/for(i=0;i《n;i++)/*该循环求每个叶子节点对应字符的哈夫曼编码*/{cd.start=n-1;c=i;p=huffnode.parent;while(p!=-1){if(huffnode.lchild==c)cd.bit=0;elsecd.bit=1;cd.start--;c=p;p=huffnode.parent;}for(j=cd.start+1;j《n;j++)/*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/huffcode;huffcode.start=cd.start;}for(i=0;i《n;i++)/*输出每个叶子节点的哈夫曼编码*/{printf(“%dcharacteris:“,i);for(j=huffcode.start+1;j《n;j++)printf(“%d“,huffcode);printf(“\n“);}}

以先根次序遍历二叉树。然后还要定义一整数a，初始值为1。在访问某一节点时将其作为参数传入，如果访问的是左节点传入a*2，访问右节点传入a*2+1，也就是在a的二进制数据中，向左走在末尾加个0，向右走加个1（初始化为1是为了避免开始时向左走，无法加零的情况，输出时要将首位的1去掉），即visit（root，a），visit（left，a*2），visit（right，a*2+1）。访问到叶子节点时将a转化成二进制，再将首位的1去掉即可。当然你也可以定义一个字符串，然后在末尾加0加1，只是这样递归起来开销比较大，用整数*2的方法比较简单，但是最后需要转化处理。