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;
}