Recursive Binary Search Tree

binary_search_tree.cpp

#include <iostream>
#include <iomanip>
#include "binary_search_tree.h"

bool
BinarySearchTree::lookup(node* n, int d)
{
  if(!n){
    return false;
  }
  
  if(n->data == d){
    return true;
  }/*else if(d < n->data){
    return lookup(n->left, d);
  }else{
    return lookup(n->right, d);
  }
  */
  return lookup((d < n->data)? n->left:n->right , d);
}

BinarySearchTree::node*
BinarySearchTree::add(node* n, int d)
{
  if(!n){
    n = new node(d);
    return n;
  }

  if(d <= n->data){
    n->left = add(n->left, d); 
  }else if(d > n->data){
    n->right = add(n->right, d); 
  }

  return n;
}

void
BinarySearchTree::add(node** n, int d)
{
  if(!*n){
    *n = new node(d);
    return;
  }

  /*
  if(d <= (*n)->data){
    add(&((*n)->left), d); 
  }else if(d > (*n)->data){
    add(&((*n)->right), d); 
  }
  */
  add((d <= (*n)->data)? &((*n)->left):&((*n)->right), d);
}

int
BinarySearchTree::getMin(node *n)
{
  while(n->left){
    n = n->left;
  }
  return n->data;
}

int
BinarySearchTree::getMax(node *n)
{
  while(n->right){
    n = n->right;
  }
  return n->data;
}

BinarySearchTree::node*
BinarySearchTree::discard(node* n, int d)
{
  if(!n){
    return n;
  }
  
  if(d == n->data){
    if(!n->left){ //node has only right child or no child
      node* tmp = n->right;
      delete n;
      return tmp;
    }else if(!n->right){ //node has only left child
      node* tmp = n->left;
      delete n;
      return tmp;
    }else{ //node has two children
      n->data = getMin(n->right);
      n->right = discard(n->right, n->data);
      //n->data = getMax(n->left);
      //n->left = discard(n->left, n->data);
    }
  }else if(d < n->data){
    n->left = discard(n->left, d);
  }else{
    n->right = discard(n->right, d);
  }

  return n;
}

bool
BinarySearchTree::discard(node** n, int d)
{
  if(!*n){
    return false;
  }
  
  if(d == (*n)->data){
    if(!(*n)->left){ //node has only right child or no child
      node* tmp = *n;
      *n = (*n)->right;
      delete tmp;
      return true;
    }else if(!(*n)->right){ //node has only left child
      node* tmp = *n;
      *n = (*n)->left;
      delete tmp;
      return true;
    }else{ //node has two children
      (*n)->data = getMin((*n)->right);
      return discard(&((*n)->right), (*n)->data);
      //(*n)->data = getMax((*n)->left);
      //return discard(&((*n)->left), (*n)->data);
    }
  }/*else if(d < (*n)->data){
    return discard(&((*n)->left), d);
  }else{
    return discard(&((*n)->right), d);
  }*/
  return discard((d < (*n)->data)? &((*n)->left):&((*n)->right), d);
}

void
BinarySearchTree::inorder(node* n)
{
  if(!n) return;
  
  inorder(n->left);
  
  std::cout << std::setw(4) << n->data;

  inorder(n->right);
}

void
BinarySearchTree::preorder(node* n)
{
  if(!n) return;
  
  std::cout << std::setw(4) << n->data;
  
  preorder(n->left);
  
  preorder(n->right);
}

void
BinarySearchTree::postorder(node* n)
{
  if(!n) return;
  
  postorder(n->left);
  
  postorder(n->right);
  
  std::cout << std::setw(4) << n->data;
}

bool
BinarySearchTree::find(int d)
{
  return lookup(root, d);
}

void
BinarySearchTree::insert(int d)
{
  root = add(root, d);
  //add(&root, d);
}

bool
BinarySearchTree::remove(int d)
{
  return (discard(root, d) != 0); 
  //return discard(&root, d); 
}

void
BinarySearchTree::inorderPrint()
{
  inorder(root);
  std::cout << std::endl;
}

void
BinarySearchTree::preorderPrint()
{
  preorder(root);
  std::cout << std::endl;
}

void
BinarySearchTree::postorderPrint()
{
  postorder(root);
  std::cout << std::endl;
}  

binary_search_tree.h

class BinarySearchTree
{
  private:
    struct node
    {   
      node* left;
      node* right;
      int data;
      
      //constructor
      node(int const &d):left(0), right(0), data(d){}
    };  
    
    node* root;

    bool lookup(node* n, int d); 
    
    int getMin(node* n); 
    
    int getMax(node* n); 
    
    node* add(node* n, int d); 
    void add(node** n, int d); 

    node* discard(node* n, int d); 
    bool discard(node** n, int d); 

    void inorder(node* n); 
    
    void preorder(node* n); 
    
    void postorder(node* n); 


  public:
 
    BinarySearchTree():root(0)
    {   
    };  
   
    ~BinarySearchTree()
    {   
      root = 0;
    };

    bool isEmpty() const { return root==0; };

    bool find(int d);

    void insert(int d);

    bool remove(int d);

    void inorderPrint();

    void preorderPrint();

    void postorderPrint();
};

main.cpp

#include "binary_search_tree.h"
#include <iostream>

int main(){
  
  BinarySearchTree bst;

  bst.insert(25); 
  bst.insert(15); 
  bst.insert(50); 
  bst.insert(10); 
  bst.insert(35); 
  bst.insert(22); 
  bst.insert(70); 
  bst.insert(90); 
  bst.insert(44); 
  bst.insert(12); 
  bst.insert(4); 
  bst.insert(18); 
  bst.insert(31); 
  bst.insert(66); 
  bst.insert(24); 

  std::cout << bst.find(22) << std::endl;
  std::cout << bst.find(44) << std::endl; 
  std::cout << bst.find(77) << std::endl;

  bst.preorderPrint();
  bst.postorderPrint();
  bst.inorderPrint();
  
  // remove one node without child
  bst.remove(18);
  bst.inorderPrint();
  
  // remove one node with two children
  bst.remove(50);
  bst.inorderPrint();
  
  // remove one node with right child only
  bst.remove(70);
  bst.inorderPrint();
  
  // remove one node without child
  bst.remove(90);
  bst.inorderPrint();

  // remove one node with left child only
  bst.remove(66);
  bst.inorderPrint();

  return 0;
}

makefile

# define the C compiler to use
CC = g++

# define any compile-time flags
CFLAGS = -ggdb

# define the compile command by compiler and flags
CC_OPTIONS = $(CC) $(CFLAGS)

# define the C source files
SRCS = binary_search_tree.cpp main.cpp

# define the C object files 
#
# This uses Suffix Replacement within a macro:
#   $(name:string1=string2)
#         For each word in 'name' replace 'string1' with 'string2'
# Below we are replacing the suffix .c of all words in the macro SRCS
# with the .o suffix
#
OBJS = $(SRCS:.cpp=.o)

# define the executable file 
MAIN = BST


#
# The following part of the makefile is generic; it can be used to 
# build any executable just by changing the definitions above and by
# deleting dependencies appended to the file from 'make depend'
#

all:$(MAIN)
	@echo  The $(MAIN) has been compiled!

$(MAIN):$(OBJS)
	$(CC_OPTIONS) -o $@ $(OBJS)

# this is a suffix replacement rule for building .o's from .c's
# it uses automatic variables 
# $<: the name of the prerequisite of the rule(a .c/cpp file) 
# and $@: the name of the target of the rule (a .o file) 
# (see the gnu make manual section about automatic variables)
#.c.o:
.cpp.o:
	$(CC) $(CFLAGS) -c $< -o $@

clean:
	$(RM) $(OBJS) $(MAIN)



# Original makefile
# ------------------------
#main:main.o binary_search_tree.o
#	g++ -ggdb -o main main.o binary_search_tree.o
#main.o:main.cpp binary_search_tree.h
#	g++ -ggdb -c main.cpp
#binary_search_tree.o:binary_search_tree.cpp
#	g++ -ggdb -c binary_search_tree.cpp
#clean:
#	rm main.o binary_search_tree.o main