HuffmanTree

1、给定数字序列，构造哈夫曼树，输出所有结点的值与权值的乘积之和

所有结点的值与权值的乘积之和可以转变为求解除根结点外其他所有结点的权值之和

不需要维系树的关系，只需要根据哈夫曼树构造的方法，不断选取两个值最小的结点进行合并（数组维系），累加，直到数组中仅剩余一个数字，即根结点。

题目

示例代码：

#include <iostream>

usingnamespacestd;

intMin(int*arr,int&n)

{

    inti,k,min;

    min=arr[0];

    k=0;

    for(i=0;i<n;i++)

    {

        if(arr[i]<min)

          {

            min=arr[i];

            k=i;

          }

    }

    arr[k]=arr[--n];

    returnmin;

}

intmain()

{

    intn;

    while(cin>>n)

    {

        intb[1000];

        inti;

        for(i=0;i<n;i++)

            cin>>b[i];

        intsum,wgt;

        sum=0;

        wgt=0;

        while(n>1)

        {

            sum=Min(b,n)+Min(b,n);

            wgt+=sum;

            b[n++]=sum;

        }

        cout<<wgt<<endl;

    }

}