#include <string.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int a[40002];
bool visit[40002];

void Haffman(int n)
{
/*
6
3 6 1 4 2 5
3
8 5 8
7
2 3 8 5 8 3 3
1 
355
*/
	memset(visit,0,sizeof(visit));
	int num = n;
	int i,j,min1,min2,index1,index2;
	
	for(i=0;i<n-1;i++)//创建n-1个新结点 
	{
		min1 = min2 = 999999;
		for(j=0;j<num;j++) 
		{
			if(!visit[j])
			{
				if(a[j]<min1)
				{
					min2 = min1;
					index2 = index1;
					min1 = a[j];
					index1 = j;		
				}
				else if(a[j]<min2)
				{
					index2 = j;
					min2 = a[j];
				}									
			}	
		} 
		visit[index1] = visit[index2] = 1;
	//	printf("index1=%d,min1=%d,index2=%d,min2=%d\n",index1,min1,index2,min2);//找到最小的两个 	
		a[num] = min1 + min2;
		num++;//创建新结点
	}   
	
	long long sum =0;
	for(i=n;i<num;i++)
		sum += a[i];
	printf("%lld\n",sum);
}

int main()
{
	int i,n;
	while(scanf("%d",&n)!=EOF)
	{
		
		for(i=0;i<n;i++)
				scanf("%d",&a[i]);		
		if(n==1) printf("0\n");	
		else	Haffman(n);	
	}

		
		
//	system("pause");
	return 0;	
}

• Re:用一个数组代替哈夫曼树，哪里错误，测试数据都正确啊，，，，，，求大神 (1292) ZQLac 2016-07-29 17:36:56
• Re:用一个数组代替哈夫曼树，哪里错误，测试数据都正确啊，，，，，，求大神 (1292) huanmx 2017-11-23 18:13:03