home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_10 / 1010122a < prev    next >
Text File  |  1992-08-12  |  2KB  |  67 lines
  1.         /*      Figure 1 - Minimal Binary Tree Program -     */
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5.  
  6.  
  7. /*  Tree Node Definition  */
  8.  
  9. typedef struct node  {
  10.     struct node *left;
  11.     struct node *right;
  12.     char key;
  13. }node;
  14.  
  15.  
  16. /*  Recursive Minimal Tree Insertion Function  */
  17.  
  18. node *tree_insert(node *root, node *new_node)
  19. {
  20.     if(! root)  {
  21.     root = (node *) calloc(1, sizeof(node));
  22.     root->key = new_node->key;
  23.     return root;    /* return pointer to new memory block */
  24.     }
  25.     if(new_node->key == root->key)                      /* if ==, return */
  26.     return root;                    
  27.     else if(new_node->key < root->key)                  /* if <, go left */
  28.     root->left = tree_insert(root->left, new_node);
  29.     else                                                /* else go right */
  30.         root->right = tree_insert(root->right, new_node);
  31.  
  32.     return root;
  33. }
  34.  
  35. /*  Recursive Minimal Tree In-Order Traversal Function  */
  36.  
  37. void tree_trace(node *root)
  38. {
  39.     if(! root)
  40.     return;
  41.     tree_trace(root->left);
  42.     printf("\n%c", root->key);
  43.     tree_trace(root->right);
  44. }
  45.  
  46. /*  Minimal Tree Test Driver  */
  47.  
  48. void main(void)
  49. {
  50.     char c, m = 'm';
  51.     node *tree_root = NULL;
  52.     node this_node = { NULL, NULL, '\0' };
  53.  
  54.     this_node.key = m;
  55.     tree_root = tree_insert(tree_root, &this_node);
  56.  
  57.     for(c = '\x1';c < '\x5';c++)  {
  58.         this_node.key = m + c;
  59.     tree_insert(tree_root, &this_node);
  60.         this_node.key = m - c;
  61.     tree_insert(tree_root, &this_node);
  62.     }
  63.     tree_trace(tree_root);
  64.     printf("\n");
  65.     exit(0);    /* minimal, so let exit() free the dynamic memory */
  66. }
  67.