[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Binary Search Tree

Posted on 2006-06-01
2
Medium Priority
?
494 Views
Last Modified: 2010-04-01
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 ==========
0
Comment
Question by:edelossantos
2 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 2000 total points
ID: 16811439
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
 

Author Comment

by:edelossantos
ID: 16812462
I am back online.  Thank you.  Del
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

829 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question