Search  

---

C:/temp/src/j2k/DataType/BST/bst.cpp

Go to the documentation of this file.

// BST.cpp - Binary Search Tree Class Implementation
#include "BST.hpp"

void BinSearchTree::display() const {           // With preorder
  cout << "DISPLAY:"<<endl;
  preorder( root );
  cout << "End of DISPLAY:"<<endl;
}

void BinSearchTree::preorder( BinNode* rt ) const {  // rt is the root of a subtree

  if ( rt == NULL ) return;                   // Empty subtree
  
  cout << rt->value() << " ";                 // Visit performs whatever action is desired

  preorder( rt->left  );
  preorder( rt->right );
}

BinSearchTree::BinSearchTree() { 
  NbElements = 0;
  searchStep = 0;
  root       = NULL; 
  current    = NULL;
  currElem   = NULL;
}

BinSearchTree::~BinSearchTree() { 
  clear( root );
}

void BinSearchTree::clear() { 
  clear( root ); 
    root = NULL;
  NbElements = 0;
  searchStep = 0;
}

void BinSearchTree::insert( DBase* val ) { 
  insert( root, val ); 
}

void BinSearchTree::remove() {
//  cout << "This will be remove:" << current << endl;
  remove( root, current->value() );
}

void BinSearchTree::remove( DBase& val ) { 
  remove( root, val ); 
}

int BinSearchTree::find( DBase& val ) {
  searchStep = 0;
    return find( root, val ); 
}

int BinSearchTree::findID( String& ID ) {
  searchStep = 0;
    return findID( root, ID ); 
}

bool BinSearchTree::isEmpty() const { 
  return ( root == NULL ); 
}

void BinSearchTree::print() const {
    if ( root == NULL ) {
    cout << "The BinSearchTree is empty.\n";
  } else {
    print( root, 0 );
  }
}

BinNode*  BinSearchTree::getCurrent() {
  return current;
}

DBase*    BinSearchTree::getValue() {
  return currElem;
}

int BinSearchTree::length()   const {
  return NbElements;
}

int BinSearchTree::search()   const {
  return searchStep;
}

// Clear all nodes from the BST
void BinSearchTree::clear( BinNode* rt ) {
  if ( rt == NULL ) return;
  clear( rt->left  );
  clear( rt->right );
  NbElements--;
  current  = NULL;
  currElem = NULL;
  delete rt;
}

void BinSearchTree::remove( BinNode*& rt, DBase& val ) {
  if ( rt == NULL ) {
    cout << val << " is not in the tree.\n";

  } else {

  if ( val < rt->value() ) {              // Check left
       remove( rt->left,  val );

  } else if ( val > rt->value() ) {       // Check right
       remove( rt->right, val );

  } else {                                // Found it: remove it

       BinNode* temp = rt;

       if ( rt->left == NULL ) {            // Only a right child
         rt = rt->right;                    //   so point to right

       } else if ( rt->right == NULL ) {    // Only a left child
         rt = rt->left;                     //   so point to left
    
     } else {                             // Both children are non-empty
         temp = deletemin( rt->right );     // Replace with min value

         rt->setValue( temp->value() );     //  in right subtree  
       }

     NbElements--;

     if ( temp == current ) {
      current  = NULL;
      currElem = NULL;
     }

       delete temp;                         // Return node to free store
  }
  }
}

BinNode* BinSearchTree::deletemin( BinNode*& rt ) {

  if ( rt == NULL ) {                  // There must be a node to delete
    cout << "Cannot delete a node inside an empty Binary Search Tree ! ";
    return NULL;
  }

  if ( rt->left != NULL ) {            // Continue left
    return deletemin( rt->left );

  } else {                             // Found it
    BinNode* temp = rt; 
  rt = rt->right; 
  NbElements--;
  current = NULL;
  return temp; 
  }
}

void BinSearchTree::insert( BinNode*& rt, DBase* val ) {
  
  if ( rt == NULL ) {                  // Empty tree: create node
  NbElements++;
  current = rt;
    rt = new BinNode( val, NULL, NULL );

  } else if ( *val < rt->value() ) {
    insert( rt->left, val );                // Check left

  } else {
  insert( rt->right, val );               // Check right
  }
}

// Print the nodes of a BST; use indentation to indicate tree shape
void BinSearchTree::print( BinNode *rt, int level ) const {

  if ( rt == NULL ) return;                 // Empty tree

  print( rt->left, level+1 );               // Print left subtree
  
  if ( level == 0 ) {
    cout << "  Root  ";
  } else {
    if ( level < 10 )  { cout << " ";  }
    if ( level < 100 ) { cout << " ";  }

    cout << level << "     " ;
  }

  cout << rt->value() << "\n";                  // Print node value

  print( rt->right, level+1 );                  // Print right subtree
}

int BinSearchTree::find( BinNode* node, DBase& val ) {
  searchStep++;
  if ( node == NULL ) {                      // Empty Tree
    cout << "Can't search an element from a NOWHERE location" << endl;
    return -50;

  } else if ( NbElements < 1 ) {
//    cout << "Can't search inside an empty binary search tree" << endl;
    return -50;
  
  } else if ( node->CompareID( val ) < 0  ) {    // Check left
    return find( node->left, val );

  } else if ( node->CompareID( val ) == 0 ) {
    current  = node;
    currElem = node->getElem();
  // node->value();
    return 100;                            // Found Flag
  
  } else {
    return find( node->right, val );          // Check right
  }
}
  
int BinSearchTree::findID( BinNode* node, String& ID ) {
 searchStep++;

 if ( node == NULL ) {
//    cout << "The element wasn't found in the tree. " << ID << endl;
    return -50;
 } else  {

//  if ( node->valid() ) {  cout << node << endl; }

  if ( NbElements < 1 ) {
    cout << "Can't search inside an empty binary search tree" << endl;
    return -50;
  
  } else if ( node->CompareID( ID ) < 0  ) {    // Check left
    return findID( node->left, ID );

  } else if ( node->CompareID( ID ) == 0 ) {
    current  = node;
    currElem = node->getElem();
  // node->value();
    return 100;                            // Found Flag
  
  } else {
    return findID( node->right, ID );         // Check right
  }

 }
}

---