C++实现哈夫曼树算法
前言
哈夫曼树(Huffman Tree)是一种经典的数据结构,用于有效地压缩和解压数据。它通过根据数据中每个字符的出现频率构建一棵具有最小编码长度的二叉树,从而实现高效的压缩和解压操作。在本文中,我们将使用C++来实现哈夫曼树算法,并对代码进行详细的分析和解释。
代码实现
#include#include #include using namespace std; // 哈夫曼树的结点类 class Node { public: char data; int freq; Node* left; Node* right; Node(char data, int freq) { this->data = data; this->freq = freq; left = right = nullptr; } }; // 用于比较两个结点的优先级 struct compare { bool operator()(Node* l, Node* r) { return l->freq > r->freq; } }; // 构建哈夫曼树 Node* buildHuffmanTree(unordered_map & freqMap) { priority_queue , compare> minHeap; // 根据频率构建最小堆 for (auto& pair : freqMap) { Node* newNode = new Node(pair.first, pair.second); minHeap.push(newNode); } // 从最小堆中构建哈夫曼树 while (minHeap.size() > 1) { Node* left = minHeap.top(); minHeap.pop(); Node* right = minHeap.top(); minHeap.pop(); Node* newNode = new Node('$', left->freq + right->freq); newNode->left = left; newNode->right = right; minHeap.push(newNode); } return minHeap.top(); } // 生成哈夫曼编码 void getHuffmanCodes(Node* root, string code, unordered_map & huffmanCodes) { if (root == nullptr) return; // 叶子结点 if (!root->left && !root->right) { huffmanCodes[root->data] = code; } getHuffmanCodes(root->left, code + "0", huffmanCodes); getHuffmanCodes(root->right, code + "1", huffmanCodes); } // 压缩数据 string compress(string data) { unordered_map freqMap; for (char c : data) { freqMap[c]++; } Node* root = buildHuffmanTree(freqMap); unordered_map huffmanCodes; getHuffmanCodes(root, "", huffmanCodes); string compressedData = ""; for (char c : data) { compressedData += huffmanCodes[c]; } return compressedData; } // 解压数据 string decompress(string compressedData, Node* root) { string decompressedData = ""; Node* curr = root; for (char bit : compressedData) { if (bit == '0') curr = curr->left; else curr = curr->right; // 叶子结点 if (!curr->left && !curr->right) { decompressedData += curr->data; curr = root; } } return decompressedData; } int main() { string data = "Hello, World!"; cout << "原始数据: " << data << endl; string compressedData = compress(data); cout << "压缩后的数据: " << compressedData << endl; string decompressedData = decompress(compressedData, root); cout << "解压后的数据: " << decompressedData << endl; return 0; }
代码解释
上述代码首先定义了一个Node类,用于表示哈夫曼树的结点。结点包含字符数据、出现频率以及左右子树的指针。接下来,通过重载compare运算符,我们可以将结点按照频率的大小进行优先级排序。
buildHuffmanTree函数用于构建哈夫曼树。它首先根据字符出现频率构建一个最小堆(优先队列),然后从最小堆中选择两个频率最低的结点合并,直到只剩下一个根结点。
getHuffmanCodes函数用于生成每个字符的哈夫曼编码。它采用深度优先搜索的方式遍历哈夫曼树,当遍历到叶子结点时,将当前路径作为该字符的编码。
compress函数通过使用哈夫曼编码来压缩输入的数据。它首先统计每个字符的频率,并根据频率构建哈夫曼树。然后,使用哈夫曼编码替代原始数据中的每个字符,生成压缩后的数据。
decompress函数用于解压压缩后的数据。它从哈夫曼树的根结点开始,根据压缩数据的每个bit选择相应的左右子树,直到遇到叶子结点。一旦遇到叶子结点,将对应字符添加到解压后的数据中,并重置当前结点为根结点。
最后,在main函数中,我们演示了如何使用上述函数来压缩和解压数据。
总结
通过上述的C++代码实现,我们成功地实现了哈夫曼树的算法。该算法可以对字节数据进行高效的压缩和解压,可以应用于许多领域,如文件压缩、网络传输等。通过深入研究和理解哈夫曼树的原理和实现细节,我们可以进一步优化算法,提高压缩效率和解压速度。