#include <iostream> 
#include <cstdlib>
using namespace std; 

const int MaxValue = 10000; //初始设定的权值最大值 

struct HaffNode //哈夫曼树的结点结构 
{ 
	int weight; //权值 
	int flag;   //标记 
	int parent; //双亲结点下标 
	int leftChild; //左孩子下标 
	int rightChild; //右孩子下标 
};


void Haffman(int weight[], int n, HaffNode haffTree[]) 
	//建立叶结点个数为n权值为weight的哈夫曼树haffTree 
{ 
	int j, m1, m2, x1, x2; 
	//哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 
	for(int i = 0; i < 2 * n - 1 ; i++) { 
		if(i < n) haffTree[i].weight = weight[i]; 
		else haffTree[i].weight = 0; 
		haffTree[i].parent = 0; 
		haffTree[i].flag = 0; 
		haffTree[i].leftChild = -1; 
		haffTree[i].rightChild = -1; 
	} 
	//构造哈夫曼树haffTree的n-1个非叶结点 
	for(int i = 0;i < n-1;i++) { 
		m1 = m2 = MaxValue; 
		x1 = x2 = 0; 
		for(j = 0; j < n+i;j++) { 
			if (haffTree[j].weight < m1 && haffTree[j].flag == 0){ 
				m2 = m1; 
				x2 = x1; 
				m1 = haffTree[j].weight; 
				x1 = j; 
			} 
			else if(haffTree[j].weight < m2 && haffTree[j].flag == 0){ 
				m2 = haffTree[j].weight; 
				x2 = j; 
			} 
		} 
		//将找出的两棵权值最小的子树合并为一棵子树 
		haffTree[x1].parent = n+i; 
		haffTree[x2].parent = n+i; 
		haffTree[x1].flag = 1; 
		haffTree[x2].flag = 1; 
		haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight; 
		haffTree[n+i].leftChild = x1; 
		haffTree[n+i].rightChild = x2; 
	} 
} 

int main(){ 
	int n; 
	cin>>n;
	if(n==1)
	{
	   cout<<0<<endl;
	   return 0;
	}
	long long sum=0;
	int weight[20005]; 
	for(int i=0;i<n;i++)
	   cin>>weight[i];
	HaffNode *myHaffTree = new HaffNode[2*n-1]; 
	Haffman(weight, n, myHaffTree);  
	for(int i = n; i < 2*n-1; i++) {  //非叶子结点的和 
		sum+=myHaffTree[i].weight;
	} 
	printf("%I64d\n",sum);
 	//system("pause");
}

• Re:用哈夫曼树做的竟然错了，哪位大牛找出错哪了（用了_int64) (1935) tanjing 2010-08-23 11:22:34
• Re:用哈夫曼树做的竟然错了，哪位大牛找出错哪了（用了_int64) (1907) lisliz 2011-03-26 22:04:19
  • Re:用哈夫曼树做的竟然错了，哪位大牛找出错哪了（用了_int64) (62) lisliz 2011-03-26 22:07:21