home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1988 / 03 / mathews / mathews.ls2 < prev   
Text File  |  1979-12-31  |  6KB  |  219 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8. /*  001  24-Apr-87  tbtree.c
  9.  
  10.    Functions to create and traverse a threaded binary tree.
  11.  
  12.                   James Mathews
  13.                   Blue Sky Software
  14.                   172 Manor Drive
  15.                   Absecon, NJ  08201
  16.  
  17.    This code is hereby placed into the public domain.
  18.  
  19. */
  20.  
  21. #include <stdio.h>
  22. #include "tbtree.h"
  23.  
  24. #ifdef LINT_ARGS       /* setup for Microsoft C V 4.0 */
  25. #include <malloc.h>
  26. TREE_NODE *talloc();
  27. void add2tree(char *);
  28. TREE_NODE *linsert(TREE_NODE *);
  29. TREE_NODE *rinsert(TREE_NODE *);
  30. TREE_NODE *inorder_succ(TREE_NODE *);
  31. TREE_NODE *inorder_pred(TREE_NODE *);
  32. #else
  33. char *malloc();
  34. void add2tree();
  35. TREE_NODE *talloc(), *linsert(), *rinsert();
  36. TREE_NODE *inorder_succ(), *indorder_pred();
  37. #endif
  38.  
  39. /* define the root node for the threaded tree */
  40.  
  41. TREE_NODE root = { "|", 0, RBIT, &root, &root };
  42.  
  43.  
  44. /**********************************************************
  45.                   A D D 2 T R E E
  46.  **********************************************************/
  47.  
  48. void
  49. add2tree(word)         /* add given word to the B-tree */
  50. char *word;
  51. {
  52.    register int cmp;
  53.    register TREE_NODE *tp = &root;
  54.  
  55.    /* search tree to find word, add it if not there */
  56.  
  57.    while ((cmp = stricmp(word,tp->word)) != 0) {
  58.  
  59.       if (cmp < 0)        /* not equal, look to the left?  */
  60.  
  61.          if (tp->flags & LBIT)  /* is there a left child?  */
  62.             tp = tp->lchild;    /* yes, go look at it      */
  63.          else {
  64.             tp = linsert(tp);   /* no left child, make one */
  65.             break;
  66.          }
  67.  
  68.       else                /* not left, look right          */
  69.  
  70.          if (tp->flags & RBIT)  /* is there a right child? */
  71.             tp = tp->rchild;    /* yes, look it over */
  72.          else {
  73.             tp = rinsert(tp);   /* no right child, make one */
  74.             break;
  75.           }
  76.    }
  77.  
  78.    if (cmp == 0)                /* did we find the word?    */
  79.       tp->usage++;              /*  if so bump usage count  */
  80.  
  81.    else {                       /* must have added new word */
  82.  
  83.       tp->word = word;          /* point it to the word     */
  84.       tp->usage = 1;            /* new word in town         */
  85.    }
  86. }
  87.  
  88.  
  89. /**********************************************************
  90.                     R I N S E R T
  91.  **********************************************************/
  92.  
  93. static TREE_NODE *
  94. rinsert(tp)    /* insert new node as right child of tp */
  95. register TREE_NODE *tp;
  96. {
  97.    register TREE_NODE *new;
  98.  
  99.    if (new = talloc()) {         /* alloc new entry */
  100.  
  101.       new->rchild = tp->rchild;     /* new gets what tp had */
  102.       new->flags = tp->flags & RBIT;   /* as a right child  */
  103.  
  104.       new->lchild = tp;          /* lchild is thread to tp */
  105.  
  106.       tp->rchild = new;          /* new is rchild of tp   */
  107.       tp->flags |= RBIT;         /* real node, not thread */
  108.    }
  109.  
  110.    return(new);
  111. }
  112.  
  113.  
  114. /**********************************************************
  115.                      L I N S E R T
  116.  **********************************************************/
  117.  
  118. static TREE_NODE *
  119. linsert(tp)    /* insert new node as left child of tp */
  120. register TREE_NODE *tp;
  121. {
  122.    register TREE_NODE *new;
  123.  
  124.    if (new = talloc()) {         /* alloc new entry */
  125.  
  126.       new->lchild = tp->lchild;     /* new gets what tp had */
  127.       new->flags = tp->flags & LBIT;     /* as a left child */
  128.  
  129.       new->rchild = tp;          /* rchild is thread to tp */
  130.  
  131.       tp->lchild = new;          /* new is lchild of tp   */
  132.       tp->flags |= LBIT;         /* real node, not thread */
  133.    }
  134.  
  135.    return(new);
  136. }
  137.  
  138.  
  139. /**********************************************************
  140.                       T A L L O C
  141.  **********************************************************/
  142.  
  143. static TREE_NODE *
  144. talloc() {     /* allocate a TREE_NODE */
  145.  
  146. #define NODES_PER_ALLOC (50)
  147.  
  148.    static TREE_NODE *tp;
  149.    static int tidx = NODES_PER_ALLOC;
  150.  
  151.    /* this routine allocates space for TREE_NODE nodes.  It
  152.       exists to cut down on the number of calls to malloc(). */
  153.  
  154.    if (tidx < NODES_PER_ALLOC) /* free nodes from last alloc? */
  155.       return(&tp[tidx++]);     /*   yes, return the next one */
  156.  
  157.    /* allocate another block of TREE_NODE nodes */
  158.  
  159.    tp = (TREE_NODE *) malloc(sizeof(TREE_NODE) * NODES_PER_ALLOC);
  160.  
  161.    if (tp == NULL) {
  162.       printf("\nOut of memory in talloc()\n");
  163.       exit();
  164.    }
  165.  
  166.    tidx = 1;                   /* return # 1 next time */
  167.    return(tp);                 /* return # 0 this time */
  168. }
  169.  
  170.  
  171. /**********************************************************
  172.                  I N O R D E R _ S U C C
  173.  **********************************************************/
  174.  
  175. TREE_NODE *
  176. inorder_succ(tp)       /* return in-order successor of tp */
  177. register TREE_NODE *tp;
  178. {
  179.    register TREE_NODE *next;
  180.  
  181.    /* if the right child is a thread, it's the successor node */
  182.  
  183.    next = tp->rchild;
  184.  
  185.    /* but if the right child is a real node, the successor is
  186.       left-most child of the right child */
  187.  
  188.    if (tp->flags & RBIT)               /* real right child? */
  189.       while (next->flags & LBIT)       /*   find left-most  */
  190.          next = next->lchild;          /*   child of that   */
  191.  
  192.    return(next);                       /* return successor  */
  193. }
  194.  
  195.  
  196. /**********************************************************
  197.                   I N O R D E R _ P R E D
  198.  **********************************************************/
  199.  
  200. TREE_NODE *
  201. inorder_pred(tp)       /* return in-order predecessor of tp */
  202. register TREE_NODE *tp;
  203. {
  204.    register TREE_NODE *prev;
  205.  
  206.    /* if the left child is a thread, it's the predecessor */
  207.  
  208.    prev = tp->lchild;
  209.  
  210.    /* but if the left child is a real node, the predecessor is
  211.       right-most child of the left child */
  212.  
  213.    if (tp->flags & LBIT)               /* real left child?  */
  214.       while (prev->flags & RBIT)       /*   find right-most */
  215.          prev = prev->rchild;          /*   child of that   */
  216.  
  217.    return(prev);                       /* return predecessor */
  218. }
  219.