huffmantreebulid.cpp

来自「一个关于赫夫曼编码与译码的展示程序」· C++ 代码 · 共 44 行

#include"Huffmanhead.h"
extern s1,s2;
void HuffmanTreeBulid(HuffmanTree HT[],int *w,int n)//构造赫夫曼树HT
{
	int m,i;
	if(n==1)
	{ 
		HT[1].weight=w[1]; 
		HT[1].parent=2;
		HT[1].lchild=0; 
		HT[1].rchild=0; 
		HT[2].parent=0;
		HT[2].lchild=1;
		HT[2].rchild=0;
		HT[2].weight=w[1];			
	}
	else
	{
		m=2*n-1;
		for (i=1;i<=n;i++)
		{ 
			HT[i].weight=w[i]; 
			HT[i].parent=0;
			HT[i].lchild=0; 
			HT[i].rchild=0; 
		}								
		for (i=n+1;i<=m;i++)
		{
			HT[i].weight=0;  
			HT[i].parent=0;
			HT[i].lchild=0; 
			HT[i].rchild=0; 
		}
		for (i=n+1;i<=m;i++)//建立赫夫曼树
		{
			Select(HT,i-1);//选择parent为0且weight最小的二个节点，其序号分别为s1和s2
			HT[s1].parent=i;
			HT[s2].parent=i;
			HT[i].lchild=s1;
			HT[i].rchild=s2;     
			HT[i].weight =HT[s1].weight+HT[s2].weight;
		}
	}
}