i am writing a program on huffman's code in C++.
I have wriiten the program till building the huffman tree. now I have to generate the code by traversing the huffman tree. I have no idea how to do that logically. please help with code or algorithm.
Here is my code so far.
IDE used is dev-cpp.

#include<iostream>
#include<stdio.h>
#include<fstream>
using namespace std;

#define MAX_SYM 256

class node;
//GLOBAL VARIABLES
node *queue_top;
int heap_size;

class node
{
      int freq;
      char ch;
      node *left, *right;
      node* next;
      
      public:
      node()
      {
            left = NULL;
            right= NULL;
            next= NULL;
      }
      void ini(int i)
      {
           freq=i;
      }
      void display()
      {
           cout<<"node is: "<<ch<<endl;
           cout<<"Freq is: "<<freq<<endl;
      }
      void extract_min_node()
      {
            freq= queue_top->freq;                  //copying
            ch= queue_top->ch;
            next=NULL;                              //no need to copy left,right as they contain NULL
            queue_top=queue_top->next;
            heap_size--;
      }
      int get_freq()
      {
          return freq;
      }
      friend void gen_freq(char *);
      friend void insert_queue(node *);
      friend void build_huffman();
      
}PQ[MAX_SYM];

----------------------------------------------CLASS DECLARATION OVER----------------------------------------------------------------

void gen_freq(char *file_name)
{
      ifstream fin;
      fin.open(file_name,ios::in);
      char ch;
      fin>>ch;
      while (fin)
      {
            PQ[int(ch)].freq++;
      }
}
void insert_queue(node* x)
     {
     int flag=0;
     node *smallest,*temp;
     if (heap_size==0)
        queue_top=x;
     else
     {
         if (x->freq < PQ[0].freq)
         {
                 //put node at start of the queue
                 temp=queue_top;
                 queue_top=x;
                 x->next=temp;  
         }
         int i=1;
         while (i<heap_size)
         {
                 if (x->freq < PQ[i].freq) 
                 {
                    x->next=&PQ[i];
                    PQ[i-1].next=x;
                    flag = 1;
                    break;
                 }
                 
         }
         if (flag==0)
         {
            PQ[heap_size-1].next=x;
         } 
     }
     heap_size++;
}

void build_huffman()
{
     node l,r,newt;
     for(int i=0;i<(heap_size-1);i++)                  //in heapsize-1 iterations only 1 root node will be left
     {
             l.extract_min_node();
             r.extract_min_node();
             newt.freq= l.freq+r.freq;
             newt.left=&l;
             newt.right=&r;
             insert_queue(&newt);
     }
}
void generate_code(char [])
{
}
void encode()
{
}

int main()
{
    //initialize the queue
    for (int i= 0; i<256; i++)
    {
        PQ[i].ini(i); 
    }
    
    //input text file name
    char file_name[100];
    cout<<"Enter name of text file: ";
    gets(file_name);
    
    //create frequencies from file
    gen_freq(file_name);
    for (int i= 0; i<256; i++)
    {
        PQ[i].display(); 
    }
    for (int i= 0; i<256; i++)            // insert node for a EXISTING symbol
    {
        if (PQ[i].get_freq()!=0)
        insert_queue(&PQ[i]); 
    }
    //build huffman tree
    build_huffman();
    
    //create code for each symbol
    char a[MAX_SYM];
    generate_code(a);
    
    //encode the given file
    encode();
    
    system("pause");
    return 0;
}

Ok i was able to do generate the code using recursive function calls.

Now I am having a problem that 'Dev-CPP IDE' shows an error "dev-cpp has stopped working" when i run the program. The program executes fine though.

Ok the problem is resolved for now. I will ask mods for deleting this thread as the code given by me here is not good and there haven't been any replies also. The thread isn't worth saving.

This article has been dead for over six months. Start a new discussion instead.