建立哈夫曼树，计算树的带权路径。

#include <iostream>
#include <queue>
#include <malloc.h>
using namespace std;
typedef struct HTNode
{
	int weight, parent, lchild, rchild;
	int flag;
	friend bool operator <(HTNode a, HTNode b)
	{
		if (a.weight!=b.weight)
			return a.weight > b.weight;
		return a.flag > b.flag;
	}
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
int CreatTree(HuffmanTree &HT, int n)//构建哈夫曼树
{
	int i, m;
	m = 2 * n - 1;
    HuffmanTree p;
	HTNode s1, s2;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
	p = (HuffmanTree)malloc(sizeof(HTNode));
    p = HT;
	priority_queue<HTNode>q;
	for (p++, i=1; i<=n; i++, p++)
	{
	   scanf("%d", &p->weight);
		p->lchild =  p->rchild = p->parent = 0;
		p->flag = i;
		q.push(*p);
	}
	for ( ; i<=m; i++, p++)
	{
        p->lchild = p->rchild = p->weight = p->parent = 0;
		p->flag = i;
	}
	for (i=n+1; i<=m; i++)
	{
		s1 = q.top();
		q.pop();
		s2 = q.top();
		q.pop();
		
		HT[s1.flag].parent = i;
		HT[s2.flag].parent = i;
		HT[i].lchild = s1.flag;
		HT[i].rchild = s2.flag;
		HT[i].weight = s1.weight + s2.weight;
		q.push(HT[i]);
	}
	return 0;
}
int Coding(HuffmanTree &HT, int n)//哈弗曼编码
{
	int i, m, c, w, f;
	long long sum;
	m = 2 * n - 1;
	sum = 0;
	for (i=1; i<=n; i++)
	{
		w = 0;
		for (c=i, f=HT[c].parent; f!=0; c=f, f=HT[f].parent)//带权路径长度
         w++;
		sum += w * HT[i].weight;//树的带权路径长度
	}
	return sum;
}
int main()
{
	int n, num;
	long long sum;
	scanf("%d", &num);
	while (num--)
	{
       HuffmanTree HT;
	   scanf("%d", &n);
	   CreatTree(HT, n);
	   sum = Coding(HT, n);
	   printf("%lld\n", sum);
	}
	return 0;
}