数据结构考研分类复习真题 第六章 答案 (五)[50]

．（）哈夫曼树的构造过程

① 根据给定的n个权值{WWW…Wn}构成n棵二叉树的集合F={TT…Tn}其中每棵二叉树Ti只有权值为Wi的根结点其左右子树均为空

② 在F中选取两棵根结点的权值最小的树作左右子树构造一棵新二叉树新二叉树根结点的权值为其左右子树上根结点的权值之和

③ 在F中删除这两棵树同时将新得到的二叉树加入F中

④ 重复②和③直到F中只剩一棵树为止这棵树便是哈夫曼树

（）含有n个叶子结点的哈夫曼树共有n个结点采用静态链表作为存储结构设置大小为n的数组现将哈夫曼树的结点及树的结构定义如下

typedef struct{float weight ; //权值

int parentlcrc;//双亲左右子女 }node ;

typedef node HufmTree[*n];

void Huffman(int nfloat w[n]HufmTree T)

//构造n个叶子结点的哈夫曼树Tn个权值己放在W[n]数组中

{int ijpp //pp为最小值和次最小值的坐标

float smallsmall; //small和small为权值的最小值和次小值

for(i=;i<*n;i++) //置初值结点的权左右子女双亲

{T[i]parent=; T[i]lc=; T[i]rc=;

if(i<n) T[i]weight=w[i]; else T[i]weight=;

}

for (i=n ;i<*n;i++) //构造新二叉树

{p=p=;small=small=maxint; //初值

for(j=;j<i;j++)

if(T[j]weight<small && T[j]parent==) //最小值

{p=p; small=small; p=j; small=T[j]weight;}

else if(T[j]weight<small && T[j]parent==) //次小值

{p=j;small=T[j]weight;}

T[i]weight=T[p]weight+T[p]weight; //合并成一棵新二叉树

T[i]lc=p; T[i]rc=p; //置双亲的左右子女

T[p]parent=i; T[p]parent=i; //置左右子女的双亲

}//for(i=;i<*n;i++) }//结束huffman

求哈夫曼编码的算法

typedef struct {char bit[n]; int start;}codetype;

void HuffmanCode(CodeType code[n]HufmTree T) //哈夫曼树T已求出现求其哈夫曼编码

{int ijcp;

CodeType cd;

for(i=;i<n;i++)

{cdstart=n;c=i;p=T[i]parent;

while(p!=)

{cdstart;

if(T[p]lc==c) cdbit[cdstart]=//左分枝生成代码

else cdbit[cdstart]=; // 右分枝生成代码

c=p; p=T[p]parent; //双亲变为新子女再求双亲的双亲

}

code[i]=cd; //成组赋值求出一个叶子结点的哈夫曼编码

}//for }//结束HuffmanCode

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []