数据结构c语言版哈夫曼树

① 数据结构中哈夫曼树的应用（c语言）

#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;

typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;

struct worder
{
char words; /*字符*/
}word[100];
struct weighted
{
int weighter; /*转换权值有利于文件的存储*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉树*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子树*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}

BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子树*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}

void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼树*/
{
int i,j,m1,m2,x1,x2;

for(i=0;i<2*n-1;i++)
{

if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}

for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*将每个权值赋值给二维数组a[][],利用这个二维数组可以进行建立二叉树*/
a[i+1][2]=haffTree[n+i].weight;
}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*对已经建立好的哈夫曼树进行编码*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;

for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}

for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}

void PrintBiTree(BiTreeNode *bt ,int n) /*将哈夫曼树转换成的二叉树进行打印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}

int search(int a[][3],int m) /*查找和a[][2]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失败返回数字0 查找成功返回和a[][2]相等的数的行数 i*/
else return i;
}

int searcher(int a[][3],int m) /*查找和a[][1]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失败返回数字0 查找成功返回和a[][1]相等的数的行数 i*/
i++;
if(i==m) return 0;
else return i;
}

void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼树*/（利用递归）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]为左子树*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]为右子树*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等则只要进行一个的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}

void code(Code myHaffCode[],int n ) /*编码*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存储编码的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*读取存储字符的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*输出每个权值的编码*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字符找到对应的编码*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*输出相应的编码*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}

fclose(fp2);
}

void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存储权值个数的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存储字符的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存储权值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;

printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}

void menu() /*界面*/
{

printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*编码*/
printf("\t\t\t2. Decoding:\n\n"); /*译码*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*打印哈夫曼树*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}

void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;

HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;

case 5:exit(0);
}
}
}
getch();
}

② 关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：

下面是我写程序的时候的注释，两种方法都写上了。这个程序不能运行，主要是为了理解，注释写的很清楚的。
/*这只是讲解，程序并不能运行*/
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

int a[100];
int s1,s2;

int Select()
/*在Select函数中，选取了两个根节点权值最小的树构造了一棵新的数，需要将这两个最小的删掉，将新的加入，再找两个最小的，但如果这样，我们就修改了树了，最后得到
的树中，我们删除了一些结点，所以我想，将这些树的权值放在一个整型数组中，去寻找最小的两个*/
{
min=a[1];
s1=1;
for(i=2;i<=a[0];++i)
if(min>a[i])
{
s2=s1;
s1=i;
}
for(i=s1;i<n;++i)
a[i]=a[i+1];
for(i=s2;i<n;++i)
a[i]=a[i+1];
a[0]=a[0]-2;
return OK;
}

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
int m,i,j,start,t;
if(n<=1)
return OK;
m=2*n-1; /*因为有n个叶结点，所以共有2*n-1个结点*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*为m个节点分配空间，0结点不使用*/
if(!HT)
return ERROR;
for(p=HT,i=1;i<=n;++i,++p)
{
p->weight=w[i]; /*数组w中存放叶结点的权值，从下标1开始*/
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;
} /*为非叶结点初始化，非叶结点的权值是待计算的*/
a[0]=n;
for(p=HT,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select(); /*找到a数组中两个最小的元素是s1,s2，并且删除它们,a[0]中存储a中元素个数，要及时修改a[0]的值*/
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight; /*将求得的新的结点的权值加入a数组中*/
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
} /*该循环是建赫夫曼树*/
/*以下从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*为n个字符编码分配头指针向量，0号单元不使用*/
cd=(char *)malloc(n*sizeof(char));
if(!cd)
return ERROR; /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=1;i<=n;++i)
{
start=n-1; /*由于n-1位置已经存放了'/0'，所以下面用--start,从n-2的位置存放0,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)); /*各字符的编码长度不等，故为每一个头指针向量动态分配它所指向的空间大小，就是n-start*/
if(!H[i])
return ERROR;
t=1;
printf("\n%d:",i);
for(j=start;j<=n-2;j++)
{
HC[i][t++]=cd[j];
printf("%c",cd[j]);
}
}
free(cd);
return HT;
}
/*由此得到的赫夫曼树的前n个分量表示叶子结点，最后一个分量表示根结点*/
/*以上算法是从叶子到根逆向处理的*/

/*以下算法是从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码*/
/*译码的过程是分解电文中字符串，从根出发，按字符'0'或'1'确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。*/
HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
HuffmanTree p;
char *cd;
int m,i,j,start,t,c,f;
if(n<=1)
exit(OK);
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
if(!HT)
return ERROR;
for(p=HT+1,i=1;i<=n;++i,++p)
{
p->weight=w[i];
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;
}
a[0]=n;
for(p=HT+1,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select();
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*分配n个字符编码的头指针向量*/
p=m; /*m是结点总数*/
cdlen=0; /*应该是计数每一个编码的长度*/
for(i=1;i<=m;++i)
HT[i].weight=0; /*遍历赫夫曼树时用作结点的标志(是否是weight域为0，表示没有遍历过，weight域为1，表示遍历过)*/
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
} /*左孩子不等于0，表示没有走到左边的尽头，0就是NULL，*/
/*我们将一直执行这个if语句，直到走到左边的尽头，将所有左边的边全部赋值为0*/
else
if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd); /*当走到最左边的时候，我们就得到了最左下那个结点的编码，存储在cd数组中，将它赋值到HC[p]中*/
}
}
else
if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen; /*因为这个编码和上一个编码只有最后一位是不一样的，所以cdlen-1*/
}
}
return HT;
}

③ 有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗

在一般的数据结构的书中，树的那章后面，着者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如

JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点

的权值乘上其到根结点的 路径长度（若根结点为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中只有一棵二叉树为止。

简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：

所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

C语言代码实现：

/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解码部分)
* 在 Win-TC 下测试通过
* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
* 父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>

#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1

typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 结点结构体 */

/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, 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; //实际值，可根据情况替换为字母
} /* end for */

/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d: ", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */

/* 循环构造 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;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 设置找到的两个子结点 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.weight and x2.weight in round %d: %d, %d ", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
printf (" ");
} /* end for */
/* 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);
}*///测试
} /* end HuffmanTree */

//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[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 ;
}
else tmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


int main(void)
{

HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n: ");
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; /* 设置下一循环条件 */
} /* end while */

/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */

/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", 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?Please Enter code: ");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}

④ 用c语言解决数据结构哈夫曼树问题

#include "string.h"
#include "stdio.h"
#define MAXVALUE 1000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树叶结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 30 /*定义哈夫曼编码的最大长度*/
typedef struct
{ int bit[MAXBIT];
int start;
} HCODETYPE;
typedef struct
{ int weight;
int parent;
int lchild;
int rchild;
} HNODETYPE;
char *getcode1(char *s1,char *s2,char *s3) /*首先去掉电文中的空格*/
{ char temp[128]="",*p,*q;
p=s1;
while ((q=strstr(p,s2))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2); }
strcat(temp,p);
strcpy(s1,temp);
return s1;
}
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/
char * getcode (char *s1)
{ char s2[26],s5[26];
char temp[200]="",*p,*q,*r,*s3="";
int m,e,n=0;
m=strlen(s1);
while(m>0)
{ p=s1;
s2[0]=s1[0];
s2[1]='\0';
r=s2;
e=0;
while((q=strstr(p,r))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2);
e++; }
m-=e;
strcat(temp,p);
strcpy(s1,temp);
s5[n]=s2[0];
n++;
strcpy(temp,"");
}
s5[n]='\0';
strcpy(s1,s5);
printf(" 压缩后的电文（即叶结点）: %s\n",s1);
return s1;
}
HNODETYPE huffmantree(char *s2,char s3[])
{ HNODETYPE huffnode[MAXNODE];
HCODETYPE huffcode[MAXLEAF],cd;
int sum,i,j,n1,n2,x1,x2,p,k,c;
char s1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','w','x','y','z'};
char s5[MAXLEAF];
int ww[26]={0},n=0;
strcpy( s5,s2);
sum=strlen(s2);
for(i=0;i<26;i++) /*统计所有字符出现的频度*/
for(j=0;j<sum;j++)
if(s2[j]==s1[i]) ww[i]++;
n=strlen(s3);
for (i=0;i<2*n-1;i++)
{ huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1; }
for(i=0;i<n;i++) /*分配给各叶结点权值*/
for(j=0;j<26;j++)
if (s3[i]==s1[j]) huffnode[i].weight=ww[j];
for (i=0;i<n-1;i++) /*构造哈夫曼树*/
{ n1=n2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{ if (huffnode[j].parent==-1 && huffnode[j].weight<n1)
{ n2=n1;
x2=x1;
n1=huffnode[j].weight;
x1=j; }
else
if (huffnode[j].parent==-1 && huffnode[j].weight<n2)
{ n2=huffnode[j].weight; x2=j;}
}
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;
}
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;
}
for (j=cd.start+1;j<n;j++)
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
printf(" 各叶结点对应哈夫曼编码 : ");/*输出每个叶结点的哈夫曼编码*/
for(i=0;i<n;i++)
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" ");}
printf("\n 电文的全部哈夫曼编码 : ");/*输出电文的全部哈夫曼编码*/
for(k=0;k<sum;k++)
for(i=0;i<n;i++)
if(s2[k]==s3[i])
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" "); }
printf("\n");
}
main()
{
char s1[MAXLEAF],s2[MAXLEAF];
printf("\n 请输入电文 : ");
gets(s1);
strcpy(s2,getcode1(s1," ",""));
huffmantree(s1,getcode(s2));
}

⑤ 怎么样用c语言程序编码哈夫曼树

#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[i]!='\0'; i++)
{
if(ch==s[i])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[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].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[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从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[i]);

}
return 0;
}