home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_10 / 1010123a < prev    next >
Text File  |  1992-08-12  |  2KB  |  84 lines
  1.         /*      Figure 2 - Slightly Enhanced Binary Tree Program -     */
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <string.h>
  6.  
  7. /*  Tree Node Definition with String Key */
  8.  
  9. typedef struct node  {
  10.     struct node *left;
  11.     struct node *right;
  12.     char key[BUFSIZ];
  13. }node;
  14.  
  15.  
  16. /*  Non-Recursive Tree Insertion Function  */
  17.  
  18. void tree_insert(node **root, node *new_node)
  19. {
  20.     node *this_node = *root;
  21.     int dif;
  22.     
  23.     while(this_node)  {
  24.     if(! (dif = strcmp(new_node->key, this_node->key)))
  25.             goto key_copy;
  26.         else if(dif < 0)  {
  27.             if(this_node->left)
  28.                 this_node = this_node->left;
  29.             else  {
  30.                 this_node->left = (node *)calloc(1, sizeof(node));
  31.                 this_node = this_node->left;
  32.                 goto key_copy;
  33.             }
  34.         }
  35.         else  {
  36.             if(this_node->right)
  37.                 this_node = this_node->right;
  38.             else  {
  39.                 this_node->right = (node *)calloc(1, sizeof(node));
  40.                 this_node = this_node->right;
  41.                 goto key_copy;
  42.             }
  43.         }
  44.     }
  45.  
  46.     /*
  47.      *  only arrives here when instatiating root
  48.      */
  49.     this_node = (node *)calloc(1, sizeof(node));
  50.     *root = this_node;
  51.  
  52. key_copy:
  53.     strncpy(this_node->key, new_node->key, BUFSIZ);
  54.     this_node->key[BUFSIZ] = '\0';
  55. }
  56.  
  57. /*  Recursive In-Order Traversal Function Prints Key String */
  58.  
  59. void tree_trace(node *root)
  60. {
  61.     if(! root)
  62.     return;
  63.     tree_trace(root->left);
  64.     printf("%s\n", root->key);
  65.     tree_trace(root->right);
  66. }
  67.  
  68. /*  String Key Tree Test Driver  */
  69.  
  70. void main(void)
  71. {
  72.     node *tree_root = NULL;
  73.     node this_node = { NULL, NULL, "" };
  74.     char *str[5] = { "some", "duplicate", "and", "duplicate", "keys" };
  75.     int i;
  76.  
  77.     for(i = 0;i < 5;i++)  {
  78.         strcpy(this_node.key, str[i]);
  79.         tree_insert(&tree_root, &this_node);
  80.     }
  81.     tree_trace(tree_root);
  82.     exit(0);
  83. }
  84.