概念

哈夫曼树是带权路径长度 WPL（Weighted Path Length）最小的二叉树，也称为最优二叉树。

如下图：

它们的带权路径长度分别为：
图a： WPL = 5*2 + 7*2 + 2*2 + 13*2 = 54
图b： WPL = 5*3 + 2*3 + 7*2 + 13*1 = 48
可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)

哈夫曼树的构建

一般按下面步骤循环来构建：
1.排序,直到数组中只有一个数则退出
2.最小两个数加起来，即为非叶子节点，累加到累加器中
3.把最小两个数加起来作为一个新的值保存在数组中，去掉最小两个值，跳回第一步

如下图：

其中还有个规律，结合算法描述仔细观察发现最小带权路径长度为非叶子结点的和
如上图中 WPL= 27 + 14 + 7 = 48

本周问题 A: 哈夫曼树

题目描述
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出
输出权值。

我的代码

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int t[1010], sum = 0, i;
        for(i = 0; i < n; i++)
            scanf("%d", &t[i]);
        for(i = 0; i < n-1; i++)
         //循环，直到数组中只有一个数则退出
        {
            sort(t + i, t+n); //排序
            sum += t[i] + t[i+1];
               //最小两个数加起来，即为非叶子节点，累加到累加器中
            t[i+1] += t[i];
               //把最小两个数加起来作为一个新的值保存在数组中，去掉最小两个值，跳回第一步
        }
        printf("%d\n", sum);
    }
    return 0;
}