> #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) (62) lisliz 2011-03-26 22:07:21