构造哈夫曼树，计算WPL。 函数接口定义： void CreateHTree(); void CreateHCode(); 裁判测试程序样例： #include <iostream> #include <queue> #include <vector> #include <string> #include <map> using namespace std; #define MAX 101 int n; struct HTreeNode //哈夫曼树结点类型 { char data; //字符 int weight; //权值 int parent; //双亲的位置 int lchild; //左孩子的位置 int rchild; //右孩子的位置 }; HTreeNode ht[MAX]; //哈夫曼树 map<char,string> htcode; //哈夫曼编码 struct NodeType //优先队列结点类型 { int no; //对应哈夫曼树ht中的位置 char data; //字符 int weight; //权值 bool operator<(const NodeType &s) const { //用于创建小根堆 return s.weight<weight; } }; void CreateHTree(); void CreateHCode(); int WPL() //求WPL { int wps=0; for (int i=0;i<n;i++) wps+=ht[i].weight*htcode[ht[i].data].size(); return wps; } int main() { cin >> n; for(int i=0;i<n;i++) { cin >> ht[i].data >> ht[i].weight; } CreateHTree(); //建立哈夫曼树 CreateHCode(); //求哈夫曼编码 printf("WPL=%d",WPL()); return 0; } /* 请在这里填写答案 */ 输入样例： 第一行输入一个数n(1<n<100)，表示叶子节点的个数，接下去输入n行，每行输入一个字符和一个整数，表示每个节点表示的字符和权值。 5 A 8 B 10 C 2 D 11 E 1 输出样例： 输出WPL。 WPL=67

以下是实现代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;

#define MAX 101

int n;

struct HTreeNode                //哈夫曼树结点类型
{
    char data;                    //字符
    int weight;                    //权值
    int parent;                    //双亲的位置
    int lchild;                    //左孩子的位置
    int rchild;                    //右孩子的位置
};

HTreeNode ht[MAX];                //哈夫曼树
map<char, string> htcode;            //哈夫曼编码

struct NodeType        //优先队列结点类型
{
    int no;                //对应哈夫曼树ht中的位置
    char data;            //字符
    int  weight;        //权值
    bool operator<(const NodeType& s) const
    {                    //用于创建小根堆
        return s.weight < weight;
    }
};

void CreateHTree()
{
    priority_queue<NodeType> q;
    for (int i = 0; i < n; i++) {
        NodeType node = { i, ht[i].data, ht[i].weight };
        q.push(node);
    }

    while (q.size() > 1) {
        NodeType node1 = q.top();
        q.pop();
        NodeType node2 = q.top();
        q.pop();

        int i = node1.no;
        int j = node2.no;
        ht[i].parent = ht[j].parent = n;
        ht[n].lchild = i;
        ht[n].rchild = j;
        ht[n].weight = node1.weight + node2.weight;
        q.push({ n++, ' ', node1.weight + node2.weight });
    }
}

void CreateHCode()
{
    for (int i = 0; i < n; i++) {
        string code;
        int p = ht[i].parent;
        int c = i;
        while (p != -1) {
            if (ht[p].lchild == c) {
                code = "0" + code;
            } else {
                code = "1" + code;
            }
            c = p;
            p = ht[p].parent;
        }
        htcode[ht[i].data] = code;
    }
}

int WPL()                //求WPL
{
    int wps = 0;
    for (int i = 0; i < n; i++) {
        wps += ht[i].weight * htcode[ht[i].data].size();
    }
    return wps;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ht[i].data >> ht[i].weight;
        ht[i].parent = -1;
        ht[i].lchild = -1;
        ht[i].rchild = -1;
    }

    CreateHTree();                    //建立哈夫曼树
    CreateHCode();                    //求哈夫曼编码

    printf("WPL=%d", WPL());
    return 0;
}