实验六 最优二叉树的应用_答案

实验六最优二叉树的应用【实验目的】掌握求最优二叉树的方法。【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率{2,3,5,7,11,13,17,19,23,29,31,37,41}，求各通信符号对应的前缀码。【实验原理和方法】（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。#includestdio.h#includestdlib.h#defineN13structtree{floatnum;structtree*Lnode;structtree*Rnode;}*fp[N];//保存结点chars[2*N];//放前缀码voidinite_node(floatf[],intn)//生成叶子结点{inti;structtree*pt;for(i=0;in;i++){pt=(structtree*)malloc(sizeof(structtree));//生成叶子结点pt-num=f[i];pt-Lnode=NULL;pt-Rnode=NULL;fp[i]=pt;}}voidsort(structtree*array[],intn)//将第N-n个点插入到已排好序的序列中。{inti;structtree*temp;for(i=N-n;iN-1;i++)if(array[i]-numarray[i+1]-num){temp=array[i+1];array[i+1]=array[i];array[i]=temp;}}structtree*construct_tree(floatf[],intn)//建立树{inti;structtree*pt;for(i=1;iN;i++){pt=(structtree*)malloc(sizeof(structtree));//生成非叶子结点//第一句pt-Lnode=fp[i-1];//第二句fp[i]=pt;//w1+w2sort(fp,N-i);}returnfp[N-1];}voidpreorder(structtree*p,intk,charc){intj;if(p!=NULL){if(c=='l')s[k]='0';elses[k]='1';if(p-Lnode==NULL){//P指向叶子printf(%.2f:,p-num);for(j=0;j=k;j++)printf(%c,s[j]);putchar('\n');}//第三句//第四句}}voidmain(){floatf[N]={2,3,5,7,11,13,17,19,23,29,31,37,41};structtree*head;//第五句-初始化结点head=construct_tree(f,N);//生成最优树s[0]=0;preorder(head,0,'l');//遍历树}参考答案：第一句：pt-num=fp[i-1]-num+fp[i]-num;第二句：pt-Rnode=fp[i];第三句：preorder(p-Lnode,k+1,'l');第四句：preorder(p-Rnode,k+1,'r');第五句：inite_node(f,N);