Link to home
Start Free TrialLog in
Avatar of edelossantos
edelossantos

asked on

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 ==========
ASKER CERTIFIED SOLUTION
Avatar of jkr
jkr
Flag of Germany image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of edelossantos
edelossantos

ASKER

I am back online.  Thank you.  Del