1Likes
LinkBack URL
About LinkBacks
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.
Here is my driver programCode:/*-- 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
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; }
I used to be an adventurer like you... then I took an arrow to the knee.