Scribd
Upload
19 views2 pages

C++ Huffman Coding Implementation

This document contains C++ code to implement a Huffman coding tree algorithm. It defines a HuffmanNode struct to represent nodes in the tree, with character, frequency, and left/right child pointers. It also defines functions to build the Huffman tree from a string by calculating character frequencies, and to generate Huffman codes by traversing the tree. The main function calls these to build the tree for a sample string and output the generated codes.

Uploaded by

fuyf
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

C++ Huffman Coding Implementation

This document contains C++ code to implement a Huffman coding tree algorithm. It defines a HuffmanNode struct to represent nodes in the tree, with character, frequency, and left/right child pointers. It also defines functions to build the Huffman tree from a string by calculating character frequencies, and to generate Huffman codes by traversing the tree. The main function calls these to build the tree for a sample string and output the generated codes.

Uploaded by

fuyf
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <iostream>

#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

// A Huffman tree node


struct HuffmanNode {
char character;
int frequency;
HuffmanNode *left, *right;
HuffmanNode(char c, int f) : character(c), frequency(f),
left(nullptr), right(nullptr) {}
};

// Compare two Huffman nodes based on their frequency


struct CompareHuffmanNodes {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->frequency > b->frequency;
}
};

// Traverse the Huffman tree and generate Huffman codes


void generateHuffmanCodes(HuffmanNode* root, string code,
unordered_map<char, string>& huffmanCodes) {
if (root == nullptr) {
return;
}
if (root->character != '\0') {
huffmanCodes[root->character] = code;
}
generateHuffmanCodes(root->left, code + "0", huffmanCodes);
generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// Build Huffman tree for given string


HuffmanNode* buildHuffmanTree(string input) {
// Calculate frequency of each character
unordered_map<char, int> charFreq;
for (char c : input) {
charFreq[c]++;
}
// Create min heap of Huffman nodes
priority_queue<HuffmanNode*, vector<HuffmanNode*>,
CompareHuffmanNodes> minHeap;
for (auto& p : charFreq) {
[Link](new HuffmanNode([Link], [Link]));
}
// Build Huffman tree from min heap
while ([Link]() > 1) {
HuffmanNode *left = [Link](); [Link]();
HuffmanNode *right = [Link](); [Link]();
HuffmanNode *parent = new HuffmanNode('\0', left->frequency +
right->frequency);
parent->left = left;
parent->right = right;
[Link](parent);
}
return [Link]();
}

// Driver code
int main() {
string input = "ACCEBFFFFAAXXBLKE";
HuffmanNode* root = buildHuffmanTree(input);
unordered_map<char, string> huffmanCodes;
generateHuffmanCodes(root, "", huffmanCodes);
for (auto& p : huffmanCodes) {
cout << [Link] << ": " << [Link] << endl;
}
return 0;
}

You might also like