Listing 3 Binary tree with variably-sized data.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>

/*  node definition */

typedef struct node {
   struct node    *left, *right;
   void           *info;
   size_t         info_size;
}
node;

/*  enumerated type to signify tree traversal order */

typedef enum tree_order {
   NO_ORDER, PRE_ORDER, IN_ORDER, POST_ORDER } tree_order;

tree_order t_order = IN_ORDER;

/*  enumerated type for error checking */

typedef enum tree_error {
   OK, LINK_ERROR, NULL_PTR, NO_MEMORY } tree_error;

tree_error t_error = OK;

/*  function prototypes */

void (*report)();
int tree_insert(node **root, void *info,
             size_t info_size, int (*info_cmp) ());
void tree_trace(node *root);
node *tree_find(node *root, void *info, int (*info_cmp) ());
void tree_-free(node *root);


/*  non-recursive tree insertion, if duplicate      */
 *  key thennew data substituted returns: 1 on      */
 *  success 0 on failure                            */

int tree_insert(node **root, void *info, size_t info_size,
             int (*info_cmp)())
{
   node *this_node = *root;
   int dif;

   t_error = OK;

   /*  does not enter while loop when */
   /*  instantiating root             */

   while(this_node) {
   if(! (dif = info_cmp(info, this_node->info))) {
      free(this_node->info);
      goto tree_load;
   }
   else if(dif < 0) {
      if(this_node->left)
      this_node = this_node->left;
      else {
      this_node->left = (node *) calloc(1, sizeof(node));
      this_node = this_node->left;
      goto tree_load;
      }
      }
   else {
      if(this_node->right)
      this_node = this_node->right;
      else {
      this_node->right = (node *) calloc(1, sizeof(node));
      this_node = this_node->right;
      goto tree_load;
      }
   }
   }

   /*  only arrives here when instantiating root */

    this_node = (node *) calloc(1, sizeof(node));
   *root = this_node;

tree_load:
   if(! this_node) {
      t_error = NO_MEMORY;
   return 0;
   }

   this_node->info = calloc(1, info_size);
   if(! this_node->info) {
      t_error = NO_MEMORY;
   free(this_node);
   return ) 0;
   }

   memmove(this_node->info, info, info_size);
   this_node->info_size = info_size;

   return 1;
}

/*  recursive tree traversal function with 3 */
 *  traversing modes                         */

void tree_trace(node *root)
{
   if(! root)
      return;

   switch(t_order) {

   case PRE_ORDER:
       report(root->info);
       tree_trace(root->left);
       tree_trace(root->right;
         return;

   case IN_ORDER:
      tree_trace(root->left);
         report(root->info);
      tree_trace(root->right);
         return;

   case POST_ORDER:
      tree_trace(root->left);
      tree_trace(root->right);
         report(root->info);
         return;

   default:
         return;
   }
}

/*  non-recursive find, returns first matching */
*  entry or NULL                               */

node *tree_find(node *root, void *info, int (*info_cmp)())
{

   int cmp_val;
   node *this_node = root;

   while(this_node) {

   if(! (cmp_val = info_cmp(info, this_node->info)))
       return this_node;
   else if(cmp_val < 0)
       this_node = this_node->left;
   else
       this_node = this_node->right;
   }

   t_error = (root)? OK: NULL_PTR;
   return this_node;
}

/*  recursive post-order traversal to */
 *  deallocate tree memory            */

void tree_free(node *root)
{
   if(! root)
      return;
   tree_free(root->left);
   tree_free(root->right);
   if(root->info)
   free(root->info);
   free(root);
}


/*  interactive tree test driver

#define KEYSIZE 80

typedef struct {
   char key[KEYSIZE];
   int id;
}
record;

record rec;

void prompt(char *verb)
{
   printf("\nEnter String to %s\t( <Enter> for none)\n>",
         verb);
}

int rec_cmp(record *rec1, record *rec2)
{
   return strcmp(rec1->key, rec2->key);
}

void tree_print(record *this_record)
{
   if(! this_record)
      return;

   printf("Key: %s\nRecord Number: %d\n",
         this_record->key, this_record->id);
}

void main(void)
{
   node *tree_root = NULL;
   node *found = NULL;
   char *orders[4] = { "no-order", "pre-order",
                   "in-order", "post-order"};
   char buf[KEYSIZE] = "";
   int record_num = 0;
   int count = 0;
   int ch;

   prompt ("Insert");

   while(*gets(buf)) {
   strncpy(rec.key, buf, KEYSIZE);
   rec.key[KEYSIZE] = '\0';
   rec.id = ++record_num;
   if(! (tree_insert(&tree_root, &rec, sizeof rec,
       rec_cmp))) {
       printf("\n\tTree Insertion Failure!\n");
       exit(1);
   }
   prompt("Insert");
   }

   prompt("Find");
   gets(buf);
   rec.key[0] = '\0';
   strncpy(rec.key, buf, KEYSIZE);
   rec.key[KEYSIZE] = '\0';

   found = tree_root;

   while(found = tree_find(found, &rec, rec_cmp)) {
   tree_print(found->info;
   found = found->right;
   ++count;
   }

   printf("\n\t%d String(s) Found\n", count);
   printf("\n\tSelect Tree Traversal Type\n");
   printf(
   "\n\t\t1) pre-order\n\t\t2) in-order\n\t\t3)
           post-order\n\n\t>");

   ch = getch();
   ch -= '0';
   if((ch < PRE_ORDER) || (ch > POST_ORDER))
   ch = NO_ORDER;

   printf("\n\t... Walking Tree %s ...\n\n", orders [ch]);
   t_order = ch;
   report = tree_print;
   tree_trace(tree_root);
   tree_free(tree_root);
}
/* End of File */