Question

Write a C++ program using produces Huffman code for a string of text entered by the user. The string given by the user can be either 1 word or 1000 words.

Must accept all ASCII characters.

Please do not copy from the internet. This is my 3rd time posting the same question and I have not received a correct answer.

Answer 1

Using below code ,we can enter single or multiple words also it accept ASCII characters.

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

struct Node
{
   char ch;
   int freq;
   Node *left, *right;
};
Node* getNode(char ch, int freq, Node* left, Node* right) //alocating new tree node
{
   Node* node = new Node();

   node->ch = ch;
   node->freq = freq;
   node->left = left;
   node->right = right;

   return node;
}

// Comparison object to be using
struct comp
{
   bool operator()(Node* l, Node* r)
   {
       return l->freq > r->freq;
   }
};

// traverse the Huffman Tree
void encode(Node* root, string str,
           unordered_map<char, string> &huffmanCode)
{
   if (root == nullptr)
       return;

  
   if (!root->left && !root->right) {
       huffmanCode[root->ch] = str;
   }

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

// decode the encoded string
void decode(Node* root, int &index, string str)
{
   if (root == nullptr) {
       return;
   }

   // found a leaf node
   if (!root->left && !root->right)
   {
       cout << root->ch;
       return;
   }

   index++;

   if (str[index] =='0')
       decode(root->left, index, str);
   else
       decode(root->right, index, str);
}

// decode given input text
void buildHuffmanTree(string text)
{
  
   unordered_map<char, int> freq;
   for (char ch: text) {
       freq[ch]++;
   }

   // priority queue created
   priority_queue<Node*, vector<Node*>, comp> pq;

  
   for (auto pair: freq) {
       pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
   }
   while (pq.size() != 1)
   {
       // Remove the two nodes of highest priority
      
       Node *left = pq.top(); pq.pop();
       Node *right = pq.top();   pq.pop();

      
       //Add the new node
       int sum = left->freq + right->freq;
       pq.push(getNode('\0', sum, left, right));
   }

  
   Node* root = pq.top();

  
  
   unordered_map<char, string> huffmanCode; // traverse the Tree
   encode(root, "", huffmanCode);

   cout << "Huffman Codes are :\n" << '\n';
   for (auto pair: huffmanCode) {
       cout << pair.first << " " << pair.second << '\n';
   }

   cout << "\nOriginal string was :\n" << text << '\n';

   string str = "";
   for (char ch: text) {
       str += huffmanCode[ch];
   }

   cout << "\nEncoded string is :\n" << str << '\n';

   // traverse the Huffman Tree

   int index = -1;
   cout << "\nDecoded string is: \n";
   while (index < (int)str.size() - 2) {
       decode(root, index, str);
   }
}

int main()
{
   string text = "a @ null hi wonderfull hello b ";// Huffman coding algorithm

   buildHuffmanTree(text);

"Please refer to the screenshot of the code to understand the indentation of the code".

PLEASE LIKE...THANK YOU!