Listing 4 Binary tree with variably-sized data and node deletion.

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

/*  node definition */

typedef struct node {
   struct node    *left, *right, *parent;
   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)());
node *tree_delete(node *root, node *this_node);
void tree_free(node *root);


/* non-recursive tree insertion, if duplicate key  */
 * then new 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));
       if(this_node->left)
         this_node->left->parent = this_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));
      if(this_node->right)
         this_node->right->parent = this_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;
}

node *tree_delete(node *root, node *this_node)
{
   typedef enum tree_child {
      NOT_CHILD, LEFT_CHILD, RIGHT_CHILD } tree_child;
   tree_child child;
   node *temp;

   t_error = OK;

   if((!this_node) || (! root)) {
      t_error = NULL_PTR;
      return root;
   }

   if(root == this_node)
      child = NOT_CHILD;
   else if(this_node->parent->left == this_node)
      child = LEFT_CHILD;
   else if(this_node->parent->right == this_node)
      child = RIGHT_CHILD;
   else {
      t_error = LINK_ERROR;
      return root;
   }

   if(! this_node->right) {
      temp = this_node;
      this_node = this_node->left;
   }
   else if(! this_node->left) {
      temp = this_node;
      this_node = this_node->right;
   }
   else {
      temp = this_node->right;
      while(temp->left)
         temp = temp->left;
      temp->left = this_node->left;
      temp->left->parent = temp;
      temp = this_node;
      this_node = this_node->right;
   }

   switch(child) {

   case NOT_CHILD :
         free(temp->info);
      free(temp);
      if(this_node)
      this_node->parent = NULL;
         return this_node;

   case LEFT_CHILD :
      temp->parent->left = this_node;
      if(this_node)
      this_node->parent = temp->parent;
         free(temp->info);
         free(temp);
         break;

   case RIGHT_CHILD :
      temp->parent->right = this_node;
      if(this_node)
      this_node->parent = temp->parent;
         free(temp->info);
         free(temp);
      /* drop through to return */
   }
   return root;
}

/* 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("Delete");
   gets(buf);
   rec.key[0] = '\0';
   strncpy(rec.key, buf, KEYSIZE);
   rec.key[KEYSIZE] = '\0';


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

   printf("\n\t%d String(s) Deleted\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 */