DS二叉树——Huffman编码与解码
DS二叉树——Huffman编码与解码
题目描述
1、问题描述
给定n个字符及其对应的权值，构造Huffman树，并进行huffman编码和译（解）码。
构造Huffman树时，要求左子树根的权值小于、等于右子树根的权值。
进行Huffman编码时，假定Huffman树的左分支上编码为‘0’，右分支上编码为‘1’。
2、算法
构造Huffman树算法：
⑴根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个权值为wi的根结点。
⑵在F中选取两棵根结点的权值最小的树，作为左、右子树构造一棵新的二叉树，且置其根结点的权值为其左、右子树权值之和。
⑶在F中删除这两棵树，同时将新得到的二叉树加入F中。
(4)重复⑵,⑶，直到F只含一棵树为止。
3、Huffman编码算法：
⑴从Huffman树的每一个叶子结点开始。
⑵依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码‘0’，否则得到编码‘1’，先得到的编码放在后面。
⑶直到到达根结点，编码序列即为该叶子结点对应的Huffman编码。
4、Huffman译（解）码算法：
⑴指针指向Huffman树的根结点，取第一个Huffman码。
⑵如果Huffman码为‘0’，将指针指向当前结点的左子树的根结点；如果Huffman码为‘1’，将指针指向当前结点的右子树的根结点。
⑶如果指针指向的当前结点为叶子结点，则输出叶子结点对应的字符；否则，取下一个Huffman码，并返回⑵。
⑷如果Huffman码序列未结束，则返回⑴继续译码。
输入
第一行测试次数
第2行：第一组测试数据的字符个数n，后跟n个字符
第3行：第一组测试数据的字符权重
待编码的字符串s1
编码串s2
其它组测试数据类推
输出
第一行~第n行,第一组测试数据各字符编码值
第n+1行，串s1的编码值
第n+2行，串s2的解码值，若解码不成功，输出error!
其它组测试数据类推
输入样例
2
5 A B C D E
15 4 4 3 2
ABDEC
00000101100
4 A B C D
7 5 2 4
ABAD
1110110
输出样例
A :1
B :010
C :011
D :001
E :000
1010001000011
error!
A :0
B :10
C :110
D :111
0100111
DAC
题解
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>using namespace std;class Node {
public:char ch;int index;int freq;int son[2];string code;Node() {ch = 0;freq = 1e9;son[0] = son[1] = -1;}bool operator>(const Node &a) const {if (freq == a.freq) return index > a.index;return freq > a.freq;}
};void dfs(int index, vector<Node> &nodes) {if (index == -1) return;for (int i = 0; i <= 1; i++) {if (nodes[index].son[i] != -1) {nodes[nodes[index].son[i]].code = nodes[index].code + to_string(i);dfs(nodes[index].son[i], nodes);}}
}int main() {int t;cin >> t;while (t--) {vector<Node> tree;int n;cin >> n;for (int i = 0; i < n; i++) {Node node;cin >> node.ch;node.index = i;tree.push_back(node);}for (int i = 0; i < n; i++) cin >> tree[i].freq;priority_queue<Node, vector<Node>, greater<>> pq;for (int i = 0; i < n; i++) pq.push(tree[i]);while (pq.size() > 1) {Node node1 = pq.top();pq.pop();Node node2 = pq.top();pq.pop();Node node;node.freq = node1.freq + node2.freq;node.son[0] = node1.index;node.son[1] = node2.index;node.index = tree.size();tree.push_back(node);pq.push(node);}dfs(tree.size() - 1, tree);unordered_map<char, string> mp;for (int i = 0; i < n; i++) {cout << tree[i].ch << " :" << tree[i].code << endl;mp[tree[i].ch] = tree[i].code;}string str;cin >> str;for (int i = 0; i < str.size(); i++) cout << mp[str[i]];cout << endl;cin >> str;string ans;int pos = 0;int cur = tree.size() - 1;while (pos < str.size()) {if (str[pos] == '0') cur = tree[cur].son[0];else cur = tree[cur].son[1];if (tree[cur].son[0] == -1 && tree[cur].son[1] == -1) {ans += tree[cur].ch;cur = tree.size() - 1;}pos++;}if (cur != tree.size() - 1) cout << "error!" << endl;else cout << ans << endl;}return 0;
}