Like Tree1Likes
  • 1 Post By hk_mp5kpdw

I can not get the counters to work right in this program.

This is a discussion on I can not get the counters to work right in this program. within the C++ Programming forums, part of the General Programming Boards category; Okay I fixed my other issue. It took some time to think it out. I have a new issue. When ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Hutto, TX
    Posts
    12

    I can not get the counters to work right in this program.

    Okay I fixed my other issue. It took some time to think it out. I have a new issue. When I run my treeHeight() function or my treeLeavesCount() function.

    I keep only getting the value "2293600". Not sure what's causing this.


    Code:
     
    
    /*-- BST.h --*/
    
    #include <iostream>
    
    #ifndef BINARY_SEARCH_TREE
    #define BINARY_SEARCH_TREE
    
    template <typename DataType>
    class BST
    {
     public:
      /***** Function Members *****/
      BST();
      /*------------------------------------------------------------------------
        Construct a BST object.
    
        Precondition:  None.
        Postcondition: An empty BST has been constructed.
       -----------------------------------------------------------------------*/
    
      bool empty() const;
      /*------------------------------------------------------------------------
        Check if BST is empty.
    
        Precondition:  None.
        Postcondition: Returns true if BST is empty and false otherwise.
       -----------------------------------------------------------------------*/
    
      bool search(const DataType & item) const; 
      /*------------------------------------------------------------------------
        Search the BST for item.
    
        Precondition:  None.
        Postcondition: Returns true if item found, and false otherwise.
       -----------------------------------------------------------------------*/
       
      void insert(const DataType & item);
      /*------------------------------------------------------------------------
        Insert item into BST.
    
        Precondition:  None.
        Postcondition: BST has been modified with item inserted at proper 
            position to maintain BST property. 
      ------------------------------------------------------------------------*/
      
      void remove(const DataType & item);
      /*------------------------------------------------------------------------
        Remove item from BST.
    
        Precondition:  None.
        Postcondition: BST has been modified with item removed (if present);
            BST property is maintained.
        Note: remove uses auxiliary function search2() to locate the node
              containing item and its parent.
     ------------------------------------------------------------------------*/
     
      void inorder(ostream & out) const;
      /*------------------------------------------------------------------------
        Inorder traversal of BST.
    
        Precondition:  ostream out is open.
        Postcondition: BST has been inorder traversed and values in nodes 
            have been output to out.
        Note: inorder uses private auxiliary function inorderAux().
     ------------------------------------------------------------------------*/
     
      void graph(ostream & out) const;
      /*------------------------------------------------------------------------
        Graphic output of BST.
    
        Precondition:  ostream out is open.
        Postcondition: Graphical representation of BST has been output to out.
        Note: graph() uses private auxiliary function graphAux().
     ------------------------------------------------------------------------*/
     
      int treeHeight();
      /*------------------------------------------------------------------------
        Deteremine the height of the BST.
    
        Precondition:  None.
        Postcondition: The height of the BST is returned.
     ------------------------------------------------------------------------*/
    
      int treeLeavesCount();
      /*------------------------------------------------------------------------
        Determine the number of leaves in the BST.
    
        Precondition:  None.
        Postcondition: The number of leaves in the BST is returned.
     ------------------------------------------------------------------------*/
    
    protected:
        
    	int nodeCnt;
    	int leafCnt;
         
     private:
      /***** Node class *****/
      class BinNode 
      {
       public:
        DataType data;
        BinNode * left;
        BinNode * right;
    
        // BinNode constructors
        // Default -- data part is default DataType value; both links are null.
        BinNode()
        : left(0), right(0)
        {}
    
        // Explicit Value -- data part contains item; both links are null.
        BinNode(DataType item)
        : data(item), left(0), right(0)
        {}
     
      };// end of class BinNode declaration
    
      typedef BinNode * BinNodePointer; 
      
      /***** Private Function Members *****/
      void search2(const DataType & item, bool & found,
                   BinNodePointer & locptr, BinNodePointer & parent) const;
     /*------------------------------------------------------------------------
       Locate a node containing item and its parent.
     
       Precondition:  None.
       Postcondition: locptr points to node containing item or is null if 
           not found, and parent points to its parent.#include <iostream>
     ------------------------------------------------------------------------*/
     
      void inorderAux(ostream & out, 
                      BinNodePointer subtreePtr) const;
      /*------------------------------------------------------------------------
        Inorder traversal auxiliary function.
    
        Precondition:  ostream out is open; subtreePtr points to a subtree 
            of this BST.
        Postcondition: Subtree with root pointed to by subtreePtr has been
            output to out.
     ------------------------------------------------------------------------*/
     
      void graphAux(ostream & out, int indent,
                          BinNodePointer subtreeRoot) const;
      /*------------------------------------------------------------------------
        Graph auxiliary function.
    
        Precondition:  ostream out is open; subtreePtr points to a subtree 
            of this BST.
        Postcondition: Graphical representation of subtree with root pointed 
            to by subtreePtr has been output to out, indented indent spaces.
     ------------------------------------------------------------------------*/
    
      int max(int x, int y);
      /*------------------------------------------------------------------------
        Function to determine the larger of x and y.
    
        Precondition:  None
        Postcondition: The larger of x and y is returned
     ------------------------------------------------------------------------*/
       
      int height(BinNodePointer subtreeRoot);
      /*------------------------------------------------------------------------
        Height function.
    
        Precondition:  None
        Postcondition: The height of the BST to which p points is returned.
     ------------------------------------------------------------------------*/
     
      int leavesCount(BinNodePointer subtreeRoot);
      /*------------------------------------------------------------------------
        Leaves Count function.
    
        Precondition:  None
        Postcondition: The number of nodes in the BST to which p points 
            is returned.
     ------------------------------------------------------------------------*/
       
     /***** Data Members *****/
      BinNodePointer myRoot; 
    
    }; // end of class template declaration
    
    //--- Definition of constructor
    template <typename DataType>
    inline BST<DataType>::BST()
    : myRoot(0)
    {
       nodeCnt = 0;
       leafCnt = 0;
    }
    
    //--- Definition of empty()
    template <typename DataType>
    inline bool BST<DataType>::empty() const
    { return myRoot == 0; }
    
    //--- Definition of search()
    template <typename DataType>
    bool BST<DataType>::search(const DataType & item) const
    {
       BinNodePointer locptr = myRoot;
       bool found = false;
       while (!found && locptr != 0)
       {
          if (item < locptr->data)       // descend left
            locptr = locptr->left;
          else if (locptr->data < item)  // descend right
            locptr = locptr->right;
          else                           // item found
            found = true;
       }
       return found;
    }
    
    //--- Definition of insert()
    template <typename DataType>
    inline void BST<DataType>::insert(const DataType & item)
    {
       BinNodePointer 
            locptr = myRoot,   // search pointer
            parent = 0;        // pointer to parent of current node
       bool found = false;     // indicates if item already in BST
       while (!found && locptr != 0)
       {
          parent = locptr;
          if (item < locptr->data)       // descend left
             locptr = locptr->left;
          else if (locptr->data < item)  // descend right
             locptr = locptr->right;
          else                           // item found
             found = true;
       }
       if (!found)
       {                                 // construct node containing item
          locptr = new BinNode(item);  
          if (parent == 0)               // empty tree
             myRoot = locptr;
          else if (item < parent->data )  // insert to left of parent
             parent->left = locptr;
          else                           // insert to right of parent
             parent->right = locptr;
       }
       else
          cout << "Item already in the tree\n";
    }
    
    //--- Definition of remove()
    template <typename DataType>
    void BST<DataType>::remove(const DataType & item)
    {
       bool found;                      // signals if item is found
       BinNodePointer 
          x,                            // points to node to be deleted
          parent;                       //    "    " parent of x and xSucc
       search2(item, found, x, parent);
    
       if (!found)
       {
          cout << "Item not in the BST\n";
          return;
       }
       //else
       if (x->left != 0 && x->right != 0)
       {                                // node has 2 children
          // Find x's inorder successor and its parent
          BinNodePointer xSucc = x->right;
          parent = x;
          while (xSucc->left != 0)       // descend left
          {
             parent = xSucc;
             xSucc = xSucc->left;
          }
    
         // Move contents of xSucc to x and change x 
         // to point to successor, which will be removed.
         x->data = xSucc->data;
         x = xSucc;
       } // end if node has 2 children
    
       // Now proceed with case where node has 0 or 2 child
       BinNodePointer 
          subtree = x->left;             // pointer to a subtree of x
       if (subtree == 0)
          subtree = x->right;
       if (parent == 0)                  // root being removed
          myRoot = subtree;
       else if (parent->left == x)       // left child of parent
          parent->left = subtree; 
       else                              // right child of parent
          parent->right = subtree;
       delete x;
    }
    
    //--- Definition of inorder()
    template <typename DataType>
    inline void BST<DataType>::inorder(ostream & out) const
    { 
       inorderAux(out, myRoot); 
    }
    
    //--- Definition of graph()
    template <typename DataType>
    inline void BST<DataType>::graph(ostream & out) const
    { 
       graphAux(out, 0, myRoot); 
    }
    
    //--- Definition of treeHeight()
    template <typename DataType>
    int BST<DataType>::treeHeight()
    {
       int height();
    } 
    //--- Definition of treeLeavesCount()
    template <typename DataType>
    int BST<DataType>::treeLeavesCount()
    {
       int leavesCount();    
    }        
    
    //--- Definition of search2()
    template <typename DataType>
    void BST<DataType>::search2(const DataType & item, bool & found,
                                BinNodePointer & locptr, 
                                BinNodePointer & parent) const
    {
       locptr = myRoot;
       parent = 0;
       found = false;
       while (!found && locptr != 0)
       {
          if (item < locptr->data)       // descend left
          {
             parent = locptr;
             locptr = locptr->left;
          }
          else if (locptr->data < item)  // descend right
          {
             parent = locptr;
             locptr = locptr->right;
          }
          else                           // item found
             found = true;
       }
    }
    
    //--- Definition of inorderAux()
    template <typename DataType>
    void BST<DataType>::inorderAux(ostream & out, 
                                   BinNodePointer subtreeRoot) const
    {
       if (subtreeRoot != 0)
       {
          inorderAux(out, subtreeRoot->left);    // L operation
          out << subtreeRoot->data << "  ";      // V operation
          inorderAux(out, subtreeRoot->right);   // R operation
       }
    }
    
    //--- Definition of graphAux()
    #include <iomanip>
    
    template <typename DataType>
    void BST<DataType>::graphAux(ostream & out, int indent, 
                                 BinNodePointer subtreeRoot) const
    {
      if (subtreeRoot != 0)
        {
          graphAux(out, indent + 8, subtreeRoot->right);
          out << setw(indent) << " " << subtreeRoot->data << endl;
          graphAux(out, indent + 8, subtreeRoot->left);
        }
    }
    //--- Definition of height()
    template <typename DataType>
    int BST<DataType>::height(BinNodePointer subtreeRoot)
    {
    
       if(subtreeRoot == NULL)
    	  return 0;
       else
          return 1 + max(height(subtreeRoot->left), height(subtreeRoot->right));
    }
    
    //--- Definition of max()
    template <typename DataType>
    int BST<DataType>::max(int x, int y)
    {
    	if(x >= y)
    		return x;
    	else
    		return y;
    }
    
    //--- Definition of leavesCount()
    template <typename DataType>
    int BST<DataType>::leavesCount(BinNodePointer subtreeRoot)
    {
           
       if (subtreeRoot->left != NULL)
       {
          ++leafCnt;
          leavesCount(subtreeRoot->left);   // total leaves in the left nodes
       }
    
       if (subtreeRoot->right != NULL)
       {
          ++leafCnt;
          leavesCount(subtreeRoot->right);	// total leaves in the right nodes
       }
    
       return leafCnt;
    }
    
    #endif
    Here is my driver program

    Code:
    #include <cctype>       // Provides toupper
    #include <iostream>     // Provides cout and cin
    #include <cassert>
    #include <iomanip>
    #include <cstdlib>      // Provides EXIT_SUCCESS
    using namespace std;
    #include "BST.h" 
    
    /* PROTOTYPES: */
    void print_menu( );
    /* Postcondition: A menu of choices has been printed. */
       
    int main( )
    {
        BST<int> intBST;
        char choice;   /* Command entered by the user */
        int number;
    
        do
        {
            print_menu( );
            cout << "Enter choice: ";
            cin >> choice; // Input of characters skips blanks and newline character
            choice = toupper(choice); 
                            
            switch (choice)
            {
                case 'C': // Test treeLeavesCount()
                          cout<<"\nThe number of leaves in the tree is/are: " 
                              << intBST.treeLeavesCount() <<"\n";
                          break; 
                case 'E': // Test empty()
                          cout << "Constructing empty BST\n";
                          cout << "BST " << (intBST.empty() ? "is" : "is not") << " empty\n";                     
                          break;
                case 'H': // Test treeHeight()
                          cout<<"\nThe number of nodes in the tree is/are: " 
                          << intBST.treeHeight() <<"\n";
                          break;                       
                case 'I': // Test insert()
                          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\n";
                          cout << "Inorder Traversal of BST: \n";
                          intBST.inorder(cout);
                          cout << endl;
                          break;
                case 'P': // Print list
                          cout << "Inorder Traversal of BST: \n";
                          intBST.inorder(cout);
                          cout << endl;     
                          break;
                case 'R': // Test remove()
                          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;                      
                          break;
                case 'S': // Test search()
                          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;
                          }    
                          break;            
                case 'Q': cout << "\nTest program ended." << endl;
                          break;
                default:  cout << choice << " is invalid." << endl;
            }
        }
        while ((choice != 'Q'));
    
        system ("pause");
        return 0;
        return EXIT_SUCCESS;
    }
    
    void print_menu( )
    {
        cout << endl; 
        cout << "The following choices are available: " << endl;
        cout << " C   Print the Tree Leaves Count with the treeLeavesCount( ) function" << endl;
        cout << " E   Print the result from the empty( ) function" << endl;
        cout << " H   Print the Tree Height with the treeHeight( ) function" << endl;
        cout << " I   Insert numbers into the BST with the insert(...) function" << endl;
        cout << " P   Print the Inorder Traversal with the inorder( ) function" << endl;
        cout << " R   Remove item from BST with the remove( ) function" << endl;
        cout << " S   Search for the location of an item with the search( ) function" << endl;
        cout << " Q   Quit this test program" << endl;
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Code:
    //--- Definition of treeHeight()
    template <typename DataType>
    int BST<DataType>::treeHeight()
    {
       int height();
    }
    //--- Definition of treeLeavesCount()
    template <typename DataType>
    int BST<DataType>::treeLeavesCount()
    {
       int leavesCount();   
    }
    Aren't you supposed to actually return a value?
    Elysia likes this.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. counters
    By XodoX in forum C++ Programming
    Replies: 22
    Last Post: 03-08-2009, 10:51 PM
  2. Cycle counters
    By cosmo1996 in forum C Programming
    Replies: 3
    Last Post: 08-14-2007, 09:33 AM
  3. array of counters
    By luigi40 in forum C# Programming
    Replies: 3
    Last Post: 12-11-2005, 01:25 AM
  4. Passing My Counters
    By djwicks in forum C Programming
    Replies: 7
    Last Post: 03-26-2005, 09:17 PM
  5. counters..omg :S
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 04-09-2003, 08:58 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21