1 #ifndef BINARY_SEARCH_TREE_H  2 #define BINARY_SEARCH_TREE_H  3   4 #include "dsexceptions.h"  5 #include <iostream>    // For NULL  6 using namespace std;         7   8 // BinarySearchTree class  9 // 10 // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds 11 // 12 // ******************PUBLIC OPERATIONS********************* 13 // void insert( x )       --> Insert x 14 // void remove( x )       --> Remove x 15 // bool contains( x )     --> Return true if x is present 16 // Comparable findMin( )  --> Return smallest item 17 // Comparable findMax( )  --> Return largest item 18 // boolean isEmpty( )     --> Return true if empty; else false 19 // void makeEmpty( )      --> Remove all items 20 // void printTree( )      --> Print tree in sorted order 21 // ******************ERRORS******************************** 22 // Throws UnderflowException as warranted 23  24 template <typename Comparable> 25 class BinarySearchTree 26 { 27   public: 28     BinarySearchTree( ) :root( NULL ) 29     { 30     } 31  32     BinarySearchTree( const BinarySearchTree & rhs ) : root( NULL ) 33     { 34         *this = rhs; 35     } 36  37     /** 38      * Destructor for the tree 39      */ 40     ~BinarySearchTree( ) 41     { 42         makeEmpty( ); 43     } 44  45     /** 46      * Find the smallest item in the tree. 47      * Throw UnderflowException if empty. 48      */ 49     const Comparable & findMin( ) const 50     { 51         if( isEmpty( ) ) 52             throw UnderflowException( ); 53         return findMin( root )->element; 54     } 55  56     /** 57      * Find the largest item in the tree. 58      * Throw UnderflowException if empty. 59      */ 60     const Comparable & findMax( ) const 61     { 62         if( isEmpty( ) ) 63             throw UnderflowException( ); 64         return findMax( root )->element; 65     } 66  67     /** 68      * Returns true if x is found in the tree. 69      */ 70     bool contains( const Comparable & x ) const 71     { 72         return contains( x, root ); 73     } 74  75     /** 76      * Test if the tree is logically empty. 77      * Return true if empty, false otherwise. 78      */ 79     bool isEmpty( ) const 80     { 81         return root == NULL; 82     } 83  84     /** 85      * Print the tree contents in sorted order. 86      */ 87     void printTree( ostream & out = cout ) const 88     { 89         if( isEmpty( ) ) 90             out << "Empty tree" << endl; 91         else 92             printTree( root, out ); 93     } 94  95     /** 96      * Make the tree logically empty. 97      */ 98     void makeEmpty( ) 99     {100         makeEmpty( root );101     }102 103     /**104      * Insert x into the tree; duplicates are ignored.105      */106     void insert( const Comparable & x )107     {108         insert( x, root );109     }110      111     /**112      * Remove x from the tree. Nothing is done if x is not found.113      */114     void remove( const Comparable & x )115     {116         remove( x, root );117     }118 119     /**120      * Deep copy.121      */122     const BinarySearchTree & operator=( const BinarySearchTree & rhs )123     {124         if( this != &rhs )125         {126             makeEmpty( );127             root = clone( rhs.root );128         }129         return *this;130     }131 132   private:133     struct BinaryNode134     {135         Comparable element;136         BinaryNode *left;137         BinaryNode *right;138 139         BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )140             : element( theElement ), left( lt ), right( rt ) { }141     };142 143     BinaryNode *root;144 145 146     /**147      * Internal method to insert into a subtree.148      * x is the item to insert.149      * t is the node that roots the subtree.150      * Set the new root of the subtree.151      */152     void insert( const Comparable & x, BinaryNode * & t )153     {154         if( t == NULL )155             t = new BinaryNode( x, NULL, NULL );156         else if( x < t->element )157             insert( x, t->left );158         else if( t->element < x )159             insert( x, t->right );160         else161             ;  // Duplicate; do nothing162     }163 164     /**165      * Internal method to remove from a subtree.166      * x is the item to remove.167      * t is the node that roots the subtree.168      * Set the new root of the subtree.169      */170     void remove( const Comparable & x, BinaryNode * & t )171     {172         if( t == NULL )173             return;   // Item not found; do nothing174         if( x < t->element )175             remove( x, t->left );176         else if( t->element < x )177             remove( x, t->right );178         else if( t->left != NULL && t->right != NULL ) // Two children179         {180             t->element = findMin( t->right )->element;181             remove( t->element, t->right );182         }183         else184         {185             BinaryNode *oldNode = t;186             t = ( t->left != NULL ) ? t->left : t->right;187             delete oldNode;188         }189     }190 191     /**192      * Internal method to find the smallest item in a subtree t.193      * Return node containing the smallest item.194      */195     BinaryNode * findMin( BinaryNode *t ) const196     {197         if( t == NULL )198             return NULL;199         if( t->left == NULL )200             return t;201         return findMin( t->left );202     }203 204     /**205      * Internal method to find the largest item in a subtree t.206      * Return node containing the largest item.207      */208     BinaryNode * findMax( BinaryNode *t ) const209     {210         if( t != NULL )211             while( t->right != NULL )212                 t = t->right;213         return t;214     }215 216 217     /**218      * Internal method to test if an item is in a subtree.219      * x is item to search for.220      * t is the node that roots the subtree.221      */222     bool contains( const Comparable & x, BinaryNode *t ) const223     {224         if( t == NULL )225             return false;226         else if( x < t->element )227             return contains( x, t->left );228         else if( t->element < x )229             return contains( x, t->right );230         else231             return true;    // Match232     }233 /****** NONRECURSIVE VERSION*************************234     bool contains( const Comparable & x, BinaryNode *t ) const235     {236         while( t != NULL )237             if( x < t->element )238                 t = t->left;239             else if( t->element < x )240                 t = t->right;241             else242                 return true;    // Match243 244         return false;   // No match245     }246 *****************************************************/247 248     /**249      * Internal method to make subtree empty.250      */251     void makeEmpty( BinaryNode * & t )252     {253         if( t != NULL )254         {255             makeEmpty( t->left );256             makeEmpty( t->right );257             delete t;258         }259         t = NULL;260     }261 262     /**263      * Internal method to print a subtree rooted at t in sorted order.264      */265     void printTree( BinaryNode *t, ostream & out ) const266     {267         if( t != NULL )268         {269             printTree( t->left, out );270             out << t->element << endl;271             printTree( t->right, out );272         }273     }274 275     /**276      * Internal method to clone subtree.277      */278     BinaryNode * clone( BinaryNode *t ) const279     {280         if( t == NULL )281             return NULL;282         else283             return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );284     }285 };286 287 #endif

 1 #include <iostream> 2 #include "BinarySearchTree.h" 3 using namespace std; 4  5     // Test program 6 int main( ) 7 { 8     BinarySearchTree<int> t; 9     int NUMS = 400000;10     const int GAP  =   3711;11     int i;12 13     cout << "Checking... (no more output means success)" << endl;14 15     for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )16         t.insert( i );17 18     for( i = 1; i < NUMS; i+= 2 )19         t.remove( i );20 21     if( NUMS < 40 )22         t.printTree( );23     if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )24         cout << "FindMin or FindMax error!" << endl;25 26     for( i = 2; i < NUMS; i+=2 )27         if( !t.contains( i ) )28             cout << "Find error1!" << endl;29 30     for( i = 1; i < NUMS; i+=2 )31     {32         if( t.contains( i ) )33             cout << "Find error2!" << endl;34     }35 36     BinarySearchTree<int> t2;37     t2 = t;38 39     for( i = 2; i < NUMS; i+=2 )40         if( !t2.contains( i ) )41             cout << "Find error1!" << endl;42 43     for( i = 1; i < NUMS; i+=2 )44     {45         if( t2.contains( i ) )46             cout << "Find error2!" << endl;47     }48 49     cout << "Finished testing" << endl;50 51     return 0;52 }