Binary Search Tree

Need code checked.  Please advise.  Del

#include<iostream>

using namespace std;

template<typename DataType>
class BST {

private:

      class BinNode {

      public:

            DataType data;
            BinNode *left;
            BinNode *right;

            BinNode(): left(0), right(0){}
            BinNode(DataType item):data(item), left(0), right(0){}
            typedef BinNode* BinNodePointer;

      public:

            BST();
            bool empty() const;
            bool search(const DataType& item) const;
            void insert(const DataType& item);
            void remove(const DataType& item);
            void display(ostream& out);

      private:

            void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
            void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
            BinNodePointer myFront;

};


template<typename DataType>
bool BST<DataType>::empty() const {

      return myRoot == 0;

}

template<typename DataType>
bool BST<DataType>::search(const DataType& item) const {

      BST<DataType>::BinNodePointer
            locPtr = myFront;
      bool found = false;

      for(; ;) {
            if(found || locPtr == 0) break;
            if(item < locPtr->data)
                  locPtr = locPtr->left;
            else if(locPtr->data < item)
                  locPtr = locPtr->right;
            else found = true;

      }
      return found;

}

void BST<DataType>::insert(const DataType& item) {

      BST<DataType>::BinNodePointer
            locPtr = myRoot, parent = 0;

      bool found = false;

      while(!found && locPtr != 0) {
            parent = locPtr;

            if(item < locPtr->data)
                  locPtr = locPtr->left;
            else if(locPtr->data < item)
                  locPtr = locPtr->right;
            else found = true;

      }
      if(!found) {
            locPtr = new BST<DataType>::BinNode(item);

            if(parent == 0)
                  myRoot = locPtr;
            else if(item < parent->data)
                  parent->left = locPtr;
            else
                  parent->right = locPtr;

      }
      cout << "Item already in the tree. " << endl;

}

template<typename DataType>
void BST<DataType>::displayAux(ostream& out) {

      int indent, BST<DataType>::BinNodePointer subTreeRoot) {

            if(subTreeRoot != 0) {
                  displayAux(out, indent + B, subTreeRoot->right);

                  out << setw(indent) << " " << subTreeRoot->data << endl;

                  displayAux(out, indent + B, subTreeRoot->left);

            }

      }
      return;

}

template<typename DataType>
void BST<DataType>::remove(const DataType& item) {

      bool found;
      BST<DataType>::BinNodePointer x, parent;

      search2(item, found, x, parent);
      if(!found) {
            cout << " Item not in the BST\n";
            return;

      }
      if(x->left != 0 && x->right !=0) {
            BST<DataType>::BinNodePointer xSucc = x->right;
            parent = x;

            while(xSucc->left != 0) {
                  parent = xSucc;
                  xSucc = xSucc->left;

            }
            x->data = xSucc->data;
            x = xSucc;

      }
      BST<DataType>::BinNodePointer
            subTree = x->left;
      if(subtree == 0)
            subtree = x->right;
      if(parent == 0)
            myRoot = subtree;
      else if(parent->left == x)
            parent->left = subtree;
      else
            parent->right = subtree;
      delete x;

}

template<typename DataType>
void BST<DataType>::search2(const DataType& item, bool& found, BST<DataType>::BinNodePointer& locPtr,
                                          BST<DataType>::BinNodePointer& parent) const {

      locPtr = myRoot;
      parent = 0;
      found = false;

      while(!found && locPtr != 0) {
            if(item < locPtr->data) {
                  parent = locPtr;
                  locPtr = locPtr->left;

            }
            else if(locPtr->data < item) {
                  parent = locPtr;
                  locPtr = locPtr->right;

            }
            else
                  found = true;

      }
      return;

}

int main(void) {

            BST<int> intBST;
            cout << " Constructing empty BST\n";
            cout << " BST " << (intBst.empty() ? "is" : "is not") << " empty\n";

            cout << " Inorder Traversal of BST: \n";
            intBST.inorder(cout);

            cout << "\nNow insert a bunch of integers into the BST. "
                  "\nTry items not in the BST and some that are in it:\n";

            int number;
            for(;;) {
                  cout << "Item to insert (-999 to stop): ";
                  cin >> number;
                  if(number == -999) break;
                  intBst.insert(number);

            }
            intBST.graph(cout);

            cout << "BST " << (intBST.empty() ? "is" : "is not") << empty;
                  cout << "Inorder Traversal of BST: \n";
            intBST.inorder(cout);

            cout << endl;

            cout << "\n\nNow testing the search() operation."
                  "\nTry both items in the BST and some not in it:\n";

            for(;;) {
                  cout << "Item to find(-999 to stop):" ;
                  cin >> number;
                  if(number == -999) break;
                  cout << (intBST.search(number) ? "Found" : "Not found") << endl;

            }
            cout << "\nNow testing the remove() operation. "
                  "\nTry both items in the BST and some not in it:\n";

            for(;;) {
                  cout << "Item to remove (-999 to stop): ";
                  cin >> number;
                  if(number == -999) break;
                  intBST.remove(number);
                  intBST.graph(cout);

            }
            cout << "\nInorder Traversal of BST: \n";
            intBST.inorder(cout);
            cout << endl;

            return 0;
            system("pause");


}

output:

------ Build started: Project: Lab 7, Configuration: Debug Win32 ------
Compiling...
bin.cpp
c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(247) : fatal error C1075: end of file found before the left brace '{' at 'c:\documents and settings\enrique\my documents\cs223_spring06 ~awanni\lab 7\bin.cpp(7)' was matched
Build log was saved at "file://c:\Documents and Settings\Enrique\My Documents\Visual Studio 2005\Projects\Lab 7\Lab 7\Debug\BuildLog.htm"
Lab 7 - 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
edelossantosAsked:
Who is Participating?
 
jkrCommented:
Ouch, there's a lot going wrong - here's the corrected version, check the comments:

#include<iostream>

using namespace std;

template<typename DataType>
class BST {

private:

     class BinNode {

     public:

          DataType data;
          BinNode *left;
          BinNode *right;

          BinNode(): left(0), right(0){}
          BinNode(DataType item):data(item), left(0), right(0){}
     }; // <--- missing!
          typedef BinNode* BinNodePointer;

     public:

          BST() {}; // need to provide an impementation!
          bool empty() const;
          bool search(const DataType& item) const;
          void insert(const DataType& item);
          void remove(const DataType& item);
          void display(ostream& out);

     private:

          void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
          void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
          BinNodePointer myFront;
          BinNodePointer myRoot; // missing!

};



template<typename DataType>
bool BST<DataType>::empty() const {

     return myRoot == 0;

}

template<typename DataType>
bool BST<DataType>::search(const DataType& item) const {

     BST<DataType>::BinNodePointer
          locPtr = myFront;
     bool found = false;

     for(; ;) {
          if(found || locPtr == 0) break;
          if(item < locPtr->data)
               locPtr = locPtr->left;
          else if(locPtr->data < item)
               locPtr = locPtr->right;
          else found = true;

     }
     return found;

}

template<typename DataType>
void BST<DataType>::insert(const DataType& item) {

     BST<DataType>::BinNodePointer locPtr, parent;
          locPtr = myRoot;

     bool found = false;

     while(!found && locPtr != 0) {
          parent = locPtr;

          if(item < locPtr->data)
               locPtr = locPtr->left;
          else if(locPtr->data < item)
               locPtr = locPtr->right;
          else found = true;

     }
     if(!found) {
          locPtr = new BST<DataType>::BinNode(item);

          if(parent == 0)
               myRoot = locPtr;
          else if(item < parent->data)
               parent->left = locPtr;
          else
               parent->right = locPtr;

     }
     cout << "Item already in the tree. " << endl;

}

template<typename DataType>
void BST<DataType>::displayAux(ostream& out, int index, BinNodePointer& subTreeRoot) { // was screwed


          if(subTreeRoot != 0) {
               displayAux(out, indent + B, subTreeRoot->right);

               out << setw(indent) << " " << subTreeRoot->data << endl;

               displayAux(out, indent + B, subTreeRoot->left);

          }

     return;

}

template<typename DataType>
void BST<DataType>::remove(const DataType& item) {

     bool found;
     BST<DataType>::BinNodePointer x, parent;

     search2(item, found, x, parent);
     if(!found) {
          cout << " Item not in the BST\n";
          return;

     }
     if(x->left != 0 && x->right !=0) {
          BST<DataType>::BinNodePointer xSucc = x->right;
          parent = x;

          while(xSucc->left != 0) {
               parent = xSucc;
               xSucc = xSucc->left;

          }
          x->data = xSucc->data;
          x = xSucc;

     }
     BST<DataType>::BinNodePointer
          subTree = x->left;
     if(subtree == 0)
          subtree = x->right;
     if(parent == 0)
          myRoot = subtree;
     else if(parent->left == x)
          parent->left = subtree;
     else
          parent->right = subtree;
     delete x;

}

template<typename DataType>
void BST<DataType>::search2(const DataType& item, bool& found, BST<DataType>::BinNodePointer& locPtr,
                                   BST<DataType>::BinNodePointer& parent) const {

     locPtr = myRoot;
     parent = 0;
     found = false;

     while(!found && locPtr != 0) {
          if(item < locPtr->data) {
               parent = locPtr;
               locPtr = locPtr->left;

          }
          else if(locPtr->data < item) {
               parent = locPtr;
               locPtr = locPtr->right;

          }
          else
               found = true;

     }
     return;

}

int main(void) {

          BST<int> intBST;
          cout << " Constructing empty BST\n";
          cout << " BST " << (intBST.empty() ? "is" : "is not") << " empty\n"; // typo

          cout << " Inorder Traversal of BST: \n";
          //intBST.inorder(cout); 'inorder' is NOT a member!

          cout << "\nNow insert a bunch of integers into the BST. "
               "\nTry items not in the BST and some that are in it:\n";

          int number;
          for(;;) {
               cout << "Item to insert (-999 to stop): ";
               cin >> number;
               if(number == -999) break;
               intBST.insert(number); // typo

          }
          //intBST.graph(cout); NOT A MEMBER!

          cout << "BST " << (intBST.empty() ? "is" : "is not") << "empty"; // quotes missing
               cout << "Inorder Traversal of BST: \n";
          //intBST.inorder(cout); 'inorder' is NOT a member!

          cout << endl;

          cout << "\n\nNow testing the search() operation."
               "\nTry both items in the BST and some not in it:\n";

          for(;;) {
               cout << "Item to find(-999 to stop):" ;
               cin >> number;
               if(number == -999) break;
               cout << (intBST.search(number) ? "Found" : "Not found") << endl;

          }
          cout << "\nNow testing the remove() operation. "
               "\nTry both items in the BST and some not in it:\n";

          for(;;) {
               cout << "Item to remove (-999 to stop): ";
               cin >> number;
               if(number == -999) break;
               //intBST.remove(number); NOT A MEMBER!
               //intBST.graph(cout); NOT A MEMBER!

          }
          cout << "\nInorder Traversal of BST: \n";
          //intBST.inorder(cout); 'inorder' is NOT a member!
          cout << endl;

          return 0;
          system("pause");


}
0
 
edelossantosAuthor Commented:
I am back online.  Thank you.  Del
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.