CODE

:: Code Portion for Encoding ::

:: Code Portion for Decoding ::

:: Complete Code ::

#include <iostream>

#include <string>

#include <queue>

#include <unordered_map>

using namespace std;

#define EMPTY_STRING ""

struct Node

{

char ch;

int frequency;

Node *left, *right;

};

Node* getNode(char ch, int frequency, Node* left,

Node* right)

{

Node* node = new Node();

node->ch = ch;

node->frequency = frequency;

node->left = left;

node->right = right;

return node;

}

struct comp

{

bool operator()(const Node* l, const Node* r)

const

{

// the highest priority item has the lowest frequency

return l->frequency > r->frequency;

}

};

//to check if Huffman Tree contains only a single node

bool vaildLeaf(Node* root) {

return root->left == nullptr && root->right == nullptr;

}

void encode(Node* root, string str, unordered_map<char,

string> &huffmanCode)

{

if (root == nullptr) {

return;

}

if (vaildLeaf(root)) {

huffmanCode[root->ch] = (str != EMPTY_STRING) ?

str : "1";

}

encode(root->left, str + "0", huffmanCode);

encode(root->right, str + "1", huffmanCode);

}

void decode(Node* root, int &index, string str)

{

if (root == nullptr) {

return;

}

if (vaildLeaf(root))

{

cout << root->ch;

return;

}

index++;

if (str[index] == '0') {

decode(root->left, index, str);

}

else {

decode(root->right, index, str);

}

}

void HuffmanTree(string symbols)

{

if (symbols == EMPTY_STRING) {

return;

}

unordered_map<char, int> frequency;

for (char ch: symbols) {

frequency[ch]++;

}

priority_queue<Node*, vector<Node*>, comp> pq;

for (auto pair: frequency) {

pq.push(getNode(pair.first, pair.second, nullptr,

nullptr));

}

while (pq.size() != 1)

{

Node* left = pq.top(); pq.pop();

Node* right = pq.top(); pq.pop();

int sum = left->frequency + right->frequency;

pq.push(getNode('\0', sum, left, right));

}

Node* root = pq.top();

unordered_map<char, string> huffmanCode;

encode(root, EMPTY_STRING, huffmanCode);

cout << "Huffman Codes are:\n" << endl;

cout<<"=========="<<endl;

for (auto pair: huffmanCode) {

cout<<pair.first << " --> "<<pair.second<<endl;

}

cout<<"=========="<<endl;

cout<<"\nThe original string is:\n"<<symbols<< endl;

// Print encoded string

string str;

for (char ch: symbols) {

str += huffmanCode[ch];

}

cout << "\nThe encoded string is:\n" << str << endl;

cout << "\nThe decoded string is:\n";

if (vaildLeaf(root))

{

// Special case: For input like a, aa, aaa, etc.

while (root->frequency--) {

cout << root->ch;

}

}

else {

int index = -1;

while (index < (int)str.size() - 1) {

decode(root, index, str);

}

}

}

int main()

{

string symbols = "Test runs are mandatory to ensure

that the code works.";

HuffmanTree(symbols);

return 0;

}