地址在这：http://ac.jobdu.com/problem.php?id=1172
题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37
我用java做出来了。但是感觉效率不高。
有没有不建树的做法？？
------解决方案--------------------
- C/C++ code
#include<iostream>#include<cstdio>using namespace std;#include<stdlib.h>#include<memory.h>typedef struct{ int weight; int flag; int parent,lchild,rchild;}Node,*HuffmanTree; //动态分配数组存储赫夫曼树 int L,length;void Select(HuffmanTree HT, int num, int &s1, int &s2){ //s1是最小值，s2是次小值 int i,minx = 1<<30; int mminx = 1<<30; for(i = 1; i <= num; ++i) { if(HT[i].weight < minx && !HT[i].flag) { mminx = minx; s2 = s1; minx = HT[i].weight; s1 = i; } else if(HT[i].weight < mminx && !HT[i].flag) { mminx = HT[i].weight; s2 = i; } } HT[s1].flag = HT[s2].flag = -1;} void AllLength(HuffmanTree HT, int m){ int m1,m2; length++; if (!HT[m].lchild && !HT[m].rchild) { L += HT[m].weight * (length-1); } else { m1 = HT[m].lchild; AllLength(HT,m1); length--; m2 = HT[m].rchild; AllLength(HT,m2); length--; }} void HuffmanCoding(HuffmanTree &HT,int *w, int n,int m){ int i, s1,s2; //w存放n个字符的权值（均>0）,构造赫夫曼树HT HT = (HuffmanTree)malloc((m+1)*sizeof(Node)); //0号单元未用 HuffmanTree p = HT + 1; for(i = 1; i <= n; ++i,++p) { p->weight = w[i]; p->parent = p->lchild = p->rchild = p->flag = 0; } for(i = n+1; i <= m; ++i,++p) { p->weight = p->parent = p->lchild = p->rchild = p->flag = 0; } for(i = n + 1; i <= m; ++i) { //建赫夫曼树 //在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。 Select(HT, i-1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }} int main(void){ int i,n,m; int w[1010]; while(scanf("%d",&n)!=EOF) { m = 2 * n - 1; HuffmanTree T; for(i = 1; i <= n; ++i) { scanf("%d",&w[i]); } HuffmanCoding(T,w,n,m); length = L = 0; AllLength(T,m); free(T); printf("%d\n",L); } return 0;}