题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37
这个题可以建树也可以不建树。
不建树比较容易。首先要明确，题目要求输出的乘积之和，其实就是哈夫曼树中去除叶节点之外，其他节点的值的和。比如
题目要求意思是 1*4+2*4+2*3+5*2+9*1=37
其实可以直接 3+5+10+19=37
明白了这一点，就可以直接排序，每次取数组中最小的两个数，然后相加，并累加，最终就得到了输出。代码如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int main(){ 5 int n; 6 int result = 0; //表示最后的结果，即3+5+10+19 7 int node[1000] = { 0 }; 8 scanf("%d", &n); 9 for(int i=0; i<n; i++){ 10 scanf("%d", &node[i]); 11 } 12 for (int i = 0; i < n - 1; i++){ 13 int sum = 0; //临时存储最小的两个数的和 14 sort(node + i, node + n); 15 sum = node[i] + node[i + 1]; 16 result += sum; 17 node[i + 1] = sum; 18 } 19 printf("%d ", result); 20 return 0; 21 }
建哈夫曼树的话，其实也是每次计算最小的两个，然后把他们的和累加，建树反而比较麻烦，最终的计算也是 3+5+10+19=37。代码如下：
1 #include<iostream> 2 using namespace std; 3 struct huffman{ 4 int weight; 5 int parent, lchild, rchild; 6 }; 7 int main(){ 8 struct huffman node[2000]; 9 int n, result = 0; 10 int x1, x2, m1 = -1, m2 = -1; //x1,x2分别表示最小和次小的权值，m1,m2分别表示最小和次小的节点编号 11 scanf("%d", &n); 12 for (int i = 0; i < 2*n; i++){ //只需要初始化前2n个结构体就行，因为节点就2*n-1个 13 //二叉树中，叶子节点的个数比度为2的节点的个数多1个 14 node[i].parent = node[i].lchild = node[i].rchild = -1; //初始化 15 } 16 for (int i = 0; i < n; i++){ 17 scanf("%d", &node[i].weight); 18 } 19 for (int i = 0; i < n - 1; i++){ 20 x1 = 101, x2 = 101; //注意每次循环前都要重新赋值，这里我开始就弄错了 21 for (int j = 0; j < n + i; j++){ //每次都会增加一个节点，在没有parent的节点中找最小的和次小的 22 if (node[j].weight < x1 && node[j].parent == -1){ //如果当前weight比最小的小，就替换，同时更新次小的 23 x2 = x1; 24 m2 = m1; 25 x1 = node[j].weight; 26 m1 = j; 27 } 28 else if (node[j].weight < x2 && node[j].parent == -1){ 29 x2 = node[j].weight; 30 m2 = j; 31 } 32 }//经过这次循环，找到了最小和次小 33 node[n + i].weight = x1 + x2; //这五行是建树，将最小的两个相加，增加新节点 34 node[n + i].lchild = m1; 35 node[n + i].rchild = m2; 36 node[m1].parent = n + i; 37 node[m2].parent = n + i; 38 result += node[n + i].weight; 39 } 40 printf("%d ", result); 41 return 0; 42 }