home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_10 / 1010124a < prev    next >
Text File  |  1992-08-12  |  5KB  |  266 lines
  1.  
  2.         /*  Figure 3 - Binary Tree with variably sized Data - */
  3.  
  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <conio.h>
  8.  
  9. /*  node definition */
  10.  
  11. typedef struct node  {
  12.     struct node     *left, *right;
  13.     void            *info;
  14.     size_t          info_size;
  15. }
  16. node;
  17.  
  18. /*  enumerated type to signify tree traversal order */
  19.     
  20. typedef enum tree_order {
  21.     NO_ORDER, PRE_ORDER, IN_ORDER, POST_ORDER } tree_order;
  22.  
  23. tree_order t_order = IN_ORDER;
  24.  
  25. /*  enumerated type for error checking */
  26.  
  27. typedef enum tree_error {
  28.     OK, LINK_ERROR, NULL_PTR, NO_MEMORY } tree_error;
  29.     
  30. tree_error t_error = OK;
  31.  
  32. /*  function prototypes */
  33.  
  34. void (*report)();
  35. int tree_insert(node **root, void *info, size_t info_size, int (*info_cmp)());
  36. void tree_trace(node *root);
  37. node *tree_find(node *root, void *info, int (*info_cmp)());
  38. void tree_free(node *root);
  39.  
  40.  
  41.  
  42. /*
  43.  *  non-recursive tree insertion, 
  44.  *  if duplicate key then new data substituted
  45.  *
  46.  *  returns:    1 on success    0 on failure
  47.  */
  48. int tree_insert(node **root, void *info, size_t info_size, int (*info_cmp)())
  49. {
  50.     node *this_node = *root;
  51.     int dif;
  52.     
  53.     t_error = OK;
  54.  
  55.     /*
  56.      *  does not enter while loop when instantiating root
  57.      */
  58.     while(this_node)  {
  59.     if(! (dif = info_cmp(info, this_node->info)))  {
  60.         free(this_node->info);
  61.         goto tree_load;
  62.     }
  63.     else if(dif < 0)  {
  64.         if(this_node->left)
  65.         this_node = this_node->left;
  66.         else  {
  67.         this_node->left = (node *) calloc(1, sizeof(node));
  68.         this_node = this_node->left;
  69.         goto tree_load;
  70.         }
  71.         }
  72.     else  {
  73.         if(this_node->right)
  74.         this_node = this_node->right;
  75.         else  {
  76.         this_node->right = (node *) calloc(1, sizeof(node));
  77.         this_node = this_node->right;
  78.         goto tree_load;
  79.         }
  80.     }
  81.     }
  82.  
  83.     /*
  84.      *  only arrives here when instantiating root
  85.      */
  86.     this_node = (node *) calloc(1, sizeof(node));
  87.     *root = this_node;
  88.  
  89. tree_load:
  90.     if(! this_node)  {
  91.         t_error = NO_MEMORY;
  92.     return 0;
  93.     }
  94.  
  95.     this_node->info = calloc(1, info_size);
  96.     if(! this_node->info)  {
  97.         t_error = NO_MEMORY;
  98.     free(this_node);
  99.     return 0;
  100.     }
  101.  
  102.     memmove(this_node->info, info, info_size);
  103.     this_node->info_size = info_size;
  104.  
  105.     return 1;
  106. }
  107.  
  108. /*
  109.  *  recursive tree traversal function with 3 traversing modes
  110.  */
  111. void tree_trace(node *root)
  112. {
  113.     if(! root)
  114.         return;
  115.  
  116.     switch(t_order)  {
  117.  
  118.     case PRE_ORDER :
  119.         report(root->info);
  120.         tree_trace(root->left);
  121.         tree_trace(root->right);
  122.             return;
  123.  
  124.         case IN_ORDER :
  125.         tree_trace(root->left);
  126.             report(root->info);
  127.         tree_trace(root->right);
  128.             return;
  129.  
  130.         case POST_ORDER :
  131.         tree_trace(root->left);
  132.         tree_trace(root->right);
  133.             report(root->info);
  134.             return;
  135.  
  136.     default:
  137.             return;
  138.     }
  139. }
  140.  
  141.  
  142. /*
  143.  *  non-recursive find, returns first matching entry or NULL
  144.  */
  145. node *tree_find(node *root, void *info, int (*info_cmp)())
  146. {
  147.     int cmp_val;
  148.     node *this_node = root;
  149.  
  150.     while(this_node)  {
  151.  
  152.     if(! (cmp_val = info_cmp(info, this_node->info)))
  153.         return this_node;
  154.     else if(cmp_val < 0)
  155.         this_node = this_node->left;
  156.     else
  157.         this_node = this_node->right;
  158.     }
  159.  
  160.     t_error = (root) ? OK : NULL_PTR;
  161.     return this_node;
  162. }
  163.  
  164.  
  165. /*
  166.  *  recursive post-order traversal to deallocate tree memory
  167.  */
  168. void tree_free(node *root)
  169. {
  170.     if(! root)
  171.         return;
  172.  
  173.     tree_free(root->left);
  174.     tree_free(root->right);
  175.     if(root->info)
  176.     free(root->info);
  177.     free(root);
  178. }
  179.  
  180.  
  181. /*
  182.  *  interactive tree test driver
  183.  */
  184.  
  185. #define KEYSIZE 80
  186.  
  187. typedef struct  {
  188.     char key[KEYSIZE];
  189.     int  id;
  190. }
  191. record;
  192.  
  193. record rec;
  194.  
  195. void prompt(char *verb)
  196. {
  197.     printf("\nEnter String to %s\t( <Enter> for none )\n>", verb);
  198. }
  199.  
  200. int rec_cmp(record *rec1, record *rec2)
  201. {
  202.     return strcmp(rec1->key, rec2->key);
  203. }
  204.  
  205. void tree_print(record *this_record)
  206. {
  207.     if(! this_record)
  208.         return;
  209.  
  210.     printf("Key: %s\nRecord Number: %d\n", this_record->key, this_record->id);
  211. }
  212.  
  213. void main(void)
  214. {
  215.     node *tree_root = NULL;
  216.     node *found = NULL;
  217.     char *orders[4] = { "no-order", "pre-order", "in-order", "post-order" };
  218.     char buf[KEYSIZE] = "";
  219.     int record_num = 0;
  220.     int count = 0;
  221.     int ch;
  222.  
  223.     prompt("Insert");
  224.  
  225.     while(*gets(buf))  {
  226.     strncpy(rec.key, buf, KEYSIZE);
  227.     rec.key[KEYSIZE] = '\0';
  228.     rec.id = ++record_num;
  229.     if(! (tree_insert(&tree_root, &rec, sizeof rec, rec_cmp)))  {
  230.         printf("\n\tTree Insertion Failure!\n");
  231.         exit(1);
  232.     }
  233.     prompt("Insert");
  234.     }
  235.  
  236.     prompt("Find");
  237.     gets(buf);
  238.     rec.key[0] = '\0';
  239.     strncpy(rec.key, buf, KEYSIZE);
  240.     rec.key[KEYSIZE] = '\0';
  241.  
  242.     found = tree_root;
  243.  
  244.     while(found = tree_find(found, &rec, rec_cmp))  {
  245.     tree_print(found->info);
  246.     found = found->right;
  247.     ++count;
  248.     }
  249.  
  250.     printf("\n\t%d String(s) Found\n", count);
  251.     printf("\n\tSelect Tree Traversal Type\n");
  252.     printf(
  253.     "\n\t\t1) pre-order\n\t\t2) in-order\n\t\t3) post-order\n\n\t>");
  254.  
  255.     ch = getch();
  256.     ch -= '0';
  257.     if((ch < PRE_ORDER)  ||  (ch > POST_ORDER))
  258.     ch = NO_ORDER;
  259.  
  260.     printf("\n\t... Walking Tree %s ...\n\n", orders[ch]);
  261.     t_order = ch;
  262.     report = tree_print;
  263.     tree_trace(tree_root);
  264.     tree_free(tree_root);
  265. }
  266.