this is my huffman code but it is not giving the correct result as it should i mean i am not getting the whole right subtree from root
for eg:
if a text file contains
space:3
a:8
e:6
w:2
r:2
t:2
d:1
q:2
den i not getting sub tree containing r,t,a,sapce
whereas left sub tree is coming all correct
to get a clear view just see the attachment[
code is below
to execute it first make a text file and write letter shown above and no's adjacent to them r dere respective occurrences in a file
Code:
#include <fstream.h>
#include<conio.h>
#include<iostream.h>
#include<stdio.h>
struct node
{ int weight;
char data;
int freq;
struct node *left,*right,*prev,*next;
};
char ch;
int min,min2,min3,m,min4;
node *root,*ptr,*last,*temp2,*add,*temp,*back,*r;
node *del(node *ptr,int min);
int minsecond(node *ptr);
node *insert(node *ptr,int min3) ;
int minfirst(node *ptr);
int main()
{
clrscr();
char filename[89];
int a;
int arr[256];
for(int i=0;i<256;i++)
{
arr[i]=0;
}
cout<<"enter filename";
cout<<"\n";
cin.get(filename,89);
fstream file_op(filename,ios::in);
if(!file_op)
{
cout<<"file does not exist";
return 0;
}
while(!file_op.eof())
{
file_op.get(ch);
a=ch;
arr[a]=arr[a]+1;
}
file_op.close();
root =new node;
ptr=root;
root->next=NULL;
root->prev=NULL;
root->right=NULL;
root->left=NULL;
for(i=0;i<256;i++)
{
if(arr[i]>0)
{
root->right=new node;
root=root->right;
root->right=NULL;
root->left=root;
root->data=i;
root->freq=arr[i];
root->next=NULL;
root->prev=NULL;
}
}
while(ptr->right->right!=NULL)
{
min=minfirst(ptr);
ptr=del(ptr,min);
min2=minr(ptr);
min3=min+min2;
ptr=del(ptr,min2);
ptr=insert(ptr,min3);
}
node *r;
r=ptr->right;
cout<<r->data<<r->freq;
cout<<endl;
while(r->next!=NULL)
{ r=r->next;
cout<<r->weight<<","<<r->freq<<","<<r->data<<"\n";
}
getch();
}
node *insert(node *ptr,int min3)
{
add=new node;
add->freq=min3;
add->data=NULL;
if(ptr->right==NULL)
add->right=NULL;
else
add->right=ptr->right;
add->left=ptr;
ptr->right=add;
add->next=temp2;
temp2->weight=1;
add->prev=last;
last->weight=0;
return(ptr);
}
node *del(node *ptr,int m)
{
back=ptr;
temp=ptr->right;
while(temp!=NULL)
{
if(temp->freq==m)
{
if(temp->right!=NULL)
{
back->right=temp->right;
temp->right=NULL;
temp->left=NULL;
}
else
back->right=NULL;
return(ptr);
}
back=temp;
temp=temp->right;
}
}
int minsecond(node *ptr)
{ ptr=ptr->right;
min4=ptr->freq;
while(ptr!=NULL)
{
if(ptr->freq<min4)
{
min4=ptr->freq;
if(ptr->next!=NULL)
{
temp2=new node;
temp2->freq=min4;
temp2=ptr;
temp2->weight=1;
temp->data=NULL;
}
else
{
temp2=new node;
temp2->next=NULL;
temp2->prev=NULL;
temp2->data=ptr->data;
temp2->weight=1;
temp2->freq=min4;
}
}
else
{
ptr=ptr->right;
}
}
return(min4);
}
int minfirst(node *ptr)
{
ptr=ptr->right;
min4=ptr->freq;
while(ptr!=NULL)
{
if(ptr->freq<min4)
{
min4=ptr->freq;
if(ptr->next!=NULL)
{
last=new node;
last->freq=min4;
last=ptr;
last->weight=0;
last->data=NULL;
}
else
{
last=new node;
last->next=NULL;
last->prev=NULL;
last->data=ptr->data;
last->weight=0;
last->freq=min4;
}
}
else
{
ptr=ptr->right;
}
}
return(min4);
}