Huffman Tree

Algorithm : Huffman tree

1.Creating an Huffman tree

Build_huffman()
{
This algorithm creates a Huffman tree using an pointer array h[]. 

Read n
 
for(i=1 to n)
	{
	t=getnode()
	read t->data,t->wt
	h[i]=t 
	}

i=1
 
while(i<n)
	{
	sort(i,n,h)                      //sorting the array h[] from i to n index.
	t=getnode()
	t->data=NULL
	t->wt=(h[i]->wt)+(h[i+1]->wt)
	t->lchild=h[i]
	t->rchild=h[i+1]
	h[i+1]=t
	i++
	}

root=h[i]

return root
}


2.Calculating the Huffman code of a given value
 
encode(root,c,k)
{
Given the root, this algorithm stores the 
Huffman encoding of the given value ‘c’ in an array e[] 
whose present index no. is stored in the pointer variable ‘k’.
If we print this array in reversed order, we will get the required code.
  

if(root=NULL)
	return 0
else if(root->data=c)
	return 1
else
	{
	i=encode(root->lchild,c,k)   //if not found within the left subtree,
                                             then accessing the right one.
	if(i≠1)
		{
		i=encode(root->rchild,c,k)
		if(i=1)
			{
			e[k]=1
			k=k+1
			}
		}
	else
		{
		e[k]=0
		k=k+1
		}

	return i
	}
}



In this set of algorithms, we have often used 
a algorithm called getnode().
This algorithm allocates a node structure in the memory and returns its
address to the variable.
Apart from that, several other functions like search(), height(), push(),
pop() etc are used in the program. 
They mean the general operations described before.


C Program For Huffman tree

Source Code:



#include<stdio.h>
#include<conio.h>

#define ns 256


struct node
	{
	char data;
	int wt;
	struct node *lchild,*rchild;
	};

struct occur
	{
	char data;
	int wt;
	};

int n0=0,e[20];

struct occur s[ns];

struct node * getnode()
{
struct node *t;
t=(struct node *)malloc(sizeof(struct node));
t->rchild=NULL;
t->lchild=NULL;

return t;
}

void sort(int i,int n,struct node **h)
{
int j,k;
struct node *temp;

for(j=1;j<=n-i-1;j++)
	{
	for(k=i;k>=n-j-1;k++)
		{
		if(h[k]->wt>h[k+1]->wt)
			{
			temp=h[k];
			h[k]=h[k+1];
			h[k+1]=temp;
			}
		}
	}
}

void inorder(struct node *root)
{

if(root!=NULL)
	{
	inorder(root->lchild);
	if(root->data!=NULL)
		printf(" %c(%d) ",root->data,root->wt);
	else
		printf(" %c(%d) ",254,root->wt);

	inorder(root->rchild);
	}
}

void preorder(struct node *root)
{

if(root!=NULL)
	{
	if(root->data!=NULL)
		printf(" %c(%d) ",root->data,root->wt);
	else
		printf(" %c(%d) ",254,root->wt);

	preorder(root->lchild);
	preorder(root->rchild);
	}
}

void postorder(struct node *root)
{

if(root!=NULL)
	{
	postorder(root->lchild);
	postorder(root->rchild);
	if(root->data!=NULL)
		printf(" %c(%d) ",root->data,root->wt);
	else
		printf(" %c(%d) ",254,root->wt);
	}
}

struct node * search(struct node *root,char key)
{
struct node *r;

if(root==NULL)
	return NULL;
else if(root->data==key)
	return root;
else
	{
	r=search(root->lchild,key);
	if(r==NULL)
		r=search(root->rchild,key);
	return r;
	}

}

void view()
{
FILE *fp;
char ch;

printf("\n");

fp=fopen("E:\\Text.txt","rt+");

while(1)
	{
	ch=fgetc(fp);
	if(ch==EOF)
		break;
	printf("%c",ch);
	}

fclose(fp);

}

struct node * bhuff()
{
FILE *fp;
char ch;
int i,j,k;
struct node *h[100],*t,*root;

for(i=0;i<ns;i++)
	{
	s[i].data=65+i;
	s[i].wt=0;
	}

fp=fopen("E:\\Text.txt","rt+");

while(1)
	{
	ch=fgetc(fp);
	if(ch==EOF)
		break;

	for(i=0;i<ns;i++)
		{
		if(ch==s[i].data)
			{
			s[i].wt++;
			break;
			}
		}
	}

fclose(fp);
j=0;

for(i=0;i<ns;i++)
	{
	if(s[i].wt==0)
		continue;

	t=getnode();
	t->data=s[i].data;
	t->wt=s[i].wt;
	h[j]=t;

	j++;
	}


for(i=0;i<j;i++)
	{
	printf("\n%c=>%d ",h[i]->data,h[i]->wt);
	}

printf("\n");

n0=j;
i=0;

while(i<j-1)
	{
	sort(i,j,h);
	t=getnode();
	t->data=NULL;
	t->wt=(h[i]->wt)+(h[i+1]->wt);
	t->lchild=h[i];
	t->rchild=h[i+1];
	h[i+1]=t;
	i++;
	}
root=h[i];


printf("\tRoot's weight=%d\n",root->wt);

return root;
}


int encode(struct node *root,char c,int *k)
{
int i;

if(root==NULL)
	return 0;
else if(root->data==c)
	return 1;
else
	{
	i=encode(root->lchild,c,k);
	if(i!=1)
		{
		i=encode(root->rchild,c,k);
		if(i==1)
			{
			e[*k]=1;
			*k=*k+1;
			}
		}
	else
		{
		e[*k]=0;
		*k=*k+1;
		}

	return i;
	}
}



void main()
{
int ch=0;
short int i,j;
char c;
struct node *root=NULL,*r;

clrscr();

printf("\nHUFFMAN TREE\n--------------");

while(ch!=5)
	{
	printf("\n\n1.Show the file E:\\Text.txt\n2.Create the tree from
E:\\Text.txt\n3.Traversal\n4.Huffman Encoding\n5.Exit\n\nYour's choice please ");
	scanf("%d",&ch);

	switch(ch)
		{
		case 2: root=bhuff();
			break;
		case 3: printf("\n1.Inorder traversal\n2.Preorder traversal
\n3.Postorder traversal\n4.All\n\nWhat do you want?? ");
			scanf("%d",&i);
			if(root!=NULL)
			   {
			switch(i)
				{
			case 1: printf("\nInorder Traversal\n");
					inorder(root);
					if(i!=4)
						break;
			case 2: printf("\n\nPreorder Traversal\n");
					preorder(root);
					if(i!=4)
						break;
			case 3: printf("\n\nPostorder Traversal\n");
					postorder(root);
					if(i!=4)
						break;

				}
			    }
			else
				printf("\nNo tree created.. :(");
			break;
	case 4: printf("\n1.Encode All\n2.Encode individual character\n\n??? ");
			scanf("%d",&ch);

			switch(ch)
				{
			case 1:	for(i=0;i<ns;i++)
						{
					if(s[i].wt!=0)
						{
						j=0;
					printf("\n%c=> ",s[i].data);
						encode(root,s[i].data,&j);
						j--;
						while(j>=0)
							{
							printf("%d",e[j]);
							j--;
							}
						}
					}
					break;
			case 2:	printf("\nEnter the character to encode ");
					fflush(stdin);
					scanf("%c",&c);
					j=0;
					r=search(root,c);
					printf("\n");
					if(r!=NULL)
						{
						j=0;
						encode(root,c,&j);
						j--;
						while(j>=0)
							{
							printf("%d",e[j]);
							j--;
							}
						}
				else
				printf("There is no such character. :(");
				break;
				}
				break;
		case 5:	break;
		case 1: view();
			break;
		default:printf("\nNot a valid choice at all..:(");
		}
	}

printf("\nPress any key to exit..");
getch();
}