home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_10 / 1010128a < prev   
Text File  |  1992-08-12  |  7KB  |  340 lines
  1.  
  2. /*  Figure 4 - Binary Tree with variably sized Data and node deletion  */
  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, *parent;
  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. node *tree_delete(node *root, node *this_node);
  39. void tree_free(node *root);
  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.     t_error = OK;
  53.  
  54.     /*
  55.      *  does not enter while loop when instantiating root
  56.      */
  57.     while(this_node)  {
  58.     if(! (dif = info_cmp(info, this_node->info)))  {
  59.         free(this_node->info);
  60.         goto tree_load;
  61.     }
  62.     else if(dif < 0)  {
  63.         if(this_node->left)
  64.         this_node = this_node->left;
  65.         else  {
  66.         this_node->left = (node *) calloc(1, sizeof(node));
  67.         if(this_node->left)
  68.             this_node->left->parent = this_node;
  69.         this_node = this_node->left;
  70.         goto tree_load;
  71.         }
  72.     }
  73.     else  {
  74.         if(this_node->right)
  75.         this_node = this_node->right;
  76.         else  {
  77.         this_node->right = (node *) calloc(1, sizeof(node));
  78.         if(this_node->right)
  79.             this_node->right->parent = this_node;
  80.         this_node = this_node->right;
  81.         goto tree_load;
  82.         }
  83.     }
  84.     }
  85.  
  86.     /*
  87.      *  only arrives here when instantiating root
  88.      */
  89.     this_node = (node *) calloc(1, sizeof(node));
  90.     *root = this_node;
  91.  
  92. tree_load:
  93.     if(! this_node)  {
  94.         t_error = NO_MEMORY;
  95.     return 0;
  96.     }
  97.  
  98.     this_node->info = calloc(1, info_size);
  99.     if(! this_node->info)  {
  100.         t_error = NO_MEMORY;
  101.     free(this_node);
  102.     return 0;
  103.     }
  104.  
  105.     memmove(this_node->info, info, info_size);
  106.     this_node->info_size = info_size;
  107.  
  108.     return 1;
  109. }
  110.  
  111. /*
  112.  *  recursive tree traversal function with 3 traversing modes
  113.  */
  114. void tree_trace(node *root)
  115. {
  116.     if(! root)
  117.         return;
  118.  
  119.     switch(t_order)  {
  120.  
  121.     case PRE_ORDER :
  122.         report(root->info);
  123.         tree_trace(root->left);
  124.         tree_trace(root->right);
  125.             return;
  126.  
  127.         case IN_ORDER :
  128.         tree_trace(root->left);
  129.             report(root->info);
  130.         tree_trace(root->right);
  131.             return;
  132.  
  133.         case POST_ORDER :
  134.         tree_trace(root->left);
  135.         tree_trace(root->right);
  136.             report(root->info);
  137.             return;
  138.  
  139.     default:
  140.             return;
  141.     }
  142. }
  143.  
  144.  
  145. /*
  146.  *  non-recursive find, returns first matching entry or NULL
  147.  */
  148. node *tree_find(node *root, void *info, int (*info_cmp)())
  149. {
  150.     int cmp_val;
  151.     node *this_node = root;
  152.  
  153.     while(this_node)  {
  154.  
  155.     if(! (cmp_val = info_cmp(info, this_node->info)))
  156.         return this_node;
  157.     else if(cmp_val < 0)
  158.         this_node = this_node->left;
  159.     else
  160.         this_node = this_node->right;
  161.     }
  162.  
  163.     t_error = (root) ? OK : NULL_PTR;
  164.     return this_node;
  165. }
  166.  
  167. node *tree_delete(node *root, node *this_node)
  168. {
  169.     typedef enum tree_child {
  170.         NOT_CHILD, LEFT_CHILD, RIGHT_CHILD } tree_child;
  171.  
  172.     tree_child child;
  173.     node *temp;
  174.  
  175.     t_error = OK;
  176.  
  177.     if((! this_node)  ||  (! root))  {
  178.         t_error = NULL_PTR;
  179.         return root;
  180.     }
  181.  
  182.     if(root == this_node)
  183.         child = NOT_CHILD;
  184.     else if(this_node->parent->left == this_node)
  185.         child = LEFT_CHILD;
  186.     else if(this_node->parent->right == this_node)
  187.         child = RIGHT_CHILD;
  188.     else  {
  189.         t_error = LINK_ERROR;
  190.         return root;
  191.     }
  192.  
  193.     if(! this_node->right)  {
  194.         temp = this_node;
  195.         this_node = this_node->left;
  196.     }
  197.     else if(! this_node->left)  {
  198.         temp = this_node;
  199.         this_node = this_node->right;
  200.     }
  201.     else  {
  202.         temp = this_node->right;
  203.         while(temp->left)
  204.             temp = temp->left;
  205.         temp->left = this_node->left;
  206.         temp->left->parent = temp;
  207.         temp = this_node;
  208.         this_node = this_node->right;
  209.     }
  210.  
  211.     switch(child)  {
  212.  
  213.         case NOT_CHILD :
  214.             free(temp->info);
  215.         free(temp);
  216.         if(this_node)
  217.         this_node->parent = NULL;
  218.             return this_node;
  219.  
  220.         case LEFT_CHILD :
  221.         temp->parent->left = this_node;
  222.         if(this_node)
  223.         this_node->parent = temp->parent;
  224.             free(temp->info);
  225.             free(temp);
  226.             break;
  227.  
  228.         case RIGHT_CHILD :
  229.         temp->parent->right = this_node;
  230.         if(this_node)
  231.         this_node->parent = temp->parent;
  232.             free(temp->info);
  233.             free(temp);
  234.         /* drop through to return */
  235.     }
  236.     return root;
  237. }
  238.  
  239.  
  240. /*
  241.  *  recursive post-order traversal to deallocate tree memory
  242.  */
  243. void tree_free(node *root)
  244. {
  245.     if(! root)
  246.         return;
  247.  
  248.     tree_free(root->left);
  249.     tree_free(root->right);
  250.     if(root->info)
  251.     free(root->info);
  252.     free(root);
  253. }
  254.  
  255.  
  256. /*
  257.  *  interactive tree test driver
  258.  */
  259.  
  260. #define KEYSIZE 80
  261.  
  262. typedef struct  {
  263.     char key[KEYSIZE];
  264.     int  id;
  265. }
  266. record;
  267.  
  268. record rec;
  269.  
  270. void prompt(char *verb)
  271. {
  272.     printf("\nEnter String to %s\t( <Enter> for none )\n>", verb);
  273. }
  274.  
  275. int rec_cmp(record *rec1, record *rec2)
  276. {
  277.     return strcmp(rec1->key, rec2->key);
  278. }
  279.  
  280. void tree_print(record *this_record)
  281. {
  282.     if(! this_record)
  283.         return;
  284.  
  285.     printf("Key: %s\nRecord Number: %d\n", this_record->key, this_record->id);
  286. }
  287.  
  288. void main(void)
  289. {
  290.     node *tree_root = NULL;
  291.     node *found = NULL;
  292.     char *orders[4] = { "no-order", "pre-order", "in-order", "post-order" };
  293.     char buf[KEYSIZE] = "";
  294.     int record_num = 0;
  295.     int count = 0;
  296.     int ch;
  297.  
  298.     prompt("Insert");
  299.  
  300.     while(*gets(buf))  {
  301.     strncpy(rec.key, buf, KEYSIZE);
  302.     rec.key[KEYSIZE] = '\0';
  303.     rec.id = ++record_num;
  304.     if(! (tree_insert(&tree_root, &rec, sizeof rec, rec_cmp)))  {
  305.         printf("\n\tTree Insertion Failure!\n");
  306.         exit(1);
  307.     }
  308.     prompt("Insert");
  309.     }
  310.  
  311.     prompt("Delete");
  312.     gets(buf);
  313.     rec.key[0] = '\0';
  314.     strncpy(rec.key, buf, KEYSIZE);
  315.     rec.key[KEYSIZE] = '\0';
  316.  
  317.  
  318.     while(found = tree_find(tree_root, &rec, rec_cmp))  {
  319.     tree_print(found->info);
  320.     tree_root = tree_delete(tree_root, found);
  321.     ++count;
  322.     }
  323.  
  324.     printf("\n\t%d String(s) Deleted\n", count);
  325.     printf("\n\tSelect Tree Traversal Type\n");
  326.     printf(
  327.     "\n\t\t1) pre-order\n\t\t2) in-order\n\t\t3) post-order\n\n\t>");
  328.  
  329.     ch = getch();
  330.     ch -= '0';
  331.     if((ch < PRE_ORDER)  ||  (ch > POST_ORDER))
  332.     ch = NO_ORDER;
  333.  
  334.     printf("\n\t... Walking Tree %s ...\n\n", orders[ch]);
  335.     t_order = ch;
  336.     report = tree_print;
  337.     tree_trace(tree_root);
  338.     tree_free(tree_root);
  339. }
  340.