Main Page   Packages   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Search  

BinSearchTree Class Reference

#include <BST.hpp>

List of all members.

Public Methods

 BinSearchTree ()
virtual ~BinSearchTree ()
void clear ()
void insert (DBase *val)
void remove ()
void remove (DBase &val)
int find (DBase &val)
int findID (String &ID)
bool isEmpty () const
int length () const
int search () const
void print () const
void display () const
void clear (BinNode *)
void insert (BinNode *&, DBase *)
BinNode * deletemin (BinNode *&)
void remove (BinNode *&, DBase &)
int find (BinNode *, DBase &)
int findID (BinNode *, String &)
void print (BinNode *, int) const
BinNode * getCurrent ()
DBase * getValue ()
void preorder (BinNode *rt) const

Private Attributes

BinNode * current
DBase * currElem
BinNode * root
int NbElements
int searchStep

Constructor & Destructor Documentation

BinSearchTree::BinSearchTree (    ) 
 

Definition at line 20 of file bst.cpp.

00020                              { 
00021   NbElements = 0;
00022   searchStep = 0;
00023   root       = NULL; 
00024   current    = NULL;
00025   currElem   = NULL;
00026 }

BinSearchTree::~BinSearchTree (    )  [virtual]
 

Definition at line 28 of file bst.cpp.

00028                               { 
00029   clear( root );
00030 }

Member Function Documentation

void BinSearchTree::clear (  BinNode *    rt ) 
 

Definition at line 91 of file bst.cpp.

00091                                        {
00092   if ( rt == NULL ) return;
00093   clear( rt->left  );
00094   clear( rt->right );
00095   NbElements--;
00096   current  = NULL;
00097   currElem = NULL;
00098   delete rt;
00099 }

void BinSearchTree::clear (    ) 
 

Definition at line 32 of file bst.cpp.

Referenced by clear(), and ~BinSearchTree(). 

00032                           { 
00033   clear( root ); 
00034     root = NULL;
00035   NbElements = 0;
00036   searchStep = 0;
00037 }

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

Definition at line 141 of file bst.cpp.

Referenced by remove(). 

00141                                                 {
00142 
00143   if ( rt == NULL ) {                  // There must be a node to delete
00144     cout << "Cannot delete a node inside an empty Binary Search Tree ! ";
00145     return NULL;
00146   }
00147 
00148   if ( rt->left != NULL ) {            // Continue left
00149     return deletemin( rt->left );
00150 
00151   } else {                             // Found it
00152     BinNode* temp = rt; 
00153   rt = rt->right; 
00154   NbElements--;
00155   current = NULL;
00156   return temp; 
00157   }
00158 }

void BinSearchTree::display (    )  const
 

Definition at line 4 of file bst.cpp.

00004                                   {           // With preorder
00005   cout << "DISPLAY:"<<endl;
00006   preorder( root );
00007   cout << "End of DISPLAY:"<<endl;
00008 }

int BinSearchTree::find (  BinNode *    node,
DBase &    val
) 
 

Definition at line 196 of file bst.cpp.

00196                                                    {
00197   searchStep++;
00198   if ( node == NULL ) {                      // Empty Tree
00199     cout << "Can't search an element from a NOWHERE location" << endl;
00200     return -50;
00201 
00202   } else if ( NbElements < 1 ) {
00203 //    cout << "Can't search inside an empty binary search tree" << endl;
00204     return -50;
00205   
00206   } else if ( node->CompareID( val ) < 0  ) {    // Check left
00207     return find( node->left, val );
00208 
00209   } else if ( node->CompareID( val ) == 0 ) {
00210     current  = node;
00211     currElem = node->getElem();
00212   // node->value();
00213     return 100;                            // Found Flag
00214   
00215   } else {
00216     return find( node->right, val );          // Check right
00217   }
00218 }

int BinSearchTree::find (  DBase &    val ) 
 

Definition at line 52 of file bst.cpp.

Referenced by find(). 

00052                                     {
00053   searchStep = 0;
00054     return find( root, val ); 
00055 }

int BinSearchTree::findID (  BinNode *    node,
String &    ID
) 
 

Definition at line 220 of file bst.cpp.

00220                                                      {
00221  searchStep++;
00222 
00223  if ( node == NULL ) {
00224 //    cout << "The element wasn't found in the tree. " << ID << endl;
00225     return -50;
00226  } else  {
00227 
00228 //  if ( node->valid() ) {  cout << node << endl; }
00229 
00230   if ( NbElements < 1 ) {
00231     cout << "Can't search inside an empty binary search tree" << endl;
00232     return -50;
00233   
00234   } else if ( node->CompareID( ID ) < 0  ) {    // Check left
00235     return findID( node->left, ID );
00236 
00237   } else if ( node->CompareID( ID ) == 0 ) {
00238     current  = node;
00239     currElem = node->getElem();
00240   // node->value();
00241     return 100;                            // Found Flag
00242   
00243   } else {
00244     return findID( node->right, ID );         // Check right
00245   }
00246 
00247  }
00248 }

int BinSearchTree::findID (  String &    ID ) 
 

Definition at line 57 of file bst.cpp.

Referenced by DataBase::findID(), and findID(). 

00057                                       {
00058   searchStep = 0;
00059     return findID( root, ID ); 
00060 }

BinNode * BinSearchTree::getCurrent (    ) 
 

Definition at line 74 of file bst.cpp.

00074                                     {
00075   return current;
00076 }

DBase * BinSearchTree::getValue (    ) 
 

Definition at line 78 of file bst.cpp.

Referenced by DataBase::findID(). 

00078                                   {
00079   return currElem;
00080 }

void BinSearchTree::insert (  BinNode *&    rt,
DBase *    val
) 
 

Definition at line 160 of file bst.cpp.

00160                                                      {
00161   
00162   if ( rt == NULL ) {                  // Empty tree: create node
00163   NbElements++;
00164   current = rt;
00165     rt = new BinNode( val, NULL, NULL );
00166 
00167   } else if ( *val < rt->value() ) {
00168     insert( rt->left, val );                // Check left
00169 
00170   } else {
00171   insert( rt->right, val );               // Check right
00172   }
00173 }

void BinSearchTree::insert (  DBase *    val ) 
 

Definition at line 39 of file bst.cpp.

Referenced by insert(), and DataBase::read(). 

00039                                        { 
00040   insert( root, val ); 
00041 }

bool BinSearchTree::isEmpty (    )  const
 

Definition at line 62 of file bst.cpp.

00062                                   { 
00063   return ( root == NULL ); 
00064 }

int BinSearchTree::length (    )  const
 

Definition at line 82 of file bst.cpp.

00082                                   {
00083   return NbElements;
00084 }

void BinSearchTree::preorder (  BinNode *    rt )  const
 

Definition at line 10 of file bst.cpp.

Referenced by display(). 

00010                                                 {  // rt is the root of a subtree
00011 
00012   if ( rt == NULL ) return;                   // Empty subtree
00013   
00014   cout << rt->value() << " ";                 // Visit performs whatever action is desired
00015 
00016   preorder( rt->left  );
00017   preorder( rt->right );
00018 }

void BinSearchTree::print (  BinNode *    rt,
int    level
)  const
 

Definition at line 176 of file bst.cpp.

00176                                                         {
00177 
00178   if ( rt == NULL ) return;                 // Empty tree
00179 
00180   print( rt->left, level+1 );               // Print left subtree
00181   
00182   if ( level == 0 ) {
00183     cout << "  Root  ";
00184   } else {
00185     if ( level < 10 )  { cout << " ";  }
00186     if ( level < 100 ) { cout << " ";  }
00187 
00188     cout << level << "     " ;
00189   }
00190 
00191   cout << rt->value() << "\n";                  // Print node value
00192 
00193   print( rt->right, level+1 );                  // Print right subtree
00194 }

void BinSearchTree::print (    )  const
 

Definition at line 66 of file bst.cpp.

Referenced by print(). 

00066                                 {
00067     if ( root == NULL ) {
00068     cout << "The BinSearchTree is empty.\n";
00069   } else {
00070     print( root, 0 );
00071   }
00072 }

void BinSearchTree::remove (  BinNode *&    rt,
DBase &    val
) 
 

Definition at line 101 of file bst.cpp.

00101                                                      {
00102   if ( rt == NULL ) {
00103     cout << val << " is not in the tree.\n";
00104 
00105   } else {
00106 
00107   if ( val < rt->value() ) {              // Check left
00108        remove( rt->left,  val );
00109 
00110   } else if ( val > rt->value() ) {       // Check right
00111        remove( rt->right, val );
00112 
00113   } else {                                // Found it: remove it
00114 
00115        BinNode* temp = rt;
00116 
00117        if ( rt->left == NULL ) {            // Only a right child
00118          rt = rt->right;                    //   so point to right
00119 
00120        } else if ( rt->right == NULL ) {    // Only a left child
00121          rt = rt->left;                     //   so point to left
00122     
00123      } else {                             // Both children are non-empty
00124          temp = deletemin( rt->right );     // Replace with min value
00125 
00126          rt->setValue( temp->value() );     //  in right subtree  
00127        }
00128 
00129      NbElements--;
00130 
00131      if ( temp == current ) {
00132       current  = NULL;
00133       currElem = NULL;
00134      }
00135 
00136        delete temp;                         // Return node to free store
00137   }
00138   }
00139 }

void BinSearchTree::remove (  DBase &    val ) 
 

Definition at line 48 of file bst.cpp.

00048                                        { 
00049   remove( root, val ); 
00050 }

void BinSearchTree::remove (    ) 
 

Definition at line 43 of file bst.cpp.

Referenced by DataBase::read(), and remove(). 

00043                            {
00044 //  cout << "This will be remove:" << current << endl;
00045   remove( root, current->value() );
00046 }

int BinSearchTree::search (    )  const
 

Definition at line 86 of file bst.cpp.

Referenced by DataBase::findID(). 

00086                                   {
00087   return searchStep;
00088 }

Member Data Documentation

int BinSearchTree::NbElements [private]
 

Definition at line 52 of file BST.hpp.

DBase* BinSearchTree::currElem [private]
 

Definition at line 49 of file BST.hpp.

BinNode* BinSearchTree::current [private]
 

Definition at line 48 of file BST.hpp.

BinNode* BinSearchTree::root [private]
 

Definition at line 51 of file BST.hpp.

int BinSearchTree::searchStep [private]
 

Definition at line 53 of file BST.hpp.

The documentation for this class was generated from the following files:
Generated on Sun Oct 14 18:48:26 2001 for Standard J2K Library by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001