文档介绍：实验四哈夫曼树及其的应用
一、实验目的
,掌握对二叉树的一些其它操作的具体实现方法。
。
3、熟练掌握哈夫曼树(最优二叉树)特征及其应用
二、实验内容
题目一、哈夫曼树和哈夫曼编码:
从终端输入若干个字符,统计(或指定)字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。
设计要求:
⑴哈夫曼殊和哈夫曼编码的存储表示参考教材事例
⑵在程序中构造四个子程序为
① int freqchar(char *text, HTree *t) /*统计字符出现的频率*/
② int createhtree(HTree *t) /*根据字符出现的频率建立哈夫曼树*/
③ void coding(HTree *t,int head_i,char *code)
/*对哈夫曼树进行编码*/
④ void printhtree(HTree *t,int head_i,int deep,int* path)
/*中序打印树*/
数据类型定义及具体函数功能
struct TreeNode//树节点
{
char letter;
int wight;
int parent;
int lChild;
int rChild;
}a[100];
struct Code//存放每一组编码
{
char letter;
string str;
}b[27];
int search(char c,int k)//查找字符
{
int i;
for(i=1;i<k;i++)
if(a[i].letter==c) return i;//若表中有该字符则输出相应序号
return k;//没有找到返回最后的序号
}
int find_min(int k,int& min1,int& min2)//查找表中最小的两个的元素
{
int w1=10000,w2=10000,i=1,temp;
min1=min2=-1;
while(i<=k)
{
if(a[i].parent==0 && a[i].wight<w1)//找到一个较小的
{
min2=min1;
w2=w1;
min1=i;
w1=a[i].wight;
}
else if(a[i].parent==0 && a[i].wight<w2)
{
min2=i;
w2=a[i].wight;
}
i++;
}
if(min1>min2) temp=min1,min1=min2,min2=temp;//min1始终为最小,min2始终为次小
return 0;
}
int CreateTree(int k)//建哈弗曼树
{
int j,min1,min2;
j=k-1;
find_min(j,min1,min2);
while(min1>=0 && min2>=0)//找到两个最小的后增加节点
{
a[j+1].wight=a[min1].wight+a[min2].wight;
a[j