home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 24 / CD_ASCQ_24_0995.iso / vrac / dflt20.zip / HTREE.C < prev    next >
Text File  |  1992-06-16  |  2KB  |  65 lines
  1. /* ------------------- htree.c -------------------- */
  2.  
  3. #include "dflat.h"
  4. #include "htree.h"
  5.  
  6. struct htree *ht;
  7. int root;
  8. int treect;
  9.  
  10. /* ------ build a Huffman tree from a frequency array ------ */
  11. void buildtree(void)
  12. {
  13.     int i;
  14.  
  15.     treect = 256;
  16.     /* ---- preset node pointers to -1 ---- */
  17.     for (i = 0; i < treect; i++)    {
  18.         ht[i].parent = -1;
  19.         ht[i].right  = -1;
  20.         ht[i].left   = -1;
  21.     }
  22.     /* ---- build the huffman tree ----- */
  23.     while (1)   {
  24.         int h1 = -1, h2 = -1;
  25.         /* ---- find the two lowest frequencies ---- */
  26.         for (i = 0; i < treect; i++)   {
  27.             if (i != h1) {
  28.                 struct htree *htt = ht+i;
  29.                 /* --- find a node without a parent --- */
  30.                 if (htt->cnt > 0 && htt->parent == -1)   {
  31.                     /* ---- h1 & h2 -> lowest nodes ---- */
  32.                     if (h1 == -1 || htt->cnt < ht[h1].cnt) {
  33.                         if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
  34.                             h2 = h1;
  35.                         h1 = i;
  36.                     }
  37.                     else if (h2 == -1 || htt->cnt < ht[h2].cnt)
  38.                         h2 = i;
  39.                 }
  40.             }
  41.         }
  42.         /* --- if only h1 -> a node, that's the root --- */
  43.         if (h2 == -1) {
  44.             root = h1;
  45.             break;
  46.         }
  47.         /* --- combine two nodes and add one --- */
  48.         ht[h1].parent = treect;
  49.         ht[h2].parent = treect;
  50.         ht = realloc(ht, (treect+1) * sizeof(struct htree));
  51.         if (ht == NULL)
  52.             break;
  53.         /* --- the new node's frequency is the sum of the two
  54.             nodes with the lowest frequencies --- */
  55.         ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
  56.         /* - the new node points to the two that it combines */
  57.         ht[treect].right = h1;
  58.         ht[treect].left = h2;
  59.         /* --- the new node has no parent (yet) --- */
  60.         ht[treect].parent = -1;
  61.         treect++;
  62.     }
  63. }
  64.  
  65.