#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define Min 1000;
typedef struct
{
  int weight;
  int parent;
  int lchild;
  int rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

void Select(HuffmanTree ht,int n,int *s1,int *s2)
{
  int i,c2;
  int c1=Min;
  for(i=1;i<=n;i++)
   {
    if((ht[i].parent==0)&&(ht[i].weight<c1))
     {
       *s1=i;
       c1=ht[i].weight;
      }
    }
  c2=Min;
  for(i=1;i<=n;i++)
   {
    if((ht[i].parent==0)&&(*s1!=i)&&(c2>ht[i].weight))
     {
       *s2=i;
       c2=ht[i].weight;
      }
    }
}

void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)
{
  int i, j, m, s1, s2, start;
  char *cd;
  unsigned int c, f;

  if (n<=1) return;
  m = 2 * n - 1;
  (*HT) = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
  for (i=1; i<=n; i++)
  {
    (*HT)[i].weight=w[i-1];
    (*HT)[i].parent=0;
    (*HT)[i].lchild=0;
    (*HT)[i].rchild=0;
  }
  for (i=n+1; i<=m; i++)
  {
    (*HT)[i].weight=0;
    (*HT)[i].parent=0;
    (*HT)[i].lchild=0;
    (*HT)[i].rchild=0;
  }
  printf("\nProcess of HuffmanCoding:\n");
  printf("HTInit:\n  Nodes  weight  parent  lchild  rchild");
  for (i=1; i<=m; i++)
    printf("\n%4d%8d%8d%8d%8d",i,(*HT)[i].weight,
            (*HT)[i].parent,(*HT)[i].lchild, (*HT)[i].rchild);
    printf("    Press any key to continue ...");
  getch();
  for (i=n+1; i<=m; i++)
  {
    Select(*HT, i-1, &s1, &s2);
    (*HT)[s1].parent = i;
    (*HT)[s2].parent = i;
    (*HT)[i].lchild = s1;
    (*HT)[i].rchild = s2;
    (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    printf("\nselect: s1=%d   s2=%d\n", s1, s2);
    printf("  Nodes  weight  parent  lchild  rchild");
    for (j=1; j<=i; j++)
      printf("\n%4d%8d%8d%8d%8d",j,(*HT)[j].weight,(*HT)[j].parent,(*HT)[j].lchild, (*HT)[j].rchild);
    printf("   Press any key to continue ...");
    getch();
  }
  (*HC)=(HuffmanCode)malloc((n+1)*sizeof(char *));
  cd = (char *)malloc(n*sizeof(char));
  cd[n-1] = '\0';
  for (i=1; i<=n; ++i)
  {
    start = n-1;
    for (c=i, f=(*HT)[i].parent; f!=0; c=f, f=(*HT)[f].parent)
      if ((*HT)[f].lchild==c) cd[--start] = '0';
      else cd[--start] = '1';
    (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
    strcpy((*HC)[i], &cd[start]);
    printf("\n%s",(*HC)[i]);
  }
  free(cd);
}

main()
{
  HuffmanTree HT;
  HuffmanCode HC;
  int w[8]={5,29,7,8,14,23,3,11};
  int n=8;
  clrscr();
  HuffmanCoding(&HT,&HC,w,n);
  getch();
}