哈夫曼树

1.题目描述：

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

输入：

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

输出：

输出权值。

样例输入：

1 2 2 5 9

样例输出：

#include"iostream"using namespace std;class Tree{public:    int weight;    int left,right,parent;    Tree(int w = 0){        weight = w;        left = 0;        parent = 0;        right = 0;    }    void select(Tree *HT,int n,int &i1,int &i2){        for(int i = 1;i <= n;i++){            if(!HT[i].parent){                i1 = i;                break;            }        }        for(i = 1;i <= n;i++){            if(!HT[i].parent && HT[i1].weight > HT[i].weight){                i1 = i;            }        }        for(i = 1;i <= n;i++){            if(!HT[i].parent && i != i1){                i2 = i;                break;            }        }        for(i = 1;i <= n;i++){            if(!HT[i].parent && i != i1 && HT[i2].weight > HT[i].weight){                i2 = i;            }        }    }    void cinCreate(Tree* &HT,int n){        //初始化        HT = new Tree[2 * n];        for(int i = 1;i <= n;i++){            cin>>HT[i].weight;        }        int m = 2 * n - 1;        //结点个数        //创建哈夫曼树        for(i = n + 1;i <= m;i++){            Tree *newt = new Tree;            int i1 = 1,i2 = 1;            select(HT,i - 1,i1,i2);            cout<
     
      <
      
       <
       
        <
        
         >n;    t->cinCreate(HT,n);    int sum = 0;    t->showx(HT,2 * n - 1,sum);    cout<
         
          <