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

x
?
Solved

Display 1 and 2 Binary Tree

Posted on 2006-06-02
5
Medium Priority
?
482 Views
Last Modified: 2006-11-18
#include<iostream>
#include<iomanip>

using namespace std;

template<typename DataType>
class BST {

public:

      BST(); //{myRoot = 0;}
    bool empty() const;
      void inorder(ostream& out) const;
      void graph(ostream& out) const;
      bool search(const DataType& item) const;
      void insert(const DataType& item);
      void remove(const DataType& item);
      void display(ostream& out);


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;
      BinNodePointer myRoot;
      BinNodePointer myFront;
      void inorderAux(ostream& out, BST<DataType>::BinNodePointer subtreePtr) const;
      void graphAux(ostream& out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const;
      bool searchAux(BST<DataType>::BinNodePointer subtreeRoot, const DataType& item) const;
      void insertAux(BST<DataType>::BinNodePointer& subtreeRoot, const DataType& item);
      void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
    void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
   
};

template<typename DataType>
inline BST<DataType>::BST():myRoot(0){}

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

      return myRoot == 0;

}

template<typename DataType>
inline void BST<DataType>::inorder(ostream& out) const {

      inorderAux(out, myRoot);

}

template<typename DataType>
void BST<DataType>::inorderAux(ostream& out, BST<DataType>::BinNodePointer subtreeRoot) const {

      if(subtreeRoot != 0) {
            inorderAux(out, subtreeRoot->left);
            out << subtreeRoot->data << " ";
            inorderAux(out, subtreeRoot->right);

      }

}

template<typename DataType>
inline void BST<DataType>::graph(ostream& out) const {

      graphAux(out, 0, myRoot);

}

template<typename DataType>
void BST<DataType>::graphAux(ostream& out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const {

      if(subtreeRoot != 0) {
            graphAux(out, indent + 8, subtreeRoot->right);
            out << setw(indent) << " " << subtreeRoot->data << endl;
            graphAux(out, indent + 8, subtreeRoot->left);

      }

}

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

      return searchAux(myRoot, item);

}

template<typename DataType>
bool BST<DataType>::searchAux(BST<DataType>::BinNodePointer subtreeRoot, const DataType& item) const {

      if(subtreeRoot == 0)
            return false;

      if(item < subtreeRoot->data)
            return searchAux(subtreeRoot->left, item);
      else if(subtreeRoot->data < item)
            return searchAux(subtreeRoot->right, item);
      else
            return true;

}

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

      BST<DataType>::BinNodePointer locptr = myRoot;
      bool found = false;

      while(!found && locptr != 0) {
            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 = 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;

      }
      else
            cout << " Item already in tree\n";

}

template<typename DataType>
void BST<DataType>::insertAux(BST<DataType>::BinNodePointer& subtreeRoot, const DataType& item) {

      if(subtreeRoot == 0)
            subtreeRoot = new BST<DataType>::BinNode(item);
      else if(item < subtreeRoot->data)
            insertAux(subtreeRoot->left, item);
      else if(subtreeRoot->data < item)
            insertAux(subtreeRoot->right, item);
      else
            cerr << " Item already in tree\n";

}

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
          subtreeRoot = x->left;
     if(subtreeRoot == 0)
          subtreeRoot = x->right;
     if(parent == 0)
          myRoot = subtreeRoot;
     else if(parent->left == x)
          parent->left = subtreeRoot;
     else
          parent->right = subtreeRoot;
     delete x;

}

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>::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:

 g++ bin.cpp
bin.cpp:119: error: redefinition of `bool BST<DataType>::search(const
   DataType&) const'
bin.cpp:97: error: `bool BST<DataType>::search(const DataType&) const'
   previously declared here
bin.cpp:119: error: no `bool BST<DataType>::search(const DataType&) const'
   member function declared in class `BST<DataType>'

******************

the format for this code is as follows:

                                         16          

                            14

               12
   
  9

               7


                                5

                                               3

I also need a horizontal output:

eg.

                                                     
                   9
 
          5              14


   3         7       12       16

Please advise.  Del



























0
Comment
Question by:edelossantos
  • 3
  • 2
5 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 2000 total points
ID: 16823839
The following compiles and runs fine:

#include<iostream>
#include<iomanip>

using namespace std;

template<typename DataType>
class BST {

public:

     BST(); //{myRoot = 0;}
    bool empty() const;
     void inorder(ostream& out) const;
     void graph(ostream& out) const;
     bool search(const DataType& item) const;
     void insert(const DataType& item);
     void remove(const DataType& item);
     void display(ostream& out);


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;
     BinNodePointer myRoot;
     BinNodePointer myFront;
     void inorderAux(ostream& out, BST<DataType>::BinNodePointer subtreePtr) const;
     void graphAux(ostream& out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const;
     bool searchAux(BST<DataType>::BinNodePointer subtreeRoot, const DataType& item) const;
     void insertAux(BST<DataType>::BinNodePointer& subtreeRoot, const DataType& item);
     void search2(const DataType& item, bool& found, BinNodePointer& locPtr, BinNodePointer& parent) const;
    void displayAux(ostream& out, int index, BinNodePointer& subTreeRoot);
   
};

template<typename DataType>
inline BST<DataType>::BST():myRoot(0){}

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

     return myRoot == 0;

}

template<typename DataType>
inline void BST<DataType>::inorder(ostream& out) const {

     inorderAux(out, myRoot);

}

template<typename DataType>
void BST<DataType>::inorderAux(ostream& out, BST<DataType>::BinNodePointer subtreeRoot) const {

     if(subtreeRoot != 0) {
          inorderAux(out, subtreeRoot->left);
          out << subtreeRoot->data << " ";
          inorderAux(out, subtreeRoot->right);

     }

}

template<typename DataType>
inline void BST<DataType>::graph(ostream& out) const {

     graphAux(out, 0, myRoot);

}

template<typename DataType>
void BST<DataType>::graphAux(ostream& out, int indent, BST<DataType>::BinNodePointer subtreeRoot) const {

     if(subtreeRoot != 0) {
          graphAux(out, indent + 8, subtreeRoot->right);
          out << setw(indent) << " " << subtreeRoot->data << endl;
          graphAux(out, indent + 8, subtreeRoot->left);

     }

}

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

     return searchAux(myRoot, item);

}

template<typename DataType>
bool BST<DataType>::searchAux(BST<DataType>::BinNodePointer subtreeRoot, const DataType& item) const {

     if(subtreeRoot == 0)
          return false;

     if(item < subtreeRoot->data)
          return searchAux(subtreeRoot->left, item);
     else if(subtreeRoot->data < item)
          return searchAux(subtreeRoot->right, item);
     else
          return true;

}
/* a duplicate?
template<typename DataType>
bool BST<DataType>::search(const DataType& item) const {

     BST<DataType>::BinNodePointer locptr = myRoot;
     bool found = false;

     while(!found && locptr != 0) {
          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 = 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;

     }
     else
          cout << " Item already in tree\n";

}

template<typename DataType>
void BST<DataType>::insertAux(BST<DataType>::BinNodePointer& subtreeRoot, const DataType& item) {

     if(subtreeRoot == 0)
          subtreeRoot = new BST<DataType>::BinNode(item);
     else if(item < subtreeRoot->data)
          insertAux(subtreeRoot->left, item);
     else if(subtreeRoot->data < item)
          insertAux(subtreeRoot->right, item);
     else
          cerr << " Item already in tree\n";

}

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
          subtreeRoot = x->left;
     if(subtreeRoot == 0)
          subtreeRoot = x->right;
     if(parent == 0)
          myRoot = subtreeRoot;
     else if(parent->left == x)
          parent->left = subtreeRoot;
     else
          parent->right = subtreeRoot;
     delete x;

}

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>::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");

}

Where do you need to change the output formatting?
0
 

Author Comment

by:edelossantos
ID: 16824402
>>
Where do you need to change the output formatting?

I am thinking in the code snippet below, and I would need to declare data members top, and bottom:

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;

}
0
 
LVL 86

Expert Comment

by:jkr
ID: 16824684
Thanx - I was just working on your display issue. Is

Item to insert (-999 to stop): 1
Item to insert (-999 to stop): 3
Item to insert (-999 to stop): 5
Item to insert (-999 to stop): 7
Item to insert (-999 to stop): 2
Item to insert (-999 to stop): 4
Item to insert (-999 to stop): 6
Item to insert (-999 to stop): -999
        7
    6
            5
        4
                3
            2
                    1

close to what you had in mind?
0
 

Author Comment

by:edelossantos
ID: 16824690
Yes.
0
 

Author Comment

by:edelossantos
ID: 16824887
jkr,

Go to the ta, I have placed my attempt under Display.  Please advise.  Del
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

830 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