11. References and Records

//------------------------------------------------------------------
/* binary tree demo program */
#define _GNU_SOURCE // getline(), tdestroy()

#include <stdio.h>
#include <search.h> // tsearch(), tfind(), tdelete(), tdestroy(); twalk()
#include <stdlib.h> // rand(), malloc(), free()

static VISIT walk_type;

int compar_int( const void * elm1, const void * elm2) {
  return ( *((int *) elm1) - *((int *) elm2) );
}

void walk( const void * node, const VISIT method, const int level) {
  int * data;
  
  data = *(int **)node;
  
  if(method == walk_type)
    fprintf( stdout, "%d ", *data );
  if( method == leaf )
    fprintf( stdout, "%d ", *data );
  return;
}

void free_elmt( void * node ){
  free( node );

  return;
}

int main( void ) {

  void * root = NULL;
    
  int i, *ptr;

  // first generate 20 random inserts
  for( i = 0; i < 20; i++ ) {
    ptr = malloc(sizeof(int));
    *ptr = (int)( 1000 * (double)rand() / (RAND_MAX + 1.0) );

    if( tsearch( ptr, &root, compar_int ) == NULL ) {
      perror("tsearch");
      exit(1);
    }
  }

  // now dump out the tree all three ways
  fprintf(stdout, "Pre order\n");
  walk_type = preorder;
  twalk( root, walk );
  printf("\n");

  fprintf(stdout, "In order\n");
  walk_type = postorder; // /!\  postorder is rather confusing
  twalk( root, walk );
  printf("\n");

  fprintf(stdout, "Post order\n");
  walk_type = endorder;
  twalk( root, walk );
  printf("\n");

  // prompt until EOF
  char * istr;
  size_t size;
  ssize_t ret;

  while(1) {
    fprintf(stdout, "Search? : ");
    size = 0;
    istr = NULL;
    ret = getline( &istr, &size, stdin );
    if( ret == -1 )
      break;
    sscanf( istr, "%d", &i );
    free(istr);

    if( tfind( &i, &root, compar_int ) == NULL )
      fprintf( stdout, "No %d in tree\n", i );
    else
      fprintf( stdout, "Found %d\n", i );
  }

  tdestroy( root, free_elmt );
  
  return 0;
}