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⾏，每⾏是⼀个字符和该字符对应的哈夫曼编码。字符按字典顺序输出。字符和哈夫曼编码之间以冒号分隔。
样例
输⼊:
8
abcdefgh
5 29 7 8 14 23 3 11
输出:
271
a:0001
b:10
c:1110
d:1111
e:110
f:01
g:0000
h: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;
}
字符串长度1是什么意思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); // 回溯得到哈夫曼编码及WPL
print();
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。