Binary Search Tree Header

[COL_Milkshake]

I desperately need help with a project I am working on. I need to create and implement a Binary Search Tree Header file. I am having great difficulty with this and was hoping I could find some help here.

This is what I have done(note: I am aware that the delete item function is not written):

#include <iostream>
#include <string>
using namespace std;


struct Node {

	int		item;
	Node	*leftChild;
	Node	*rightChild;

};


class	BinarySearchTree {

	public:

		BinarySearchTree();								// constructor.

		~BinarySearchTree();							// destructor.

		void insertItem(Node *& curPtr, int newValue);	// insert a value into BST.
		
		bool SearchItem(Node *curPtr, int searchKey);	// search the key in BST

		void deleteItem(Node *& curPtr, int searchKey);	// delete the key in BST

		void preorderTraverse(Node *curPtr);			// preorder traverse.

		void inorderTraverse(Node *curPtr);				// inorder traverse.

		void postorderTraverse(Node *curPtr);			// postoder traverse.

		int numberOfNodes(Node *curPtr);				// counting the number of nodes.

		int heightOfTree(Node *curPtr);					// computing the height of BST

		int maxElement(Node *curPtr);					// finding the max. value in BST

		int averageOfElements(Node *curPtr);			// computing the average value from BST

		Node *getRoot();								// get the ptr to the root node

	private:

		Node *rootPtr;
}
//--------------------------------------------------------------------
		//CONSTUCTOR
//--------------------------------------------------------------------
	
	BinarySearchTree()
	{
        Node* root = NULL;
	}
//--------------------------------------------------------------------
		//DESTRUCTOR
//--------------------------------------------------------------------
	~BinarySearchTree()
	{

		if (curPtr != NULL)
		{
			delete (*curPtr -> leftChild);
			delete (*curPtr -> rightChild);
			delete *curPtr;
		}
	}
//--------------------------------------------------------------------
		//INSERT ITEM
//--------------------------------------------------------------------
void insertItem(Node*& curPtr, int newValue)
{
			if (curPtr->item = NULL)
				curPtr->item = newValue;
			
			else if (newValue > curPtr->item)
				insertItem(curPtr->rightChild, newValue);

			else
				insertItem(curPtr->leftChild, newValue);
		}
//--------------------------------------------------------------------
		//SEARCH ITEM
//--------------------------------------------------------------------
	bool SearchItem(Node *curPtr, int searchKey);
	{
		if (curPtr == searchKey)
		{
			return true;
		}
		else if (curPtr < searchKey && curPtr->leftChild != NULL)
		{
			searchItem(curPtr->leftChild, searchKey);
		}
		else if (curPtr > searchKey && curPtr->rightChild != NULL)
		{
			searchItem(curPtr->rightChild, searchKey);
		}
		else
			return false;
	}
//--------------------------------------------------------------------
		//DELETE ITEM
//--------------------------------------------------------------------
	
//--------------------------------------------------------------------
		//PRE-ORDER TRAVERSAL
//--------------------------------------------------------------------
	void preorderTraverse(Node *curPtr)
	{
        if (curPtr != NULL ) 
		{ 
           cout << curPtr->item << " ";     
           preorderTraverse( curPtr->leftChild ); 
           preorderTraverse( curPtr->rightChild );   
        }
     }
//--------------------------------------------------------------------
		//IN-ORDER TRAVERSAL
//--------------------------------------------------------------------
	void inorderTraverse(Node *curPtr)
	{
        if ( curPtr != NULL ) 
		{ 
			inorderTraverse( curPtr->leftChild );
			cout << curPtr->item << " "; 
			inorderTraverse( curPtr->rightChild );   
        }
     }
//--------------------------------------------------------------------
		//POST-ORDER TRAVERSAL
//--------------------------------------------------------------------
	void postorderTraverse(Node *curPtr)
	{
		if ( curPtr != NULL )
		{
			postorderTraverse( curPtr->leftChild );
			postorderTraverse( curPtr->rightChild );
			cout << curPtr->item << " "; 
		}
	}
//--------------------------------------------------------------------
		//NUMBER OF NODES
//--------------------------------------------------------------------
	int numberOfNodes(Node *curPtr, int count)
	{
	
		if ( curPtr == NULL )
			   return 0;
		else 
		{
			   count++;
			   count += numberOfNodes(curPtr->leftChild, count); 
			   count += numberOfNodes(curPtr->rightChild, count); 
			   return count;
		}
	}
//--------------------------------------------------------------------
		//HEIGHT OF TREE
//--------------------------------------------------------------------
	int heightOfTree(Node *curPtr, int heightCounter)
	{
		if(curPtr->item == NULL)
			return heightCounter;

		else if (curPtr->leftChild == NULL && curPtr->rightChild == NULL)
		{
			heightCounter++;
			return heightCounter;
		}
		else
			heightOfTree(curPtr->leftChild, heightCounter);
			heightOfTree(curPtr->rightChild, heightCounter);
	}
//--------------------------------------------------------------------
		//MAX ELEMENT
//--------------------------------------------------------------------
	int maxElement(Node *curPtr)
	{
		if(curPtr-> rightChild == NULL)
		{
			return curPtr->item;
		}
		else
		{
			maxElement(curPtr->rightChild);
		}
	}
//--------------------------------------------------------------------
		//AVERAGE OF ELEMENTS
//--------------------------------------------------------------------
	int averageOfElements(Node *curPtr)
	{
		int average, total=0, divsior=0;

		numberOfNodes(curPtr, divisor);

		if(curPtr->item != NULL)
		{
			total += curPtr->item;
			total += averageOfElements(curPtr->leftChild);
			total += averageOfElements(curPtr->rightChild);
		}
		else
			return total/divisor;
	}

NOTE: Must be recursive and I'm sorry for the weird spacing on code.

[pseudorandom21]

What problems are you having?

[COL_Milkshake]

The mains issue is the Constructor and Destructor functions give me errors when I try to compile it. I am also looking to see if my functions look like they will work.

[L7Sqr]

To answer the question about the constructor/destructor failing compilation: You need to prefix methods of a class with the class name when defining them outside the scope of the class declaration. To make that more concrete look at the following example

class Foo {
   public:
      Foo() { /* constructor here is OK, defined inside the class declaration */ }
};

class Bar {
   public:
      Bar(); /* needs external definition */
};

// Definition external to the class declaration
Bar::Bar () {
   // ...
}

That goes for all your class methods, by the way.

As far as whether your code looks ok, well, that is a more difficult problem. Pointers are a source of many subtle problems. The best advise I can give is to get the code compiled and start running it with small inputs. Once you start to see behavior you do not expect try to narrow down the area it is happening in and post back with specific questions.

[COL_Milkshake]

Thanks for the info on the prefix method, that fixed my original constructor issue however now it gives the error:

'BinarySearchTree::{ctor}' : constructors not allowed a return type

[mike_2000_17]

>>'BinarySearchTree::{ctor}' : constructors not allowed a return type
If there is a return type, erase it. If there isn't a return type, then look at the code before the definition of the constructor to see if you made some mistake (like forgetting a closing bracket).

There are several subtle errors in your code. First, I think you have mixed up curPtr and curPtr->item at several points. I suggest you take a close rereading of the code with that in mind. My own, quick scan of it reveals several places where it is suspicious: Lines 75, 89, 93, 97, 165 and 200. Also, you have a single equal sign where there should be two at line 75.

Second, your destructor is not correct. In fact, it won't compile. You are deleting dereferenced pointers, when you have to delete the pointers themselves. So, to make it compile it would have to be:

BinarySearchTree::~BinarySearchTree()
{
  if (rootPtr != NULL)
  {
    if(rootPtr->leftChild != NULL)
      delete rootPtr->leftChild;
    if(rootPtr->rightChild != NULL)
      delete rootPtr->rightChild;
    delete rootPtr;
  }
}

However, this is still wrong because you are not deleting all the elements of the tree, only the top three nodes. Technically, you would have to traverse the tree down to the leafs and delete all the pointers on your way back up. However, the easiest thing to do is to write a destructor for the Node class that takes care of deleting its children (which will trigger a recursive deletion of the entire tree). So I would suggest you add at least this to your Node class:

struct Node {

  int  item;
  Node *leftChild;
  Node *rightChild;

  ~Node() {
    if(leftChild)   //this is btw equivalent to if(leftChild != NULL)
      delete leftChild;
    if(rightChild)
      delete rightChild;
  };
};

Then, all your BST destructor has to do is delete the root Node and let the recursive deletion do the rest:

BinarySearchTree::~BinarySearchTree()
{
  if(rootPtr != NULL)
    delete rootPtr; //that will make rootPtr delete its children and their children, and so on...
};

As a final remark, I would say that your use of recursion in this problem is very nice, but it could be really awesome if you think about it a bit more. As a technical recommendation, it is not advisable to have all these public recursive functions that take a pointer to the current node, that requires the user to manually feed to start of the recursion with the rootPtr. Typically, for good style and coding practices, people will expose a non-recursive function as public and hide away a corresponding recursive function, as so for example (for a factorial):

class MyInt {
  private:
    int getFactorialImpl(int currentValue) {
      if(currentValue == 0)
        return 1;
      else
        return currentValue * getFactorialImpl(--currentValue);
    };
  
    int value;
  public:
    MyInt(int aValue) { value = aValue; };

    int getFactorial() { //expose non-recursive function
      return getFactorialImpl(value); //call the private recursive function
    };
};

As a final hint towards improving your code, Why have you decided to implement all those functions in the BinarySearchTree class? By the recursive nature of the algorithms and the recursive nature of the tree, it would seem there is a more natural place for these functions to be.. no?

[COL_Milkshake]

Thanks so much Mike. After changing the destructor I looked at the constructor and realized that I was missing a semi colon. Now it is compiling and I can take a closer look at how each function works to tweak them. Also, the reason I am using so many public functions is because that is what the assignment requires. Also as for the use of the root pointer I think that will be changed in the final version at the moment I want to be able to manipulate where it starts from.