哈工大数据结构大作业——哈夫曼树生成、编码、遍历

。

#define m 2*(n)-1

typedef struct//建立哈夫曼结点结构体 {

char data; float weight; int lchild; int rchild; int parent; }htnode;

typedef struct//建立哈夫曼编码结构体 {

char ch; char bits[n+1]; }htcode;

void SelectMin(htnode T[m],int nn,int&p1,int&p2)//选择哈夫曼树所有结点中权值最小的两个根结点 { int i,j;

for(i=0;i<=nn;i++) {

if(T[i].parent==-1)

{ p1=i;

break; }

}

for(j=i+1;j<=nn;j++) {

if(T[j].parent==-1)

-可编辑修改-

。

{ p2=j;

break; }

}

for(i=0;i<=nn;i++) {

if((T[p1].weight>T[i].weight)&&(T[i].parent==-1)

&&(p2!=i)) p1=i;

}

for(j=0;j<=nn;j++) {

if((T[p2].weight>T[j].weight)&&(T[j].parent==-1) }

void CreatHT(htnode T[m])//建立哈夫曼树 {

int i,p1,p2; for(i=0;i

{

T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值 } {

SelectMin(T,i-1,p1,p2); T[p1].parent=T[p2].parent=i;

-可编辑修改-

&&(p1!=j)) p2=j;

}

for(i=n;i

。

}

if(T[p1].weight

T[i].lchild=p2; }

T[i].weight=T[p1].weight+T[p2].weight; }

T[i].rchild=p2;

T[i].rchild=p1;

void HuffmanEncoding(htnode T[m],htcode C[n])//哈夫曼编码 {

int c,p,i; char cd[n+1]; int start;

cd[n]='\\0';//结束表示 for(i=0;i

{

C[i].ch=T[i].data; start=n; c=i;

while((p=T[c].parent)>=0) {

start=start-1; if(T[p].lchild==c) {

cd[start]='0';

-可编辑修改-

。

}

}

else {

cd[start]='1';

} c=p;

}

strcpy(C[i].bits,&cd[start]); }

void preorder(htnode T[],int i)//先序遍历哈夫曼树：递归的办法 {

printf(\

if(T[i].lchild!=-1) { }

void inorder(htnode T[],int i)//中序遍历哈夫曼树 {

-可编辑修改-

preorder(T,T[i].lchild); preorder(T,T[i].rchild);

}