basic binary tree routines

Basic binary search tree routines

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

struct tnode {
 int data;
 struct tnode *left;
 struct tnode *right;
};

/* insert, swap, search value, search minimum and search maximum values */
struct tnode *tnode_insert(struct tnode *p, int value);
struct tnode *tnode_swap(struct tnode *p);
struct tnode *tnode_search(struct tnode *p, int key);
struct tnode *tnode_searchmin(struct tnode *p);
struct tnode *tnode_searchmax(struct tnode *p);

/* destroy, count tree nodes */
void tnode_destroy(struct tnode *p);
int tnode_count(struct tnode *p);

/* print binary tree inorder, preorder, postorder [recursive] */
void print_inorder(struct tnode *p);
void print_preorder(struct tnode *p);
void print_postorder(struct tnode *p);

int main(void) {
 int demo_nr[] = {1, 3, 4, 7, 2, 9, 9, 0, 5, 6, 8, 7, 1, 2, 4};
 struct tnode *root = NULL;
 struct tnode *searchval = NULL;
 int querry = 0;
 int i = 0;

 /* demo: insert some nr's into the binary tree */
 for(i = 0; i < 15; i++)
  root = tnode_insert(root, demo_nr[i]);

 printf("=-=-=\n");
 printf("Total number of tree nodes: %d\n", tnode_count(root));
 printf("inorder  : ");
 print_inorder(root);
 printf("\n");

 printf("preorder : ");
 print_preorder(root);
 printf("\n");

 printf("postorder: ");
 print_postorder(root);
 printf("\n");

 printf("=-=-=\n");
 printf("Enter integer, find: ");
 scanf("%d", &querry);
 searchval = tnode_search(root, querry);
 if(searchval == NULL)
  printf(" * %d Not! found in btree\n", querry);
 else
  printf(" * Found! %d in btree\n", searchval->data);

 searchval = NULL;
 printf("Searching for Minimum value\n");
 searchval = tnode_searchmin(root);
 if(searchval == NULL)
  printf(" * Minimum Not! found in btree ?\n");
 else
  printf(" * Found! minimum value %d in btree\n", searchval->data);

 searchval = NULL;
 printf("Searching for Maximum value\n");
 searchval = tnode_searchmax(root);
 if(searchval == NULL)
  printf(" * Maximum Not! found in btree ?\n");
 else
  printf(" * Found! Maximum value %d in btree\n", searchval->data);

 printf("=-=-=\n");
 printf("Exchanging all tree nodes: left <-> right\n");
 root = tnode_swap(root);

 printf("inorder  : ");
 print_inorder(root);
 printf("\n");

 printf("preorder : ");
 print_preorder(root);
 printf("\n");

 printf("postorder: ");
 print_postorder(root);
 printf("\n");

 printf("=-=-=\n");
 printf("Destroying btree... bye!\n");
 tnode_destroy(root);

 return 0;
}

/* insert a tnode into the binary tree */
struct tnode *tnode_insert(struct tnode *p, int value) {
 struct tnode *tmp_one = NULL;
 struct tnode *tmp_two = NULL;

 if(p == NULL) {
  /* insert [new] tnode as root node */
  p = (struct tnode *)malloc(sizeof(struct tnode));
  p->data = value;
  p->left = p->right = NULL;
 } else {
  tmp_one = p;
  /* Traverse the tree to get a pointer to the specific tnode */
  /* The child of this tnode will be the [new] tnode */
  while(tmp_one != NULL) {
   tmp_two = tmp_one;
   if(tmp_one ->data > value)
    tmp_one = tmp_one->left;
   else
    tmp_one = tmp_one->right;
  }

  if(tmp_two->data > value) {
   /* insert [new] tnode as left child */
   tmp_two->left = (struct tnode *)malloc(sizeof(struct tnode));
   tmp_two = tmp_two->left;
   tmp_two->data = value;
   tmp_two->left = tmp_two->right = NULL;
  } else {
   /* insert [new] tnode as left child */
   tmp_two->right = (struct tnode *)malloc(sizeof(struct tnode));
   tmp_two = tmp_two->right;
   tmp_two->data = value;
   tmp_two->left = tmp_two->right = NULL;
  }
 }

 return(p);
}

/* print binary tree inorder */
void print_inorder(struct tnode *p) {
 if(p != NULL) {
  print_inorder(p->left);
  printf("%d ", p->data);
  print_inorder(p->right);
 }
}

/* print binary tree preorder */
void print_preorder(struct tnode *p) {
 if(p != NULL) {
  printf("%d ", p->data);
  print_preorder(p->left);
  print_preorder(p->right);
 }
}

/* print binary tree postorder */
void print_postorder(struct tnode *p) {
 if(p != NULL) {
  print_postorder(p->left);
  print_postorder(p->right);
  printf("%d ", p->data);
 }
}

/* returns the total number of tree nodes */
int tnode_count(struct tnode *p) {
 if(p == NULL)
  return 0;
 else {
  if(p->left == NULL && p->right == NULL)
   return 1;
  else
   return(1 + (tnode_count(p->left) + tnode_count(p->right)));
 }
}

/* exchange all left and right tnodes */
struct tnode *tnode_swap(struct tnode *p) {
 struct tnode *tmp_one = NULL;
 struct tnode *tmp_two = NULL;

 if(p != NULL) {
  tmp_one = tnode_swap(p->left);
  tmp_two = tnode_swap(p->right);
  p->right = tmp_one;
  p->left  = tmp_two;
 }

 return(p);
}

/* locate a value in the btree */
struct tnode *tnode_search(struct tnode *p, int key) {
 struct tnode *temp;
 temp = p;

 while(temp != NULL) {
  if(temp->data == key)
   return temp;
  else if(temp->data > key)
   temp = temp->left;
  else
   temp = temp->right;
 }

 return NULL;
}

/* locate a minimum value in the btree */
struct tnode *tnode_searchmin(struct tnode *p) {
 if(p == NULL)
  return NULL;
 else
  if(p->left == NULL)
   return p;
  else
   return tnode_searchmin(p->left);
}

/* locate a maximum value in the btree */
struct tnode *tnode_searchmax(struct tnode *p) {
 if(p != NULL)
  while(p->right != NULL)
   p = p->right;

 return p;
}

/* destroy the binary tree */
void tnode_destroy(struct tnode *p) {
 if(p != NULL) {
  tnode_destroy(p->left);
  tnode_destroy(p->right);

  free(p);
 }
}