#include iostream#include vector#include queue#include string#include functionalstruct TreeNode char ch; int freq; TreeNode left right; TreeNodeint f = 0 freqf leftNULL rightNULL ;st

#include #include #include #include #include

struct TreeNode { char ch; int freq; TreeNode *left, *right; TreeNode(char c = '\0', int f = 0) : ch(c), freq(f), left(nullptr), right(nullptr) {} };

struct CodeInfo { char ch; std::string code; };

void Init(TreeNode* nodes[], int n) { for (int i = 0; i < n; ++i) { char ch; int freq; std::cin >> ch >> freq; nodes[i] = new TreeNode(ch, freq); } }

TreeNode* BuildHuffmanTree(TreeNode* nodes[], int n) { auto cmp = [](TreeNode* a, TreeNode* b) { return a->freq > b->freq; }; std::priority_queue<TreeNode*, std::vector<TreeNode*>, decltype(cmp)> pq(cmp); for (int i = 0; i < n; ++i) { pq.push(nodes[i]); } while (pq.size() > 1) { TreeNode* left = pq.top(); pq.pop(); TreeNode* right = pq.top(); pq.pop(); TreeNode* parent = new TreeNode('\0', left->freq + right->freq); parent->left = left; parent->right = right; pq.push(parent); } return pq.top(); }

void GetCode(TreeNode* root, std::string code, std::vector& codes) { if (root == nullptr) { return; } if (root->ch != '\0') { CodeInfo info; info.ch = root->ch; info.code = code; codes.push_back(info); } GetCode(root->left, code + "0", codes); GetCode(root->right, code + "1", codes); }

std::string Decode(TreeNode* root, const std::string& code) { TreeNode* cur = root; std::string result; for (char c : code) { if (c == '0') { cur = cur->left; } else { cur = cur->right; } if (cur->ch != '\0') { result.push_back(cur->ch); cur = root; } } return result; }

int main() { int n; std::cin >> n; TreeNode* nodes[n]; Init(nodes, n); TreeNode* root = BuildHuffmanTree(nodes, n); std::vector codes; GetCode(root, "", codes); for (auto code : codes) { std::cout << code.ch << ' ' << code.code << '\n'; } std::string encoded; std::cin >> encoded; std::cout << Decode(root, encoded) << '\n'; return 0;