离散数学实验指导书及其答案(3)

实验七 最优二叉树的应用

【实验目的】掌握求最优二叉树的方法。

【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求

各通信符号对应的前缀码。

【实验原理和方法】

（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。

（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。 #include #include #define N 13 struct tree {

float num;

struct tree *Lnode; struct tree *Rnode; }* fp[N];//保存结点 char s[2*N];//放前缀码

void inite_node(float f[],int n)//生成叶子结点 {

}

void sort(struct tree * array[],int n)//将第N-n个点插入到已排好序的序列中。 {

int i;

struct tree *temp; for(i=N-n;i

if(array[i]->num>array[i+1]->num) { int i;

struct tree *pt; for(i=0;i

pt=(struct tree *)malloc(sizeof(struct tree));//生成叶子结点 pt->num=f[i];

pt->Lnode=NULL;pt->Rnode=NULL; fp[i]=pt;

}

}

temp=array[i+1]; array[i+1]=array[i]; array[i]=temp;

struct tree * construct_tree(float f[],int n)//建立树 {

int i;

struct tree *pt; for(i=1;i

return fp[N-1]; }

void preorder(struct tree *p,int k,char c) {

int j; if(p!=NULL) { } }

if(c=='l') s[k]='0'; else s[k]='1';

if(p->Lnode==NULL) {//P指向叶子 }