756
九度題目1172：哈夫曼樹
題目1172：哈夫曼樹 時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：4366
解決：1827
題目描述：
哈夫曼樹，第一行輸入一個數n，表示葉結點的個數。需要用這些葉結點生成哈夫曼樹，根據哈夫曼樹的概念，這些結點有權值，即weight，題
目需要輸出所有結點的值與權值的乘積之和。
輸入：
輸入有多組數據。
每組第一行輸入一個數n，接著輸入n個葉節點（葉節點權值不超過100，2<=n<=1000）。
輸出：
輸出權值。
樣例輸入：
5
1 2 2 5 9
樣例輸出：
37
來源：
2010年北京郵電大學計算機研究生機試真題
構建一顆哈弗曼樹的方法：
1.根據給定的N{W1,W2,...,Wn}個權值構成N棵二叉樹的集合F={T1,T2,...,Tn},其中每課二叉樹Ti隻有一個帶權值為Wi的根節點，其左右子樹為
空。
2.在F中選取兩棵根節點最小的樹作為左右子樹構造一顆新的二叉樹，且置新的二叉樹的根節點的權值為其左右子樹上根節點的權值之和。
3.在F中刪除這兩科樹，同時將新得到的二叉樹加入到F中。
4.重複2和3，直到F隻含一棵樹為止，這棵樹便是哈弗曼樹。
思路：所有的非葉子節點之和就是答案
AC代碼：（沒有構建樹，僅僅模擬哈弗曼數組合節點）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1100];
int main()
{
int i,j,n,m,num,sum;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
i=1;sum=0;
while(i<n)
{
sort(a+i-1,a+n);//每次都要重新排序,因為生成了新的節點
num=a[i]+a[i-1];//計算父親
sum+=num;//非葉子節點之和
a[i]=a[i]+a[i-1];//將小樹生成新的節點
i++;
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 12:56:20