Haar Wavelet Image Compression

#include <iostream>

#include <math.h>

#include <conio.h>

#include <stdio.h>

#include <graphics.h>

#define PI 3.14

using namespace std;

void paint(int a,int b,int value)

{

     for(int i=0;i<20;i++)

     {

          for(int j=0;j<20;j++)

             putpixel(20*a+i,20*b+j,COLOR(int(value)%255,int(value)%255,int(value)%255));

     }

}

 void haar(int imgdata[][8],int wt,int ht,int numlevel)

    {

        int htrnsr[ht][wt], htrnsc[ht][wt], htindex;

        for(int level=1;level<=numlevel ;level++)

        {

            for(int i=0;i<ht;i++)

            {

                htindex=0;

                for(int j=0;j<wt;j+=2)

                {

                    htrnsr[i][htindex]=(imgdata[i][j]+imgdata[i][j+1])/2;

                    htrnsr[i][htindex+wt/2]=imgdata[i][j]-imgdata[i][j+1];

                    htindex++;

                }

            }

            for(int i=0;i<wt;i++)

            {

                htindex=0;

                for(int j=0;j<ht;j+=2)

                {

                    htrnsc[htindex][i]=(htrnsr[j][i]+htrnsr[j+1][i])/2;

                    htrnsc[htindex+ht/2][i]=htrnsr[j][i]-htrnsr[j+1][i];

                    htindex++;

                }

            }

            for(int i=0;i<ht;i++)

                for(int j=0;j<wt;j++)

                    imgdata[i][j]=htrnsc[i][j];

            wt=wt>>1;            ht=ht>>1;

        }

    initwindow(160,160,"HWT");         cout<<"\n";

    cout<<"\n HWT IMAGE DATA \n";      

    for(int i=0;i<8;i++)

    {

        for(int j=0;j<8;j++)

        {

            paint(i,j,imgdata[i][j]);            cout<<imgdata[i][j]<<"\t";

        }

        cout<<"\n";

    }

    }

      

int main()

{

    initwindow(160,160,"INPUT");

    

    int P[8][8]={ 12,25,21,26,20,21,24,23,

                    63,59,55,90,109,85,69,72,

                    42,49,48,143,144,144,46,43,

                    13,58,71,122,154,106,90,69,

                    67,61,68,164,166,68,68,60,

                    79,35,60,70,77,68,58,75,

                    85,81,84,89,85,81,85,83,

                    87,79,69,68,65,76,78,94};

    float F[8][8];

    

    cout<<"\n INPUT IMAGE DATA \n";   

    for(int i=0;i<8;i++)

    {

        for(int j=0;j<8;j++)

        {

            paint(i,j,P[i][j]);            cout<<P[i][j]<<"\t";

        }

        cout<<"\n";

    }    

    haar(P,8,8,1);    

    while( !kbhit() ); 

    closegraph( );

    getch();

    return 0;

}

DCT Image Compression

#include <iostream>
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <graphics.h>
#define PI 3.14


using namespace std;


void paint(int a,int b,int value)
{
     for(int i=0;i<20;i++)
     {
             for(int j=0;j<20;j++)
               putpixel(20*a+i,20*b+j,COLOR(value%255,value%255,value%255));
     }
}
  
int main()
{
    initwindow(160,160,"INPUT IMAGE");
    
    float P[8][8]={ 12,25,21,26,20,21,24,23,
                    63,59,55,90,109,85,69,72,
                    42,49,48,143,144,144,46,43,
                    13,58,71,122,154,106,90,69,
                    67,61,68,164,166,68,68,60,
                    79,35,60,70,77,68,58,75,
                    85,81,84,89,85,81,85,83,
                    87,79,69,68,65,76,78,94};


    float F[8][8];
   
    cout<<"\n INPUT IMAGE DATA \n");
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            paint(i,j,P[i][j]);
            P[i][j]-=128;
            cout<<P[i][j]<<"\t";
        }
        cout<<"\n";
    }
    cout<<"\n\n NORMALIZED IMAGE DATA \n");
    initwindow(160,160,"NORMALIZED IMAGE");
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            paint1(i,j,P[i][j]);
    cout<<"\n\n DCT IMAGE DATA \n");
    initwindow(160,160,"DCT IMAGE");
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            float temp=0;
            float alpha1,alpha2;
            for(int k=0;k<8;k++)
                for(int l=0;l<8;l++)
                    temp+=P[k][l]*cos((PI/8)*(k+0.5)*i)*cos((PI/8)*(l+0.5)*j);




            if(i==0)
                alpha1=0.707;
            else
                alpha1=1.0;
            if(j==0)
                alpha2=0.707;
            else
                alpha2=1.0;
            F[i][j]=0.25*alpha1*alpha2*temp;
            cout<<int(F[i][j])<<"\t";
            paint(i,j,F[i][j]);
        }
        cout<<"\n";
    }    
    while( !kbhit() ); 
    closegraph( );
    return( 0 );
}

String Comparison

#include<fstream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define TMAX 100 // Maximum Length of Text in a Text File
#define MAX 12 // Maximum Length of Text File Name


void create_file()
{
 FILE *fp;
 char fn[MAX];
 char ch;
 char text[TMAX];
 printf("Enter a filename (.txt): ");
 scanf("%s",fn);
 fflush(stdin);
 fp = fopen(fn,"w+");
 if(fp == NULL)
  printf("\n ERROR in Opening File \n");
 else
 {
 printf("\n\n Enter the text : ");
 gets(text);
 fflush(stdin);
 for(int i=0;i<strlen(text);i++)
  fputc(text[i],fp);
 printf("\n\n The Text has been written on '%s'",fn);
 }
 fclose(fp);
}


void display_file()
{
 FILE *fp;
 char fn[MAX];
 char text[TMAX];
 char ch;
 printf("Enter a filename (.txt): ");
 gets(fn);
 fflush(stdin);
 fp = fopen(fn,"r+");
 if(fp == NULL)
  printf("\n ERROR in Opening File \n");
 else
 {
 printf("\n\n The Text has been read on '%s'",fn);
 printf("\n\n The Text : ");
 while(!feof(fp))
 {
  ch = fgetc(fp);
  printf("%c",ch);
 }
 fflush(stdin);
 }
 fclose(fp);
}










void compare_files()
{
 FILE *fp1,*fp2;
 char fn1[MAX];
 char fn2[MAX];
 char ch1,ch2;
 printf("Enter a 1st filename (.txt): ");
 gets(fn1);
 fflush(stdin);
 printf("Enter a 2nd filename (.txt): ");
 gets(fn2);
 fflush(stdin);


 fp1 = fopen(fn1,"r+");
 fp2 = fopen(fn2,"r+");


 if(fp1 == NULL || fp2 == NULL || strcmp(fn1,fn2) == 0)
  printf("\n ERROR in Opening either Files \n");
 else
 {
 int ind = 0;
 printf("\n\n The Texts can be read and compared from '%s' and '%s' ",fn1,fn2);
 while((!feof(fp1)) || (!feof(fp2)))
 {
  ch1 = fgetc(fp1);
  ch2 = fgetc(fp2);
  if(ch1 != ch2)
  {
   ind = 1;
   break;
  }
 }
 if(ind == 1)
  printf("\n\n The Text of both files are distinct. ");
 else
  printf("\n\n The Text of both files are same. ");
 }
 fclose(fp1);
 fclose(fp2);
}


void main()
{
 int cho;
 do
 {
 clrscr();
 printf("\n... MENU ...\n");
 printf("\n1. Create a file ");
 printf("\n2. Display a file ");
 printf("\n3. Compare the files ");
 printf("\n Hit '0' to exit ");
 printf("\n\n Enter the option : ");
 scanf("%d",&cho);
 switch(cho)
 {
  case 1 : create_file();
     break;
  case 2 : display_file();
     break;
  case 3 : compare_files();
     break;
  default: break;
 }
 getch();
 }while(cho != 0);
}

Static Huffman Coding

#include<conio.h>
#include <stdio.h>
#define max 0
#define mxbits 20


struct ele
{
  int posn; // Position of the node inside the Huffman tree
  int info;
  int code[mxbits];
  int lft;
  int rgt;
}ar[max],tr[max],item,item1,tmp1,tmp2,tmp3;


int noe,i,j,ptr,par,ind,left,right;


/* Data Items (Internal Nodes) and External Nodes are Inserted in Min Heap */
void ins_heap(int n,struct ele item)
{
 tr[n] = item;
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;


 while(ptr>1 && tr[par].info > tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }


 }
}


/* Data Items (Internal Nodes) and External Nodes are Deleted from the Min Heap */
struct ele del_heap(int end)
{
 item1 = tr[1];
 tr[1] = tr[end];
 par = 1; left = 2; right = 3;
 ind = 0;


 while(par < end && ind == 0)
 {
  if(tr[left].info < tr[par].info && tr[left].info < tr[right].info && left<end)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }


  else if(tr[right].info < tr[par].info && tr[left].info > tr[right].info  && right<end)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 return item1;
}


/* Insertion of data items in an arrays as well as on the Min-Heap
Here, every Data Items will be treated as Internal Nodes of the Huffman Tree */


void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of data items : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max/2);


 printf("\n\n Enter the frequencies '%d' data items : ",noe);

for(i=1;i<=noe;i++)
  {
  scanf("%d",&ar[i].info);
  ar[i].posn = 0;
  ar[i].lft = 0;
  ar[i].rgt = 0;
  ins_heap(i,ar[i]);
  }
}


/* The following Function performs to Form a Huffman Tree
After Forming a Min-Heap of Data Items, Two of them are Popped from the heap and 
added together to form an External node, which is again Inserted to the Min-Heap */


void hfmn_tree()
{
 i = noe;
 j = i+1;


 while(i>1)
 {
  tmp1 = del_heap(i);
  tmp2 = del_heap(--i);
  tmp3.info = tmp1.info + tmp2.info;
  tmp3.posn = j;
  tmp3.lft = tmp1.posn;
  tmp3.rgt = tmp2.posn;
  ar[j] = tmp3;
  ins_heap(i,tmp3);
  j++;
 }


 ar[j-1].posn = 1; // Sets the position of Root of Huffman Tree to ‘1’
 i = j-1;
// Sets the position of External Nodes & Internal Nodes as Data Items of Huffman Tree
 while(i > noe)
 {
  ar[ar[i].lft].posn = 2*ar[i].posn;
  ar[ar[i].rgt].posn = 2*ar[i].posn+1;
  i--;
 }
}






/* After getting the position of every Data Items (Internal Nodes of Huffman Tree)
  We’ve to find out the codes of every Data Item  */


void codes()
{
  int k;
  char ch;


/* The code of every Data Item is obtained by Dividing its Huffman Tree position by 2 
  And storing its remainder until it becomes less than 1 */


  printf("\n The Codes for every input is : ");
  for(i=1;i<=noe;i++)
  {
   k = 0;
   ch = 64+i;
   printf(" \n For %c = %d : ",ch,ar[i].info);
   while(ar[i].posn > 1)
   {
   ar[i].code[k] = ar[i].posn % 2;
   ar[i].posn /= 2;
   k++;
   }
   for(j=k-1;j>=0;j--) // Codes are printed in Reversed Order
    printf("%d",ar[i].code[j]);
  }
}


void main()
{
clrscr();
inp_dat();
hfmn_tree();
codes();
getch();
}

Arithmetic Coding

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define MAX 127 
#define SIZE 100 




struct element
{
  char c;
  float pr;
  float rng;
  float UL;
  float LL;     
}el[MAX];


int size;
char msg[SIZE];
float range = 1.00;
float UP;
float DOWN;
float enc;
int str_len;


void make_table()
{
  int i;  
  printf(" Enter the size of elements : "); 
  scanf("%d",&size);
  fflush(stdin);
  for(i=0;i<size;i++) 
  {
    printf("\n #%d Enter character and its probablity (decreasing order) : ",i+1); 
    scanf("%c %f",&el[i].c,&el[i].pr);  
    fflush(stdin); 
    el[i].LL = ((i==0) ? 0.0 :el[i-1].UL);
    el[i].UL = ((i==size-1) ? 1.0 : (el[i].LL + el[i].pr));         
  }
  getch();    
}


void show_table(int num)
{
  printf("\t\tENCODER TABLE\n\tFrequency\tRange\n");   
  for(int i=0;i<size;i++)
  {    
    printf("\n");
    if(i==num)
    { printf("*"); }     
    printf("%c\t%f\t%f-%f",el[i].c,el[i].pr,el[i].LL,el[i].UL);       
  }   
}


int find_char(int num)
{
  int i=0;
  if(num != -1)
  {
   while(el[i].c != msg[num])
   { i++; }
   
  }
  else
  {
    while(!(enc <= el[i].UL && enc >= el[i].LL))
    { i++; }      
  }
  return i;
}


void modify_table(int num)
{
  range = el[num].UL - el[num].LL;
  for(int i=0;i<size;i++)
  {
    el[i].LL = ((i==0) ? el[num].LL : el[i-1].UL) ;     
    el[i].UL = ((i==size-1) ? (el[0].LL+range) : (el[i].LL + (el[i].pr*range)));    
  }  
}


void refresh_table()
{
  for(int i=0;i<size;i++)
  {
    el[i].LL = ((i==0) ? 0.0 :el[i-1].UL);
    el[i].UL = ((i==size-1) ? 1.0 : (el[i].LL + el[i].pr));       
  }   
}
void encode_text()
{
  fflush(stdin);   
  printf("\n Enter the string to be encoded : ");
  gets(msg);   
  fflush(stdin);
  int i=0;
  int j;
  while(msg[i] != '\0')
  {
    printf("\n\n\n Word Checked : %c \n",msg[i]);           
    j = find_char(i);     
    show_table(j);  
    modify_table(j);  
    getch();    
    i++;
  } 
  DOWN = el[j].LL;
  UP = el[j].UL;
  str_len = i;
  printf("\n\n The encoded range : %f-%f for a string of %d characters",DOWN,UP,str_len);
  refresh_table();
}


void decode_text()
{
  int j;   
  printf("\n Enter the encoded value : "); 
  scanf("%f",&enc);    
  fflush(stdin);
  printf("\n\n ... Decoding Text ... \n\n");   
  while(str_len)
  {
    j = find_char(-1);     
    printf("\n\n Word decoded : %c",el[j].c);
    enc = (enc - el[j].LL)/(el[j].UL - el[j].LL);       
    printf("\n New encoded value : %f",enc);
    str_len--;     
  }
}


int main()
{
 int cho;
 do
 {   
 printf("\n\n\n\t MENU \t\n"); 
 printf("\n1. Create Table ");
 printf("\n2. Encode Text "); 
 printf("\n3. Decode Text "); 
 printf("\n\n Choose the option : "); 
 scanf("%d",&cho);
 switch(cho)
 {
   case 1  : make_table();  break;
   case 2  : encode_text();  break;
   case 3  : decode_text();  break;
   default : break;             
 } 
 }while(cho>=1 && cho<=3);
 printf("\n\n\t Thanks for using the Program !! \t\n\n"); 
 return 0;  
}

LZW Encoding

#include<stdio.h>
#include<fstream.h>
#include<string.h>
#include<conio.h>
#include <iostream.h>
#define MAX 128




char dictionary[MAX][10];
int dictionarylen=-1;


bool finddict(char str[])
{
    if(str[1]=='\0' && str[0]<128)
            return 1;
    for(int i=0;i<=dictionarylen;i++)
    {
        if(!strcmp(str,dictionary[i]))
            return 1;
    }
    return 0;
}


void adddict(char str[],char ch)
{
    int i;
    for(int i=0;i<strlen(str);i++)
     cout<<"\n'"<<str[i]<<"'\t'"<<str[i]<<"'("<<(int)str[i]<<")";              
    if(ch == ' ')
     cout<<"\n' '";
    else
     cout<<"\nEOF";       
    dictionarylen++;    
    strcpy(dictionary[dictionarylen],str);
     cout<<"\t\t\t\t'"<<dictionary[dictionarylen]<<"'("<<dictionarylen+128<<")";
}


int findindex(char str[])
{
    if(strlen(str)==1 && str[0]<128)
            return int(str[0]);
    for(int i=0;i<=dictionarylen;i++)
    {
        if(!strcmp(str,dictionary[i]))
            return i+128;
    }
}


int main()
{
    char ch;
    char str[10];
    int i,indexloc=-1;
    cout<<"The Sender Dictionary Has 127 ASCII characters initially\nReading Text from .txt file";     
    FILE *fp;
    fp=fopen("input.txt","r");
    cout<<"\nRead\tTransmitted(Code)\tExtended Dictionary";
    cout<<"\n----------------------------------------------------";
    while(ch!=EOF)
    {
        i=0;       
        while(1)
        {
            ch=fgetc(fp);
            if(ch==' ' || ch==EOF)
               break;
            
            str[i]=ch;
            i++;          
        }
        str[i]='\0';


        if(!finddict(str))
        {
            adddict(str,ch);
        }
        else
        {
            indexloc=findindex(str);
            for(int i=0;i<strlen(str);i++)
             cout<<"\n'"<<str[i]<<"'";              
            if(ch == ' ')
             cout<<"\n' '";
            else
             cout<<"\nEOF";
            cout<<"\t"<<str<<"("<<indexloc<<")";            
        }
    }
    fclose(fp);    
    getch();
    return 0;
    
}

Dynamic Huffman Coding

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<math.h>
#define max 50 
#define ascmax 130


struct tree
{
  int posn;     
  char ct;
  int frq;     
  int rgt;     
  int lft;       
}tr[ascmax+max];






int size =2;
int epos;




void init_node(char tmp)
{
  tr[0].posn = 1;
  tr[0].ct = '~'; 
  tr[0].lft = 1;
  tr[0].rgt = 2;
  tr[0].frq = 1; 
  
  tr[1].posn = 2*tr[0].posn;
  tr[1].ct = 'E';
  tr[1].frq = 0;
  
  tr[2].posn = 2*tr[0].posn+1;
  tr[2].ct = tmp;
  tr[2].frq = 1;
    
  tr[1].lft = tr[2].lft = -1;
  tr[1].rgt = tr[2].rgt = -1;  


  epos = 1;
  
  printf("\n '%c'\t\t '%c'",tmp,tmp);
  printf("\n Traversing :- ('E',0) ('%c',1)",tmp); 
  printf("\n The Tree is in weight order\n"); 
}






void add_node(char ctc)
{
 char bits[max];
 int bsize=0,ps,j; 

 printf("\n '%c'\t\t '%c' ",ctc,ctc);
 int tp = tr[epos].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

 ++size;
 tr[size] = tr[epos];
 tr[size].posn = 2*tr[epos].posn;
 tr[size].lft = -1;    
 tr[size].rgt = -1;    



 tr[epos].ct = '^';
 tr[epos].frq = 1;    
 tr[epos].lft = size;    
 tr[epos].rgt = size+1;    




 epos = size;

 ++size;

 tr[size].posn = tr[epos].posn+1;
 tr[size].ct = ctc;
 tr[size].frq = 1;
 tr[size].lft = -1;
 tr[size].rgt = -1;  

 ps = (tr[size].posn/2)/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   
   tr[j].frq += 1;         
   ps /= 2;           
  }  



}




void update_node(char ctc)
{
  char bits[max];
 int bsize=0;    

  int i=1,j;
  int ps;
  while(ctc != tr[i].ct)
   i++; 
    
  tr[i].frq += 1;
  
  ps = tr[i].posn/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   

   tr[j].frq += 1;         
   ps /= 2;           
  }  
  
  printf("\n '%c'\t\t   ",ctc);
 int tp = tr[i].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

}


void reset_node(int nm)
{
 ///printf("\n\n %c/%d(pos=%d)",tr[nm].ct,tr[nm].frq,tr[nm].posn);    
 if(tr[nm].ct == 'E')
  epos = nm;
  
 if(tr[nm].lft != -1)
 {
   //printf("\n Lft Case");            
   tr[tr[nm].lft].posn = 2*tr[nm].posn;
   reset_node(tr[nm].lft);        
 }

 if(tr[nm].rgt != -1 )
 {
   //printf("\n Rgt Case");
   tr[tr[nm].rgt].posn = 2*tr[nm].posn+1;
   reset_node(tr[nm].rgt);      
 }
     
}


void balance_tree()
{
  //printf("\n%d",tr[epos].posn);
  struct tree tn;
  double lvl;
  int i,ilvl,j,ind;
  int optnsize;
  int init; 
  //= tr[epos].posn;
  
  struct outptn
  {
   int psn;
   int frq;      
  }optn[ascmax+max];
  
 do
 {
  optnsize = 0;
  //printf("\n %d %d %c",epos,tr[epos].posn,tr[epos].ct);
  
  lvl = log((double)tr[epos].posn)/log (2);
  ilvl = (int) lvl;
  init = tr[epos].posn;
  
 // printf("\n level=%d ",ilvl);
  while(ilvl>0)
  {
    for(i=init;i<=pow(2,ilvl+1)-1;i++)
    {
      j = 0;
      while(j<=size && tr[j].posn != i)
       j++;    
      if(j<=size)
      {
        optn[optnsize].psn = j;
        optn[optnsize].frq = tr[j].frq;
        ++optnsize;         
      }        
    }    
    --ilvl;     
    init = pow(2,ilvl);          
  }
    
  optn[optnsize].psn = 0;
  optn[optnsize].frq = tr[0].frq;
  ++optnsize;      
  
  ind = -1;
  printf("\n Traversing :-");
  for(i=0;i<optnsize;i++)  
  {
    printf(" ('%c',%d)",tr[optn[i].psn].ct,optn[i].frq);
     if(i < optnsize-1 && optn[i].frq > optn[i+1].frq && ind == -1)
       ind = i;   
  } 
  
  if(ind != -1)
  {
   printf("\n The Tree is not in weight order");     
   
   int ind2 = ind+1;
   
   while(optn[ind2].frq == optn[ind2+1].frq)
    ind2++;
   
   while(optn[ind].frq == optn[ind-1].frq)
    ind--;
    
   printf("\n Swapping ('%c',%d) and ('%c',%d)",tr[optn[ind].psn].ct,optn[ind].frq,tr[optn[ind2].psn].ct,optn[ind2].frq);
   
   int tmp = tr[optn[ind].psn].posn;
     tmp /= 2;
     int k=0;
   
     while(tr[k].posn != tmp)
      k++;
      
   tmp = tr[optn[ind2].psn].posn;
     tmp /= 2;
     int l=0;
     while(tr[l].posn != tmp)
      l++;
     
      
     if(tr[optn[ind].psn].posn%2 == 0)
     {
      tmp = tr[k].lft;                           
      tr[k].lft = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].lft].posn = 2*tr[k].posn;
     }
     
     else
     {
      tmp = tr[k].rgt;                           
      tr[k].rgt = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].rgt].posn = 2*tr[k].posn+1;
     }
     
     

   reset_node(optn[ind].psn);
   reset_node(optn[ind2].psn);     
   
   for(j=size;j>=0;j--) 
   {
     if(tr[j].ct == '~' || tr[j].ct == '^') 
       tr[j].frq = tr[tr[j].lft].frq + tr[tr[j].rgt].frq ;              
   }    
  }
  else
   printf("\n The Tree is in weight order");  
  optnsize = 0;
 }while(ind != -1);
 printf("\n");
}




int main()
{
 char msg[max]; 
 printf("\n Enter the string : "); 
 gets(msg);
 printf("\n Dynamic Huffman Coding \n");
 printf("\n Input\t\t Output");
 printf("\n -----\t\t ------\n");
  int i=1;
 int j; 
 init_node(msg[0]);
 while(msg[i]!='\0')
 {
   j=i;
   do
   {
     --j;  
   }while(j>=0 && msg[j] != msg[i]);     
   if(j>=0)
    update_node(msg[i]);
   else
    add_node(msg[i]);
   balance_tree();
  i++;   
  getch(); 
 }
 getch();
 return 0;   
}