DS二叉树--赫夫曼树解码

题目描述

已知赫夫曼编码算法和程序，在此基础上进行赫夫曼解码

可以增加一个函数：int Decode(const string codestr, char txtstr[]);//输入编码串codestr，输出解码串txtstr

该方法如果解码成功则返回1，解码失败则返回-1，本程序增加宏定义ok表示1，error表示-1

赫夫曼解码算法如下：

定义指针p指向赫夫曼树结点，指针i指向编码串，定义ch逐个读取编码串的字符

初始操作包括读入编码串str，设置p指向根结点，i为0表示指向串首，执行以下循环：

1）取编码串的第i个字符放入ch

2）如果ch是字符0，则p跳转到左孩子；如果ch是字符1，则p跳转到右孩子；如果ch非0非1，表示编码串有错误，报错退出

3）如果p指的结点是叶子，输出解码字符，p跳回根结点，i++，跳步骤1

4）如果p指的结点不是叶子且i未到编码串末尾，i++，跳步骤1

5）如果p指的结点不是叶子且i到达编码串末尾，报错退出

当i到达编码串末尾，解码结束。

输入

第一行先输入n，表示有n个叶子

第二行输入n个权值，权值全是小于1万的正整数

第三行输入n个字母，表示与权值对应的字符

第四行输入k，表示要输入k个编码串

第五行起输入k个编码串

输出

每行输出解码后的字符串，如果解码失败直接输出字符串“error”，不要输出部分解码结果

输入样例1

5
15 4 4 3 2
A B C D E
3
11111
10100001001
00000101100
输出样例1

AAAAA
ABEAD
error

AC代码

#include "bits/stdc++.h"
using namespace std;struct node
{int weight;char data;node *left;node *right; // 左孩子和右孩子node(int w, int d) : weight(w), data(d), left(nullptr), right(nullptr) {}
};
struct compare
{bool operator()(node *left, node *right){if (left->weight == right->weight){return left->data > right->data;}return left->weight > right->weight;}
};
void generatehuffmancodes(node *root, string code, map<char, string> &codes)
{if (root->left == nullptr && root->right == nullptr){codes[root->data] = code; // yiyiduiyingreturn;}if (root->left != nullptr){generatehuffmancodes(root->left, code + '0', codes);}if (root->right != nullptr){generatehuffmancodes(root->right, code + '1', codes);}
}
string decodeHuffman(node *root, const string &codestr)
{ // 解码string decodedString;node *current = root;for (char c : codestr){if (c == '0')current = current->left;else if (c == '1')current = current->right;if (!current->left && !current->right){decodedString += current->data;current = root;}}if (current != root)decodedString = "error";return decodedString;
}
int main()
{int n;cin >> n;vector<int> weights(n + 1);char zifu[n + 1];for (int i = 1; i <= n; i++){cin >> weights[i];}for (int i = 1; i <= n; i++){cin >> zifu[i];}priority_queue<node *, vector<node *>, compare> dui;for (int i = 1; i <= n; i++){node *newnode = new node(weights[i], zifu[i]);dui.push(newnode);}while (dui.size() > 1){                            // 当优先队列中有多个节点时node *left = dui.top();  // 取出权重最小的左节点dui.pop();               // 移除左节点node *right = dui.top(); // 取出权重次小的右节点dui.pop();               // 移除右节点// 创建新内部节点，其权重为左右子节点权重之和node *internalNode = new node(left->weight + right->weight, '*');internalNode->left = left;   // 设置左子节点internalNode->right = right; // 设置右子节点dui.push(internalNode);      // 将新节点插入优先队列}node *root = dui.top(); // 取出哈夫曼树的根节点int t;cin >> t;while (t--){string s, d;cin >> s;d = decodeHuffman(root, s);cout << d << endl;}// map<char, string> huffmanCodes;  // 存储字符和编码的映射// generatehuffmancodes(root, "", huffmanCodes);  // 生成哈夫曼编码// 如果第一个权重为 15，交换两个特定字符的编码// if (weights[1] == 15)// swap(huffmanCodes[char('A' + 2 - 1)], huffmanCodes[char('A' + 3 - 1)]);// 输出每个字符及其哈夫曼编码/*for (int i = 1; i <= n; ++i) {char ch = char('A' + i - 1);  // 计算字符cout << weights[i] << "-" << huffmanCodes[ch] << endl;  // 输出权重和编码}*/return 0;
}