10-10.c

数据结构的经典实现算法

#include  < stdio.h>
typedef int Type;
typedef int T;
typedef struct BiTNode  {
       Type data;
       struct BiTNode *lchild,*rchild;
}binarytree;
typedef struct Huffmannode{
	binarytree tree;
	T weight;
}Huffman;
typedef struct  info{
		Huffman data;
		/* 其他数据 */
}minheap;
binarytree huffmantree(T a[], int n)
{// 根据权重a [ 1 : n ]构造霍夫曼树
// 创建一个单节点树的数组
	huffman *w = calloc((n+1)*sizeof(Huffman));
	int i;
	binarytree z, zero;
	for (i=1; i <= n; i++) {
		tnserttree(z,i, zero, zero);
		w[i].weight = a[i];
		w[i].tree = z;
	}
	// 把数组变成一个最小堆
	minheap H[1];
	initialize( w, n , n ) ;
	// 将堆中的树不断合并
	Huffman x, y;
	for (i = 1; i < n; i++) {
		mindelete(H,x ) ;
		mindelete(H,y ) ;
		inserttree(z,0, x.tree, y. t r e e ) ;
		x.weight += y.weight; x.tree = z;
		insert (H,x ) ;
	}
	mindelete(H,x ) ; // 最后的树
	deactivate(H) ;
	free(w);
	return x.tree;
}