PTA数据结构哈夫曼树与哈夫曼编码⽂章⽬录题⽬描述题⽬背景:介绍什么是哈夫曼树和哈夫曼编码, 不影响做题哈夫曼树(Huffman Tree)⼜称最优⼆叉树，是⼀种带权路径长度最短的⼆叉树。
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。
树的路径长度是从树在数据通信中，需要将传送的⽂字转换成⼆进制的字符串，⽤0，1码的不同排列来表⽰字符。
例如，需传送的报⽂为“AFTER DATA EAR ARE ART AREA”，这⾥⽤到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。
现要为使不等长编码为前缀编码(即要求⼀个字符的编码不能是另⼀个字符编码的前缀)，可⽤字符集中的每个字符作为叶⼦结点⽣成⼀棵编码⼆叉树，为了获得传送报⽂的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使⽤本题要求从键盘输⼊若⼲电⽂所⽤符号及其出现的频率，然后构造哈夫曼树，从⽽输出哈夫曼编码。
注意：为了保证得到唯⼀的哈夫曼树，本题规定在构造哈夫曼树时，左孩⼦结点权值不⼤于右孩⼦结点权值。
如权值相等，则先选优先级队列中先出队的节点。
编码时，左分⽀取“0”，右分⽀取“1”。
输⼊格式输⼊有3⾏第1⾏：符号个数n（2～20）第2⾏：⼀个不含空格的字符串。
记录着本题的符号表。
我们约定符号都是单个的⼩写英⽂字母，且从字符‘a’开始顺序出现。
也就是说，如果 n 为 2 ，则符号表为 ab；如果 n 为 6，则符号为 abcdef；以此类推。
第3⾏：各符号出现频率（⽤乘以100后的整数），⽤空格分隔。
输出格式先输出构造的哈夫曼树带权路径长度。
接下来输出n⾏，每⾏是⼀个字符和该字符对应的哈夫曼编码。
字符按字典顺序输出。
字符和哈夫曼编码之间以冒号分隔。
样例输⼊:8abcdefgh5 29 7 8 14 23 3 11输出:271a:0001b:10c:1110d:1111e:110f:01g:0000h:001⼀点说明关于题⽬描述中的"如权值相等，则先选优先级队列中先出队的节点"可以参考上图, 权值为7的节点选择了权值为8的叶⼦节点, ⽽不是权值为8的⼦树感觉题⽬想表达的意思是, 若权值相等，则先选优先级队列中先⼊队的节点(如有错误, 望指正)想法利⽤优先队列维护⼩根堆(因为建树时,要选两个权值最⼩的),利⽤哈夫曼算法建树,再根据所建哈夫曼树,利⽤深搜回溯,得到各个字符的哈夫曼编码和树的带权路径长度实现#include <cstdio>#include <iostream>#include <string>#include <queue>#include <vector>using namespace std;struct node{int weight;char ch = 'z' + 1; // 这样在优先队列⾃定义排序时, 可以做到权值相等,则先选优先级队列中先出队的节点node *lchild, *rchild;};// ⾃定义优先队列的排序⽅式, 权值⼩优先, 权值相等,则先选优先级队列中先出队的节点struct cmp{bool operator() (node* a, node* b){if(a->weight == b->weight)return a->ch > b->ch;return a->weight > b->weight;}};int n, WPL; // n:结点数 WPL:树的带权路径长度(⾮叶⼦节点的权值和)string str;priority_queue<node, vector<node*>, cmp> q; //vector<char> ans[100]; // 存放哈夫曼编码vector<char> code; // ⽤于深搜得到哈夫曼编码node* createTree() // 建⽴哈夫曼树{node* r;while(!q.empty()){if(q.size() == 1){node* a = q.top();q.pop();r = a;break;}else{node* a = q.top();q.pop();node* b = q.top();q.pop();node* c = new node();c->weight = a->weight + b->weight;c->lchild = a;c->rchild = b;r = c;q.push(c);}}return r;}void print() // 输出前缀编码{cout << WPL << endl;for(int i=0; i<n; i++){cout << str[i] << ":";int index = str[i] - 'a';for(int j=0; j<ans[index].size(); j++)cout << ans[index][j];cout << endl;}}void dfs(node* root) // 深搜回溯得到哈夫曼编码和树的带权路径长度{if(root->lchild != NULL || root->rchild != NULL)WPL += root->weight; // WPL即⾮叶⼦节点的权值之和if(root->lchild == NULL && root->rchild == NULL){char ch = root->ch;ans[ch-'a'] = code; // 根据叶⼦节点的字符, 判断是谁的哈夫曼编码return;}if(root->lchild != NULL){code.push_back('0');dfs(root->lchild);code.pop_back(); // 回溯}if(root->rchild != NULL){code.push_back('1');dfs(root->rchild);code.pop_back(); // 回溯}return;}int main(){cin >> n;cin >> str;for(int i=0; i<n; i++) // 读⼊各节点的权值, 利⽤优先队列维护⼩根堆, 便于建树{node* temp = new node(); // 不要忘记给指针分配空间cin >> temp->weight;temp->ch = str[i];temp->lchild = temp->rchild = NULL;q.push(temp);}node* root = createTree(); // 建⽴哈夫曼树dfs(root); // 回溯得到哈夫曼编码及WPLprint();return 0;}。
