Listing 2 A program that reads a file and generates a Huffman encoding tree based on the character frequencies in that file.

/* ---------------------- bldtree - main --------------------
*/

#include <stdio.h>
#define MAIN
#include "hufftree.h"

long htcnt[512];

main(int argc, char *argv[])
{
  FILE *fin, *fout;
  int c;
  int i;
  int ntree = 256;
  short h1, h2;
  
  if (argc < 2)
  { fprintf(stderr,"usage: %s infile \n",argv[0]);
    exit(0);
  }
  
  if ((fin = fopen(argv[1],"rb")) == NULL)
  { fprintf(stderr,"Unable to open %s for input\n",argv[1]);
    exit(1);
  }
  
  if ((fout = fopen("htree.dat","wb")) == NULL)
  { fprintf(stderr,"Unable to open htree.dat for output\n");
    exit(1);
  }
  
  /* initialize character counts so all characters recognized
*/
  for (i=0; i<256; i++)
    htcnt[i] = 1;
  
  /* count character occurrence frequencies */
  while ((c = fgetc(fin)) != EOF)
  { htcnt[c]++;
  }
  
  /* build Huffman tree */
  while(1)
  { h1 = 0;
    h2 = 0;
    for (i=0; i<ntree; i++)
    { if (i != h1)
      { if (htcnt[i] > 0 && ht[i].parent == 0)
        { if (h1 == 0 || htcnt[i] < htcnt[h1])
          { if (h2 == 0 || htcnt[h1] < htcnt[h2])
              h2 = h1;
            h1 = i;
          }
          else if (h2 == 0 || htcnt[i] < htcnt[h2])
            h2 = i;
        }
      }
    }
    if (h2 == 0)
    { root = h1;
      break;
    }
    ht[h1].parent = ntree;
    ht[h2].parent = ntree;
    htcnt[ntree] = htcnt[h1] + htcnt[h2];
    ht[ntree].right = h1;
    ht[ntree].left = h2;
    ntree++;
  }
  
  /* write out tree */
  fwrite(&root, sizeof(root), 1, fout);
  fwrite(ht, sizeof(ht), 1, fout);
  fclose(fin);
  fclose(fout);
}

/* End of File */