c语言实现传递函数的离散化（数据结构-构造哈夫曼树）

给定n个权值的集合W={w₁,w₂,….w_n}

1.在W中选取两个最小的权作为兄弟结点，以它们的权值之和作为其父结点，得到一棵新树；

2.在W中删除上述已选取的权值，以它们的权值之和作为新的权值加入W中；

3.在已构造的二叉树中重复①、②，直至W中只含有一个权重值，这棵二叉树就是所要建立的哈夫曼树（构造出有n个叶结点，叶结点相应的权值为w₁,w₂…w_n的一棵树）

假定仍采用图6-11中的四个带权叶子结点来构造一棵哈夫曼树，按照上述算法，则构造过程如图6-12所示，其中图6-12(d)就是最后生成的哈夫曼树，它的带权路径长度为37，由此可知，图6-11(c)是由所给的4个带权叶子结点生成的一棵哈夫曼树。

构造哈夫曼的过程

在构造哈夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，新树的左子树和右子树可以任意安排，这样将会得到具有不同结构的多个哈夫曼树，但它们都具有相同的带权路径长度。为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。上述哈夫曼树的构造过程就是遵照这一规定进行的。

（2）构造哈夫曼树的算法描述

根据上述构造哈夫曼树的过程可以写出相应的用C语言描述的算法，具体如下：

构造哈夫曼树算法

struct BTreeNode* CreateHuffman(int a[], int n) /*根据数组a中n个权值建立一棵哈夫曼树，返回树根指针*/ { int i,j; struct BTreeNode **b,*q; /*动态分配一个由b指向的指针数组*/ b=calloc(n, sizeof(struct BTreeNode*)); /*初始化b指针数组，使每个指针元素指向a数组中对应元素的结点*/ for(i=0; i<n; i ) { b[i]=malloc(sizeof(struct BTreeNode)); b[i]->data=a[i]; b[i]->left=b[i]->right=NULL; } /*进行n-1次循环建立哈夫曼树*/ for(i=1; i<n; i ) { /*用k1表示森林中具有最小权值的树根结点的下标*/ /*用k2表示森林中具有次最小权值的树根结点的下标*/ int k1=-1,k2; /*让k1初始指向森林中第一棵树，k2初始指向森林中第二棵树*/ for(j=0; j<n; j ) { if(b[j]!=NULL && k1==-1) {k1=j; continue;} if(b[j]!=NULL) {k2=j; break;} } /*从当前森林中求出最小权值树和次最小权值树*/ for(j=k2; j<n; j ) { if(b[j]!=NULL) { if(b[j]->data<b[k1]->data) {k2=k1; k1=j;} else if(b[j]->data<b[k2]->data) k2=j; } } /*由最小权值树和次最小权值树建立一棵新树，q指向树根结点*/ q=malloc(sizeof(struct BTreeNode)); q->data=b[k1]->data b[k2]->data; q->left=b[k1]; q->right=b[k2]; /*将指向新树的指针赋给b指针数组中k1位置，k2位置置为空*/ b[k1]=q; b[k2]=NULL; } /*删除动态建立的数组b*/ free(b); /*返回整个哈夫曼树的树根指针*/ return q; }

在这个算法中有多处动态分配存储空间，按正常情况需要判断分配是否成功，这里为简便起见而省略了。不过，由于计算机操作系统的功能越来越强，即使内存无动态分配的空间可用，系统也会自动到外存寻找空间并进行有效分配，所以通常没有必要判断动态分配是否有效。万一分配失败，也不会造成机器故障，系统会自动退出程序运行。

（3）求哈夫曼树的带权路径长度的算法描述

下面给出求哈夫曼树带权路径长度的算法。

求哈夫曼树的带权路径长度的算法

int WeightPathLength(struct BTreeNode* FBT, int len) /*根据FBT指针所指向的哈夫曼树求出带权路径长度，len初值为0*/ { if(FBT==NULL) return 0; /*空树则返回0*/ else { /*访问到叶子结点时返回该结点的带权路径长度，其中值参len保存当前被访问结点的路径长度*/ if(FBT->left==NULL && FBT->right==NULL) { return FBT->data*len; } /*访问到非叶子结点时进行递归调用，返回左、右子树的带权路径长度之和，向下深入一层时len值增1*/ else { return WeightPathLength(FBT->left,len 1) WeightPathLength(FBT->right,len 1); } } }

,