bst.c

bst.c

contents ::

  app.c
  bst.c
  bst.h
  mylib.c
  mylib.h

#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
#include "mylib.h"

struct bstnode {
  char *key;
  bst left;
  bst right;
};

bst bst_new(){
  return NULL;
}

char *bst_search(bst b, char *key){
  if(b == NULL) return NULL;
  /* strcmp(cs,ct) returns 0  if cs==ct
     strcmp(cs,ct) returns <0 if cs<ct
     strcmp(cs,ct) returns >0 if cs>ct
  */
  if(!strcmp(key, b->key)) return b->key;
  else if(strcmp(key, b->key)<0)
    return bst_search(b->left, key);
  else
    return bst_search(b->right, key);
}

bst bst_insert(bst b, char *key){
  if(b == NULL){
    b = emalloc(sizeof *b);
    b->key = emalloc((strlen(key)+1) * sizeof (char));
    strcpy(b->key, key);
    b->left = NULL;
    b->right = NULL;
  } else if(strcmp(key, b->key)<0)
    b->left = bst_insert(b->left, key);
  else if(strcmp(key, b->key)>0)
    b->right = bst_insert(b->right, key);
  return b;
}

void bst_inorder(bst b, void f(char *s)){
  if(b == NULL) return;
  bst_inorder(b->left, f);
  f(b->key);
  bst_inorder(b->right, f);
}

void bst_preorder(bst b, void f(char *s)){
  if(b == NULL) return;
  f(b->key);
  bst_inorder(b->left, f);
  bst_inorder(b->right, f);
}

void bst_postorder(bst b, void f(char *s)){
  if(b == NULL) return;
  bst_inorder(b->left, f);
  bst_inorder(b->right, f);
  f(b->key);
}

bst bst_delete(bst b, char *key){
  if(b == NULL) return NULL;             /* Key does not exist */
  if(strcmp(key, b->key)<0)
    b->left = bst_delete(b->left, key);  /* Key may be in the left subtree */
  else if(strcmp(key, b->key)>0)
    b->right = bst_delete(b->right, key);/* Key may be in the right subtree */
  else { /* We have found it, now erradicate it! */
    bst temp = NULL;
    if(b->left!=NULL && b->right!=NULL){
      temp = b->right;
      while(temp->left!=NULL)
         temp = temp->left;
      free(b->key);
      b->key = emalloc((strlen(temp->key)+1) * sizeof (char));
      strcpy(b->key, temp->key);
      b->right = bst_delete(b->right, key);
    } else {
      if(b->left!=NULL)
         temp = b->left;
      else
         temp = b->right;
      free(b->key);
      free(b);
      b = temp;
    }
  }
  return b;
}

James Little