Thread: huffman coding

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

hey see the attachment along with dis post

there is a tree for these freq.

hey did u see that attachment?

Originally Posted by brewbuck

I am unable to open a .doc file.

wht's the problem?

u don't hv MS-word with u?

if u hv notepad or wordpad with u den u can also open dis file in it

r u still unable to open it?

hey is dere nyone who can help me out?