c＋＋构建哈夫曼树及译码并逐行注释

C++构建哈夫曼树通常涉及以下几个步骤，这里我们使用优先队列和贪心算法： ```cpp #include <iostream> #include <queue> #include <vector> #include <unordered_map> using namespace std; // 定义节点结构体，包含字符和频率 struct Node { char data; int freq; Node* left = nullptr; Node* right = nullptr; }; // 创建新节点函数 Node* createNode(char data, int freq) { Node* newNode = new Node(); newNode->data = data; newNode->freq = freq; return newNode; } // 用于存储节点及其频率的结构体，以及优先队列操作 struct Compare { bool operator()(const pair<Node*, int>& a, const pair<Node*, int>& b) { return a.second > b.second; // 按频率降序排序 } }; // 构建哈夫曼树 vector<Node*> buildHuffmanTree(vector<int>& freqs) { priority_queue<pair<Node*, int>, vector<pair<Node*, int>>, Compare> pq; for (int freq : freqs) { pq.push({createNode('\0', freq), freq}); // 初始化队列，空字符作为默认值 } while (pq.size() > 1) { // 当队列大小大于1时，继续构建 Node* left = pq.top().first; pq.pop(); // 弹出左节点 Node* right = pq.top().first; pq.pop(); // 弹出右节点 // 合并左右节点，并更新新的节点频率 Node* newNode = createNode('\0', left->freq + right->freq); newNode->left = left; newNode->right = right; // 将新节点加入队列 pq.push({newNode, newNode->freq}); } // 最后队列剩下的就是根节点 return {pq.top().first}; } // 哈夫曼编码，对给定的字符进行编码 string huffmanCode(Node* root, char data, string code) { if (!root || root->data == data) { return code; } if (root->left && root->left->data == data) { return huffmanCode(root->left, data, code + "0"); } else { return huffmanCode(root->right, data, code + "1"); } } // 译码函数，接收编码和构建好的哈夫曼树 void decode(const vector<Node*>& tree, const string& encoded, string decoded) { Node* currentNode = tree[0]; // 从根节点开始 for (char bit : encoded) { if (bit == '0') { currentNode = currentNode->left; } else { currentNode = currentNode->right; } // 如果到达叶子节点，则添加字符到解码结果 if (!currentNode->left && !currentNode->right) { decoded += currentNode->data; currentNode = tree[0]; // 继续解码下一个字符 } } } int main() { // 示例：输入字符频率向量 vector<int> freqs = {9, 4, 3, 2, 5}; // {'e': 9, 't': 4, 'a': 3, 'o': 2, 'i': 5} vector<Node*> tree = buildHuffmanTree(freqs); // 对每个字符进行编码 map<char, string> codes; for (auto& node : tree) { codes[node->data] = huffmanCode(tree[0], node->data, ""); // 假设根节点为整个树 } // 测试编码和解码 string encoded = codes['e']; // 编码 'e' string decoded = ""; decode(tree, encoded, decoded); cout << "Encoded: " << encoded << endl; cout << "Decoded: " << decoded << endl; // 清理内存 for (auto& node : tree) { delete node; } return 0; } ```