733&767.哈夫曼树

问题描述 假设用于通信的电文由ｎ个字符组成，字符在电文中出现的频度（权值）为w1,w2,…,wn，试根据该权值序列构造哈夫曼树，并计算该树的带权路径长度。

输入说明 第１行为ｎ的值，第２行为ｎ个整数，表示字符的出现频度。

输出说明 输出所构造哈夫曼树的带权路径长度。

输入样例

8 
7 19 2 6 32 3 21 10

输出样例

261

#include
const int MAX_VAL = 10000;
struct HTNode
{int weight;int parent, lchild, rchild;
};
void Select(HTNode*& HT, int range, int& l, int& r)
//找两个最小值，把下标传回l和r 
{int minimum1 = MAX_VAL, minimum2 = MAX_VAL;//先找最小值1for (int i = 1; i <= range; i++){if (HT[i].weight < minimum1 && HT[i].parent == 0){minimum1 = HT[i].weight;l = i;}}//再找最小值2for (int i = 1; i <= range; i++){if (HT[i].weight < minimum2 && i != l && HT[i].parent == 0){minimum2 = HT[i].weight;r = i;}}
}
int CreateHuffmanTree(HTNode*& HT, int n)
//构造huffman树，返回WPL
{int WPL = 0;if (n <= 1) return 0;int m = 2 * n - 1;HT = new HTNode[m + 1];//对每个单元的所有成员进行初始化 for (int i = 1; i <= m; i++){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (int i = 1; i <= n; i++){std::cin >> HT[i].weight;}//叶子结点存完之后后面的单元用于存Huffman树处理过程的单元 for (int i = n + 1; i <= m; i++){int s1 = 0, s2 = 0;//从HT的1~i-1选双亲域为0权值最小两个结点，得到下标分别是s1，s2Select(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;WPL += HT[i].weight;}return WPL;
}
int main()
{int n;HTNode* HT = NULL;std::cin >> n;std::cout<