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;
}