（完整版C语言代码）哈夫曼树的构造

图：最终构成的哈夫曼树

//哈夫曼树的构造
#include <stdio.h>
#include <stdlib.h>
#define MinSize -1000
typedef struct HTNode *HuffmanTree;
struct HTNode{
	int Weight;
	HuffmanTree Left;
	HuffmanTree Right;
};
typedef HuffmanTree ElementType;
typedef struct HeapNode *MinHeap;
struct HeapNode{
	ElementType *Elements;
	int Size;
	int Capacity;
};
MinHeap Create(int N)
{
	MinHeap H=(MinHeap)malloc(sizeof(struct HeapNode));
	H->Elements=(ElementType*)malloc((N+1)*sizeof(ElementType));
	H->Size=0;
	H->Capacity=N;
	
	HuffmanTree HT;
	HT=(HuffmanTree)malloc(sizeof(struct HTNode));
	HT->Weight=MinSize;
	HT->Left=HT->Right=NULL;
	H->Elements[0]=HT;
	return H;
}
void Insert(MinHeap H,ElementType X)
{
	if(H->Size==H->Capacity){
		printf("最小堆已经满，不能插入！\n");
		return;
	}
	int i=++H->Size;
	for(;X->Weight<H->Elements[i/2]->Weight;i/=2){//这里没有等号会少运行一次 
		H->Elements[i]=H->Elements[i/2];
	}	
	H->Elements[i]=X;
} 
ElementType DeleteMin(MinHeap H)
{
	if(H->Size==0){
		printf("最小堆为空，无法删除！\n");
		return NULL;
	}
	ElementType First=H->Elements[1],Last=H->Elements[H->Size];
	int Weight=H->Elements[H->Size--]->Weight;
	int Parent,Child;
	for(Parent=1;2*Parent<=H->Size;Parent=Child){
		Child=2*Parent;
		if((Child!=H->Size)&&(H->Elements[Child+1]->Weight<H->Elements[Child]->Weight))
			Child++;
		if(Weight<=H->Elements[Child]->Weight) break;//注意，这里有等号可以少运行一次 
		else H->Elements[Parent]=H->Elements[Child]; 		
	}
	H->Elements[Parent]=Last;
	return First;
}
void PercDown(MinHeap H,int index)
{
	ElementType i=H->Elements[index];
	int Parent,Child;
	for(Parent=index;2*Parent<=H->Size;Parent=Child){
		Child=2*Parent;
		if((Child!=H->Size)&&(H->Elements[Child+1]->Weight<H->Elements[Child]->Weight))
			Child++;
		if(i->Weight<=H->Elements[Child]->Weight) break;//注意，这里有等号可以少运行一次 
		else H->Elements[Parent]=H->Elements[Child]; 
	}
	H->Elements[Parent]=i;
}
void BuildMinHeap(MinHeap H)
{
	int i=H->Size/2;
	for(;i>0;i--)
		PercDown(H,i);
}
HuffmanTree Huffman(MinHeap H)
{
	int i,N=H->Size;
	HuffmanTree T;
	BuildMinHeap(H);
	for(i=1;i<N;i++){
		T=(HuffmanTree)malloc(sizeof(struct HTNode));
		T->Left=DeleteMin(H);
		T->Right=DeleteMin(H);
		T->Weight=T->Left->Weight+T->Right->Weight; 
		Insert(H,T);
	}
	return DeleteMin(H);
}
void Preorder(HuffmanTree HT)
{
	if(HT){
		printf("%d ",HT->Weight);
		Preorder(HT->Left);
		Preorder(HT->Right);
	}
}
int main()
{
	MinHeap H=Create(50);
	HuffmanTree HT;
	for(int i=1;i<=5;i++){
		HT=(HuffmanTree)malloc(sizeof(struct HTNode));
		HT->Weight=6-i;//希望存入权重5,4,3,2,1 
		HT->Left=HT->Right=NULL;
		H->Elements[i]=HT; 
	}
	H->Size=5;
	printf("没按权重调整的最小堆：");
	for(int i=1;i<=H->Size;i++) printf("%d ",H->Elements[i]->Weight);
	BuildMinHeap(H);
	printf("\n按权重调整后的最小堆：");
	for(int i=1;i<=H->Size;i++) printf("%d ",H->Elements[i]->Weight);
	printf("\n测试DeleteMin：%d\n",DeleteMin(H)->Weight);
	for(int i=1;i<=H->Size;i++) printf("%d ",H->Elements[i]->Weight);
	
	printf("\n测试Insert：");
	HT=(HuffmanTree)malloc(sizeof(struct HTNode));
	HT->Weight=1;
	HT->Left=HT->Right=NULL;
	Insert(H,HT);
	for(int i=1;i<=H->Size;i++) printf("%d ",H->Elements[i]->Weight);
	printf("\n测试Huffman：");
	HT=Huffman(H);
	Preorder(HT);
	return 0;
}