[AlexH]

Hi everyone,

I have an assignment where I am supposed to create a method that counts the number of leaves in a binary search tree. I am confident that it will work once I test it. The problem is, VS won't let me access the root of the tree when I use it as a parameter in my function. The root is declared as protected in binaryTreeType class, which is inherited by the bSearchTreeType class. The function is implemented in the binaryTreetype class. I beleive the problem is that you aren't allowed to access private members from the main function. I don't know how to fix it though. Here is my code.

Thank you for any help!

Main function:

// DS Week 3 Page 716 Exerercise 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "binaryTree.h"
#include "binarySearchTree.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
	bSearchTreeType<int> * bstt = new bSearchTreeType<int>();

	int i = 0;
	bool keepGoing = true;
	
	cout << "We are going to build a binary tree now." << endl;

	while(keepGoing)
	{
		
		cout << "Please enter a number." << endl;
		cin >> i;
		cout << "you entered " << i << endl;
		bstt->insert(i);
		cout << "Do you want to continue?  Enter 1 for yes and 0 for no." << endl;
		cin >> keepGoing;

	}

	//cout << "height: " << bstt->treeHeight() << endl;
	cout << "number of leaves: " << bstt->leavesCount(bstt->root) << endl;

}

binaryTreeType class:

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

	 //Definition of the node
template<class elemType>
struct nodeType
{
   elemType			   info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

	//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
	const binaryTreeType<elemType>& operator=
				 (const binaryTreeType<elemType>&); 
	  //Overload the assignment operator.
	bool isEmpty();
	  //Function to determine if the binary tree is empty.
	  //Postcondition: Returns true if the binary tree is empty;
	  //			   otherwise, returns false.
	void inorderTraversal();
	  //Function to do an inorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the inorder sequence.
	void preorderTraversal();
	  //Function to do a preorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the preorder sequence.
	void postorderTraversal();
	  //Function to do a postorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the postorder sequence.

	int treeHeight();
	  //Function to deteremine the height of the binary tree.
	  //Postcondition: The height of the binary tree is returned.
	int treeNodeCount();
	  //Function to determine the number of nodes in the 
	  //binary tree.
	  //Postcondition: The number of nodes in the binary tree
	  //			   is returned.
	int treeLeavesCount();
	  //Function to determine the number of leaves in the 
	  //binary tree.
	  //Postcondition: The number of leaves in the binary tree
	  //			   is returned.
	void destroyTree();
	  //Deallocates the memory space occupied by the binary tree.
	  //Postcondition: root = NULL;

	binaryTreeType(const binaryTreeType<elemType>& otherTree); 
	  //copy constructor

	binaryTreeType();   
	  //default constructor

	~binaryTreeType();   
	  //destructor

protected:
	nodeType<elemType> *root;

private:
	void copyTree(nodeType<elemType>* &copiedTreeRoot,
				  nodeType<elemType>* otherTreeRoot);
	  //Function to make a copy of the binary tree to 
	  //which otherTreeRoot points. 
	  //Postcondition: The pointer copiedTreeRoot points to
	  //			   the root of the copied binary tree.

	void destroy(nodeType<elemType>* &p);
	  //Function to destroy the binary tree to which p points. 
	  //Postcondition: The nodes of the binary tree to which
	  //			   p points are deallocated.
	  //			   p = NULL.

	void inorder(nodeType<elemType> *p);
	  //Function to do an inorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the inorder sequence.
	void preorder(nodeType<elemType> *p);
	  //Function to do a preorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the preorder sequence.
	void postorder(nodeType<elemType> *p);
	  //Function to do a postorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the postorder sequence.

	int height(nodeType<elemType> *p);
	  //Function to determine the height of the binary tree
	  //to which p points. 
	  //Postcondition: The height of the binary tree to which p
	  //			   points is returned.

	int max(int x, int y);
	  //Function to determine the larger of x and y.
	  //Postcondition: The larger of x and y is returned.

	int nodeCount(nodeType<elemType> *p);
	  //Function to determine the number of nodes in the binary 
	  //tree to which p points. 
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.

	int leavesCount(nodeType<elemType> *p);
	  //Function to determine the number of leaves in the binary 
	  //tree to which p points.
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.
};

	//Definition of member functions

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
	return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
	inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
	preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
	postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
	return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
	return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
	return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
					  (nodeType<elemType>* &copiedTreeRoot,
					   nodeType<elemType>* otherTreeRoot)
{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
	}
} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		inorder(p->llink);
		cout<<p->info<<" ";
		inorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		cout<<p->info<<" ";
		preorder(p->llink);
		preorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout<<p->info<<" ";
	}		
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
		   operator=(const binaryTreeType<elemType>& otherTree)
{ 
	 
	if(this != &otherTree) //avoid self-copy
	{
		if(root != NULL)  //if the binary tree is not empty, 
						  //destroy the binary tree
			destroy(root);

		if(otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
	}//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
	if(p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
	}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
	destroy(root);
}

	//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
			  (const binaryTreeType<elemType>& otherTree)
{
	if(otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
	destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
	if(p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
	if(x >= y)
		return x;
	else
		return y;
}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
	cout<<"Write the definition of the function nodeCount"
		<<endl;

	return 0;
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p, int)
{

	// make sure node exists
	if (p != NULL)
	{
		// if node is a leaf
		if (p->llink =  NULL && p->rlink == NULL)
		{
			return 1;
		}

		else
		{
			return leavesCount(p->llink) + leavesCount(p->rlink);
		}
	}

	else
	{
		return 0;
	}
}

#endif

bSearchTreeType class:

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
	bool search(const elemType& searchItem);
	  //Function to determine if searchItem is in the binary 
	  //search tree.
	  //Postcondition: Returns true if searchItem is found in the 
	  //			 binary search tree; otherwise, returns false.

	void insert(const elemType& insertItem);
	  //Function to insert insertItem in the binary search tree.
	  //Postcondition: If no node in the binary search tree has 
	  //		   the same info as insertItem, a node with the 
	  //		   info insertItem is created and inserted in the
	  //binary search tree.

	void deleteNode(const elemType& deleteItem);
	  //Function to delete deleteItem from the binary search tree 
	  //Postcondition: If a node with the same info as deleteItem 
	  //			   is found, it is deleted from the binary 
	  //			   search tree.

private:
	void deleteFromTree(nodeType<elemType>* &p);
	  //Function to delete the node, to which p points, from the 
	  //binary search tree.
	  //Postcondition: The node to which p points is deleted
	  //			   from the binary search tree.
};


template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
	nodeType<elemType> *current;
	bool found = false;

	if(root == NULL)
	   cerr<<"Cannot search the empty tree."<<endl;
	else
	{ 
	   current = root;

	   while(current != NULL && !found)
	   {
			 if(current->info == searchItem)
				found = true;
			  else
				  if(current->info > searchItem)
					 current = current->llink;
				  else
					 current = current->rlink;
	   }//end while
	}//end else

	return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	nodeType<elemType> *newNode;  //pointer to create the node

	newNode = new nodeType<elemType>;
	assert(newNode != NULL);
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if(root == NULL)
	   root = newNode;
	else
	{
	   current = root;
 
	   while(current != NULL)
	   {
		   trailCurrent = current;

		   if(current->info == insertItem)
		   {
			  cerr<<"The insert item is already in the list -- ";
			  cerr<<"duplicates are not allowed."<<endl;
			  return;
		   }
		   else
			  if(current->info > insertItem)
				 current = current->llink;
			  else
				 current = current->rlink;
	   }//end while

	   if(trailCurrent->info > insertItem)
		  trailCurrent->llink = newNode;
	   else
		  trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(current->info == deleteItem)
				found = true;
			else
			{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
			}//end if
	}
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
								 (nodeType<elemType>* &p)
{
	 nodeType<elemType> *current;	//pointer to traverse 
									 //the tree
	 nodeType<elemType> *trailCurrent;   //pointer behind current
	 nodeType<elemType> *temp;		//pointer to delete the node

	 if(p == NULL)
		cerr<<"Error: The node to be deleted is NULL."
			<<endl;
	 else if(p->llink == NULL && p->rlink == NULL)
		  {
			 temp = p;
			 p = NULL;
			 delete temp;
		  }
	 else if(p->llink == NULL)
		  {
			 temp = p;
			 p = temp->rlink;
			 delete temp;
		  }
	 else if(p->rlink == NULL)
		  {
			 temp = p;
			 p = temp->llink;
			 delete temp;
		  }
	 else
	 {
		current = p->llink;
		trailCurrent = NULL;

		while(current->rlink != NULL)
		{
			trailCurrent = current;
			current = current->rlink;
		}//end while

		p->info = current->info;

		if(trailCurrent == NULL) //current did not move; 
								 //current == p->llink; adjust p
		   p->llink = current->llink;
		else
		   trailCurrent->rlink = current->llink;
 
		delete current;
	 }//end else
}//end deleteFromTree


#endif

[KYA]

Make a getRoot() function that returns the root?

[AlexH]

Ok I tried that, but it gives an error that says "error C2039: 'getRoot' : is not a member of 'bSearchTreeType<elemType>'

How is that possible when I have getRoot DEFINED in the bSearchTreeType class? Here is the class with getRoot added to it.

bSearchTreetype class:

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
	bool search(const elemType& searchItem);
	  //Function to determine if searchItem is in the binary 
	  //search tree.
	  //Postcondition: Returns true if searchItem is found in the 
	  //			 binary search tree; otherwise, returns false.

	void insert(const elemType& insertItem);
	  //Function to insert insertItem in the binary search tree.
	  //Postcondition: If no node in the binary search tree has 
	  //		   the same info as insertItem, a node with the 
	  //		   info insertItem is created and inserted in the
	  //binary search tree.

	void deleteNode(const elemType& deleteItem);
	  //Function to delete deleteItem from the binary search tree 
	  //Postcondition: If a node with the same info as deleteItem 
	  //			   is found, it is deleted from the binary 
	  //			   search tree.

private:
	void deleteFromTree(nodeType<elemType>* &p);
	  //Function to delete the node, to which p points, from the 
	  //binary search tree.
	  //Postcondition: The node to which p points is deleted
	  //			   from the binary search tree.
};

template<class elemType>
nodeType<elemType> * bSearchTreeType<elemType>::getRoot()
	{
		return root;
	}

template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
	nodeType<elemType> *current;
	bool found = false;

	if(root == NULL)
	   cerr<<"Cannot search the empty tree."<<endl;
	else
	{ 
	   current = root;

	   while(current != NULL && !found)
	   {
			 if(current->info == searchItem)
				found = true;
			  else
				  if(current->info > searchItem)
					 current = current->llink;
				  else
					 current = current->rlink;
	   }//end while
	}//end else

	return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	nodeType<elemType> *newNode;  //pointer to create the node

	newNode = new nodeType<elemType>;
	assert(newNode != NULL);
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if(root == NULL)
	   root = newNode;
	else
	{
	   current = root;
 
	   while(current != NULL)
	   {
		   trailCurrent = current;

		   if(current->info == insertItem)
		   {
			  cerr<<"The insert item is already in the list -- ";
			  cerr<<"duplicates are not allowed."<<endl;
			  return;
		   }
		   else
			  if(current->info > insertItem)
				 current = current->llink;
			  else
				 current = current->rlink;
	   }//end while

	   if(trailCurrent->info > insertItem)
		  trailCurrent->llink = newNode;
	   else
		  trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(current->info == deleteItem)
				found = true;
			else
			{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
			}//end if
	}
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
								 (nodeType<elemType>* &p)
{
	 nodeType<elemType> *current;	//pointer to traverse 
									 //the tree
	 nodeType<elemType> *trailCurrent;   //pointer behind current
	 nodeType<elemType> *temp;		//pointer to delete the node

	 if(p == NULL)
		cerr<<"Error: The node to be deleted is NULL."
			<<endl;
	 else if(p->llink == NULL && p->rlink == NULL)
		  {
			 temp = p;
			 p = NULL;
			 delete temp;
		  }
	 else if(p->llink == NULL)
		  {
			 temp = p;
			 p = temp->rlink;
			 delete temp;
		  }
	 else if(p->rlink == NULL)
		  {
			 temp = p;
			 p = temp->llink;
			 delete temp;
		  }
	 else
	 {
		current = p->llink;
		trailCurrent = NULL;

		while(current->rlink != NULL)
		{
			trailCurrent = current;
			current = current->rlink;
		}//end while

		p->info = current->info;

		if(trailCurrent == NULL) //current did not move; 
								 //current == p->llink; adjust p
		   p->llink = current->llink;
		else
		   trailCurrent->rlink = current->llink;
 
		delete current;
	 }//end else
}//end deleteFromTree


#endif

[KYA]

I don't see it declared "within" your class under the public area.

[AlexH]

KYA, on 24 Nov, 2008 - 01:20 PM, said:

I don't see it declared "within" your class under the public area.

Sorry about that. That was another version of the code. Here's the right one.

Main

// DS Week 3 Page 716 Exerercise 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "binaryTree.h"
#include "binarySearchTree.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
	bSearchTreeType<int> * bstt = new bSearchTreeType<int>();

	int i = 0;
	bool keepGoing = true;
	
	cout << "We are going to build a binary tree now." << endl;

	while(keepGoing)
	{
		
		cout << "Please enter a number." << endl;
		cin >> i;
		cout << "you entered " << i << endl;
		bstt->insert(i);
		cout << "Do you want to continue?  Enter 1 for yes and 0 for no." << endl;
		cin >> keepGoing;

	}

	//cout << "height: " << bstt->treeHeight() << endl;
	cout << "number of leaves: " << bstt->leavesCount(bstt->getRoot()) << endl;

}

bSearchTreeType class[

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
	bool search(const elemType& searchItem);
	  //Function to determine if searchItem is in the binary 
	  //search tree.
	  //Postcondition: Returns true if searchItem is found in the 
	  //			 binary search tree; otherwise, returns false.

	void insert(const elemType& insertItem);
	  //Function to insert insertItem in the binary search tree.
	  //Postcondition: If no node in the binary search tree has 
	  //		   the same info as insertItem, a node with the 
	  //		   info insertItem is created and inserted in the
	  //binary search tree.

	void deleteNode(const elemType& deleteItem);
	  //Function to delete deleteItem from the binary search tree 
	  //Postcondition: If a node with the same info as deleteItem 
	  //			   is found, it is deleted from the binary 
	  //			   search tree.

	template<class elemType>
nodeType<elemType> * bSearchTreeType<elemType>::getRoot()
	{
		return root;
	}

private:
	void deleteFromTree(nodeType<elemType>* &p);
	  //Function to delete the node, to which p points, from the 
	  //binary search tree.
	  //Postcondition: The node to which p points is deleted
	  //			   from the binary search tree.
};



template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
	nodeType<elemType> *current;
	bool found = false;

	if(root == NULL)
	   cerr<<"Cannot search the empty tree."<<endl;
	else
	{ 
	   current = root;

	   while(current != NULL && !found)
	   {
			 if(current->info == searchItem)
				found = true;
			  else
				  if(current->info > searchItem)
					 current = current->llink;
				  else
					 current = current->rlink;
	   }//end while
	}//end else

	return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	nodeType<elemType> *newNode;  //pointer to create the node

	newNode = new nodeType<elemType>;
	assert(newNode != NULL);
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if(root == NULL)
	   root = newNode;
	else
	{
	   current = root;
 
	   while(current != NULL)
	   {
		   trailCurrent = current;

		   if(current->info == insertItem)
		   {
			  cerr<<"The insert item is already in the list -- ";
			  cerr<<"duplicates are not allowed."<<endl;
			  return;
		   }
		   else
			  if(current->info > insertItem)
				 current = current->llink;
			  else
				 current = current->rlink;
	   }//end while

	   if(trailCurrent->info > insertItem)
		  trailCurrent->llink = newNode;
	   else
		  trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(current->info == deleteItem)
				found = true;
			else
			{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
			}//end if
	}
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
								 (nodeType<elemType>* &p)
{
	 nodeType<elemType> *current;	//pointer to traverse 
									 //the tree
	 nodeType<elemType> *trailCurrent;   //pointer behind current
	 nodeType<elemType> *temp;		//pointer to delete the node

	 if(p == NULL)
		cerr<<"Error: The node to be deleted is NULL."
			<<endl;
	 else if(p->llink == NULL && p->rlink == NULL)
		  {
			 temp = p;
			 p = NULL;
			 delete temp;
		  }
	 else if(p->llink == NULL)
		  {
			 temp = p;
			 p = temp->rlink;
			 delete temp;
		  }
	 else if(p->rlink == NULL)
		  {
			 temp = p;
			 p = temp->llink;
			 delete temp;
		  }
	 else
	 {
		current = p->llink;
		trailCurrent = NULL;

		while(current->rlink != NULL)
		{
			trailCurrent = current;
			current = current->rlink;
		}//end while

		p->info = current->info;

		if(trailCurrent == NULL) //current did not move; 
								 //current == p->llink; adjust p
		   p->llink = current->llink;
		else
		   trailCurrent->rlink = current->llink;
 
		delete current;
	 }//end else
}//end deleteFromTree


#endif

binaryTreetype class

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

	 //Definition of the node
template<class elemType>
struct nodeType
{
   elemType			   info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

	//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
	const binaryTreeType<elemType>& operator=
				 (const binaryTreeType<elemType>&); 
	  //Overload the assignment operator.
	bool isEmpty();
	  //Function to determine if the binary tree is empty.
	  //Postcondition: Returns true if the binary tree is empty;
	  //			   otherwise, returns false.
	void inorderTraversal();
	  //Function to do an inorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the inorder sequence.
	void preorderTraversal();
	  //Function to do a preorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the preorder sequence.
	void postorderTraversal();
	  //Function to do a postorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the postorder sequence.

	int treeHeight();
	  //Function to deteremine the height of the binary tree.
	  //Postcondition: The height of the binary tree is returned.
	int treeNodeCount();
	  //Function to determine the number of nodes in the 
	  //binary tree.
	  //Postcondition: The number of nodes in the binary tree
	  //			   is returned.
	int treeLeavesCount();
	  //Function to determine the number of leaves in the 
	  //binary tree.
	  //Postcondition: The number of leaves in the binary tree
	  //			   is returned.
	void destroyTree();
	  //Deallocates the memory space occupied by the binary tree.
	  //Postcondition: root = NULL;

	binaryTreeType(const binaryTreeType<elemType>& otherTree); 
	  //copy constructor

	binaryTreeType();   
	  //default constructor

	~binaryTreeType();   
	  //destructor

	

protected:
	nodeType<elemType> *root;

private:
	void copyTree(nodeType<elemType>* &copiedTreeRoot,
				  nodeType<elemType>* otherTreeRoot);
	  //Function to make a copy of the binary tree to 
	  //which otherTreeRoot points. 
	  //Postcondition: The pointer copiedTreeRoot points to
	  //			   the root of the copied binary tree.

	void destroy(nodeType<elemType>* &p);
	  //Function to destroy the binary tree to which p points. 
	  //Postcondition: The nodes of the binary tree to which
	  //			   p points are deallocated.
	  //			   p = NULL.

	void inorder(nodeType<elemType> *p);
	  //Function to do an inorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the inorder sequence.
	void preorder(nodeType<elemType> *p);
	  //Function to do a preorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the preorder sequence.
	void postorder(nodeType<elemType> *p);
	  //Function to do a postorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the postorder sequence.

	int height(nodeType<elemType> *p);
	  //Function to determine the height of the binary tree
	  //to which p points. 
	  //Postcondition: The height of the binary tree to which p
	  //			   points is returned.

	int max(int x, int y);
	  //Function to determine the larger of x and y.
	  //Postcondition: The larger of x and y is returned.

	int nodeCount(nodeType<elemType> *p);
	  //Function to determine the number of nodes in the binary 
	  //tree to which p points. 
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.

	int leavesCount(nodeType<elemType> *p);
	  //Function to determine the number of leaves in the binary 
	  //tree to which p points.
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.
};

	//Definition of member functions

	template<class elemType>
	nodeType<elemType> * binaryTreetype<elemType>::binaryTreeType()
		{
			return root;
		}

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
	return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
	inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
	preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
	postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
	return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
	return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
	return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
					  (nodeType<elemType>* &copiedTreeRoot,
					   nodeType<elemType>* otherTreeRoot)
{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
	}
} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		inorder(p->llink);
		cout<<p->info<<" ";
		inorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		cout<<p->info<<" ";
		preorder(p->llink);
		preorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout<<p->info<<" ";
	}		
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
		   operator=(const binaryTreeType<elemType>& otherTree)
{ 
	 
	if(this != &otherTree) //avoid self-copy
	{
		if(root != NULL)  //if the binary tree is not empty, 
						  //destroy the binary tree
			destroy(root);

		if(otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
	}//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
	if(p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
	}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
	destroy(root);
}

	//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
			  (const binaryTreeType<elemType>& otherTree)
{
	if(otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
	destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
	if(p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
	if(x >= y)
		return x;
	else
		return y;
}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
	cout<<"Write the definition of the function nodeCount"
		<<endl;

	return 0;
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p, int)
{

	// make sure node exists
	if (p != NULL)
	{
		// if node is a leaf
		if (p->llink =  NULL && p->rlink == NULL)
		{
			return 1;
		}

		else
		{
			return leavesCount(p->llink) + leavesCount(p->rlink);
		}
	}

	else
	{
		return 0;
	}
}

#endif

[KYA]

New error or same?

Anyway, the getRoot thing still isn't in there right, what i mean is:

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
    bool search(const elemType& searchItem);
      //Function to determine if searchItem is in the binary
      //search tree.
      //Postcondition: Returns true if searchItem is found in the
      //             binary search tree; otherwise, returns false.

    void insert(const elemType& insertItem);
      //Function to insert insertItem in the binary search tree.
      //Postcondition: If no node in the binary search tree has
      //           the same info as insertItem, a node with the
      //           info insertItem is created and inserted in the
      //binary search tree.

    void deleteNode(const elemType& deleteItem);
      //Function to delete deleteItem from the binary search tree
      //Postcondition: If a node with the same info as deleteItem
      //               is found, it is deleted from the binary
      //               search tree.

nodeType<elemType> * getRoot(); 
// this is now properly definded within the class
//definition is placed outside

private:
    void deleteFromTree(nodeType<elemType>* &p);
      //Function to delete the node, to which p points, from the
      //binary search tree.
      //Postcondition: The node to which p points is deleted
      //               from the binary search tree.
};

//wherever your method definitions are
   template<class elemType>
nodeType<elemType> * bSearchTreeType<elemType>::getRoot()
    {
        return root;
    }

It could also be:

//within class
nodeType<elemType>* getRoot() {return root;};

My template skills are a little rusty so i could be way off here, but only the return value of the function is needed in the declaration and then in the definition the class name with the scope :: Might not need the template portion in the first code listing, try both.

This post has been edited by KYA: 24 November 2008 - 02:42 PM

[AlexH]

I'm still getting the same error. Thank you very much for trying though. I'm very frustrated today. Here is the code as it exists now with your changes.

Main

// DS Week 3 Page 716 Exerercise 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "binaryTree.h"
#include "binarySearchTree.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
	bSearchTreeType<int> * bstt = new bSearchTreeType<int>();

	int i = 0;
	bool keepGoing = true;
	
	cout << "We are going to build a binary tree now." << endl;

	while(keepGoing)
	{
		
		cout << "Please enter a number." << endl;
		cin >> i;
		cout << "you entered " << i << endl;
		bstt->insert(i);
		cout << "Do you want to continue?  Enter 1 for yes and 0 for no." << endl;
		cin >> keepGoing;

	}

	//cout << "height: " << bstt->treeHeight() << endl;
	cout << "number of leaves: " << bstt->leavesCount(bstt->getRoot()) << endl;

}

bSearchTreeType class

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
	{
	public:
		bool search(const elemType& searchItem);
		//Function to determine if searchItem is in the binary 
		//search tree.
		//Postcondition: Returns true if searchItem is found in the 
		//			 binary search tree; otherwise, returns false.

		void insert(const elemType& insertItem);
		//Function to insert insertItem in the binary search tree.
		//Postcondition: If no node in the binary search tree has 
		//		   the same info as insertItem, a node with the 
		//		   info insertItem is created and inserted in the
		//binary search tree.

		void deleteNode(const elemType& deleteItem);
		//Function to delete deleteItem from the binary search tree 
		//Postcondition: If a node with the same info as deleteItem 
		//			   is found, it is deleted from the binary 
		//			   search tree.

		nodeType<elemType> * getRoot();

	private:

		void deleteFromTree(nodeType<elemType>* &p);
		//Function to delete the node, to which p points, from the 
		//binary search tree.
		//Postcondition: The node to which p points is deleted
		//			   from the binary search tree.
	};



template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
	{
	nodeType<elemType> *current;
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot search the empty tree."<<endl;
	else
		{ 
		current = root;

		while(current != NULL && !found)
			{
			if(current->info == searchItem)
				found = true;
			else
				if(current->info > searchItem)
					current = current->llink;
				else
					current = current->rlink;
			}//end while
		}//end else

	return found;
	}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
	{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	nodeType<elemType> *newNode;  //pointer to create the node

	newNode = new nodeType<elemType>;
	assert(newNode != NULL);
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if(root == NULL)
		root = newNode;
	else
		{
		current = root;

		while(current != NULL)
			{
			trailCurrent = current;

			if(current->info == insertItem)
				{
				cerr<<"The insert item is already in the list -- ";
				cerr<<"duplicates are not allowed."<<endl;
				return;
				}
			else
				if(current->info > insertItem)
					current = current->llink;
				else
					current = current->rlink;
			}//end while

		if(trailCurrent->info > insertItem)
			trailCurrent->llink = newNode;
		else
			trailCurrent->rlink = newNode;
		}
	}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
	{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
		{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
			{
			if(current->info == deleteItem)
				found = true;
			else
				{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
				}
			}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
				{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
				}//end if
		}
	}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(nodeType<elemType>* &p)
	{
	nodeType<elemType> *current;	//pointer to traverse 
	//the tree
	nodeType<elemType> *trailCurrent;   //pointer behind current
	nodeType<elemType> *temp;		//pointer to delete the node

	if(p == NULL)
		cerr<<"Error: The node to be deleted is NULL."
		<<endl;
	else if(p->llink == NULL && p->rlink == NULL)
		{
		temp = p;
		p = NULL;
		delete temp;
		}
	else if(p->llink == NULL)
		{
		temp = p;
		p = temp->rlink;
		delete temp;
		}
	else if(p->rlink == NULL)
		{
		temp = p;
		p = temp->llink;
		delete temp;
		}
	else
		{
		current = p->llink;
		trailCurrent = NULL;

		while(current->rlink != NULL)
			{
			trailCurrent = current;
			current = current->rlink;
			}//end while

		p->info = current->info;

		if(trailCurrent == NULL) //current did not move; 
			//current == p->llink; adjust p
			p->llink = current->llink;
		else
			trailCurrent->rlink = current->llink;

		delete current;
		}//end else
	}//end deleteFromTree

template<class elemType>
nodeType<elemType> * binaryTreeType::getRoot()
	{
	return root;
	}
}

#endif

binaryTreeType class

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

//Definition of the node
template<class elemType>
struct nodeType
	{
	elemType			   info;
	nodeType<elemType>  *llink;
	nodeType<elemType>  *rlink;
	};

//Definition of the class
template <class elemType>
class binaryTreeType
	{
	public:
		const binaryTreeType<elemType>& operator=
			(const binaryTreeType<elemType>&); 
		//Overload the assignment operator.
		bool isEmpty();
		//Function to determine if the binary tree is empty.
		//Postcondition: Returns true if the binary tree is empty;
		//			   otherwise, returns false.
		void inorderTraversal();
		//Function to do an inorder traversal of the binary tree.
		//Postcondition: The nodes of the binary tree are output
		//			   in the inorder sequence.
		void preorderTraversal();
		//Function to do a preorder traversal of the binary tree.
		//Postcondition: The nodes of the binary tree are output
		//			   in the preorder sequence.
		void postorderTraversal();
		//Function to do a postorder traversal of the binary tree.
		//Postcondition: The nodes of the binary tree are output
		//			   in the postorder sequence.

		int treeHeight();
		//Function to deteremine the height of the binary tree.
		//Postcondition: The height of the binary tree is returned.
		int treeNodeCount();
		//Function to determine the number of nodes in the 
		//binary tree.
		//Postcondition: The number of nodes in the binary tree
		//			   is returned.
		int treeLeavesCount();
		//Function to determine the number of leaves in the 
		//binary tree.
		//Postcondition: The number of leaves in the binary tree
		//			   is returned.
		void destroyTree();
		//Deallocates the memory space occupied by the binary tree.
		//Postcondition: root = NULL;

		binaryTreeType(const binaryTreeType<elemType>& otherTree); 
		//copy constructor

		binaryTreeType();   
		//default constructor

		~binaryTreeType();   
		//destructor

		nodeType<elemType> * getRoot();

	protected:
		nodeType<elemType> *root;

	private:
		void copyTree(nodeType<elemType>* &copiedTreeRoot,
			nodeType<elemType>* otherTreeRoot);
		//Function to make a copy of the binary tree to 
		//which otherTreeRoot points. 
		//Postcondition: The pointer copiedTreeRoot points to
		//			   the root of the copied binary tree.

		void destroy(nodeType<elemType>* &p);
		//Function to destroy the binary tree to which p points. 
		//Postcondition: The nodes of the binary tree to which
		//			   p points are deallocated.
		//			   p = NULL.

		void inorder(nodeType<elemType> *p);
		//Function to do an inorder traversal of the binary
		//tree to which p points.  
		//Postcondition: The nodes of the binary tree to which p
		//			   points are output in the inorder sequence.
		void preorder(nodeType<elemType> *p);
		//Function to do a preorder traversal of the binary
		//tree to which p points.  
		//Postcondition: The nodes of the binary tree to which p
		//			   points are output in the preorder sequence.
		void postorder(nodeType<elemType> *p);
		//Function to do a postorder traversal of the binary
		//tree to which p points.  
		//Postcondition: The nodes of the binary tree to which p
		//			   points are output in the postorder sequence.

		int height(nodeType<elemType> *p);
		//Function to determine the height of the binary tree
		//to which p points. 
		//Postcondition: The height of the binary tree to which p
		//			   points is returned.

		int max(int x, int y);
		//Function to determine the larger of x and y.
		//Postcondition: The larger of x and y is returned.

		int nodeCount(nodeType<elemType> *p);
		//Function to determine the number of nodes in the binary 
		//tree to which p points. 
		//Postcondition: The number of nodes in the binary tree
		//			   to which p points is returned.

		int leavesCount(nodeType<elemType> *p);
		//Function to determine the number of leaves in the binary 
		//tree to which p points.
		//Postcondition: The number of nodes in the binary tree
		//			   to which p points is returned.
	};

//Definition of member functions

template<class elemType>
nodeType<elemType> * binaryTreetype<elemType>::binaryTreeType()
	{
	return root;
	}

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
	{
	root = NULL;
	}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
	{
	return (root == NULL);
	}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
	{
	inorder(root);
	}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
	{
	preorder(root);
	}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
	{
	postorder(root);
	}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
	{
	return height(root);
	}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
	{
	return nodeCount(root);
	}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
	{
	return leavesCount(root);
	}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
 nodeType<elemType>* otherTreeRoot)
	{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
		{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
		}
	} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
	{
	if(p != NULL)
		{
		inorder(p->llink);
		cout<<p->info<<" ";
		inorder(p->rlink);
		}
	}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
	{
	if(p != NULL)
		{
		cout<<p->info<<" ";
		preorder(p->llink);
		preorder(p->rlink);
		}
	}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
	{
	if(p != NULL)
		{
		postorder(p->llink);
		postorder(p->rlink);
		cout<<p->info<<" ";
		}		
	}

//Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
	{ 

	if(this != &otherTree) //avoid self-copy
		{
		if(root != NULL)  //if the binary tree is not empty, 
			//destroy the binary tree
			destroy(root);

		if(otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
		}//end else

	return *this; 
	}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
	{
	if(p != NULL)
		{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
		}
	}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
	{
	destroy(root);
	}

//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
	{
	if(otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
	}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
	{
	destroy(root);
	}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
	{
	if(p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
	}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
	{
	if(x >= y)
		return x;
	else
		return y;
	}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
	{
	cout<<"Write the definition of the function nodeCount"
		<<endl;

	return 0;
	}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p, int)
	{

	// make sure node exists
	if (p != NULL)
		{
		// if node is a leaf
		if (p->llink =  NULL && p->rlink == NULL)
			{
			return 1;
			}

		else
			{
			return leavesCount(p->llink) + leavesCount(p->rlink);
			}
		}

	else
		{
		return 0;
		}
	}
}
#endif

[AlexH]

Can anyone please help?

[KYA]

Hmm, I didn't notice earlier. Root is part of your base class, why not try to add getRoot to it instead of your derived class?


(Sorry if I'm not being helpful, i can't run your program without having your stdafx.h)

edited for a typo

This post has been edited by KYA: 24 November 2008 - 04:59 PM

[AlexH]

KYA, on 24 Nov, 2008 - 03:47 PM, said:

Hmm, I didn't notice earlier. Root is part of your base class, why not try to add getRoot to it instead of your derived class?


(Sorry if I'm not being helpful, i can't run your program without having your stdafx.h)

edited for a typo

You are being very helpful. I added getRoot to the base class but it still doesn't want to work. Since you asked for the stdafx.h file, I'm attaching all of my code. Can you please try running it? I appreciate all the help.

Here's the code posted for everyone to see.

main function

// DS Week 3 Page 716 Exerercise 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "binaryTree.h"
#include "binarySearchTree.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
	bSearchTreeType<int> * bstt = new bSearchTreeType<int>();

	int i = 0;
	bool keepGoing = true;
	
	cout << "We are going to build a binary tree now." << endl;

	while(keepGoing)
	{
		
		cout << "Please enter a number." << endl;
		cin >> i;
		cout << "you entered " << i << endl;
		bstt->insert(i);
		cout << "Do you want to continue?  Enter 1 for yes and 0 for no." << endl;
		cin >> keepGoing;

	}

	//cout << "height: " << bstt->treeHeight() << endl;
	cout << "number of leaves: " << bstt->leavesCount(bstt->getRoot()) << endl;

}

binaryTreetype class

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

	 //Definition of the node
template<class elemType>
struct nodeType
{
   elemType			   info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

	//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
	const binaryTreeType<elemType>& operator=
				 (const binaryTreeType<elemType>&); 
	  //Overload the assignment operator.
	bool isEmpty();
	  //Function to determine if the binary tree is empty.
	  //Postcondition: Returns true if the binary tree is empty;
	  //			   otherwise, returns false.
	void inorderTraversal();
	  //Function to do an inorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the inorder sequence.
	void preorderTraversal();
	  //Function to do a preorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the preorder sequence.
	void postorderTraversal();
	  //Function to do a postorder traversal of the binary tree.
	  //Postcondition: The nodes of the binary tree are output
	  //			   in the postorder sequence.

	int treeHeight();
	  //Function to deteremine the height of the binary tree.
	  //Postcondition: The height of the binary tree is returned.
	int treeNodeCount();
	  //Function to determine the number of nodes in the 
	  //binary tree.
	  //Postcondition: The number of nodes in the binary tree
	  //			   is returned.
	int treeLeavesCount();
	  //Function to determine the number of leaves in the 
	  //binary tree.
	  //Postcondition: The number of leaves in the binary tree
	  //			   is returned.
	void destroyTree();
	  //Deallocates the memory space occupied by the binary tree.
	  //Postcondition: root = NULL;

	binaryTreeType(const binaryTreeType<elemType>& otherTree); 
	  //copy constructor

	binaryTreeType();   
	  //default constructor

	~binaryTreeType();   
	  //destructor

	int leavesCount(nodeType<elemType> *p);
	  //Function to determine the number of leaves in the binary 
	  //tree to which p points.
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.

	nodeType<elemType> * getRoot();
	// returns the root node of the tree

protected:
	nodeType<elemType> *root;

private:
	void copyTree(nodeType<elemType>* &copiedTreeRoot,
				  nodeType<elemType>* otherTreeRoot);
	  //Function to make a copy of the binary tree to 
	  //which otherTreeRoot points. 
	  //Postcondition: The pointer copiedTreeRoot points to
	  //			   the root of the copied binary tree.

	void destroy(nodeType<elemType>* &p);
	  //Function to destroy the binary tree to which p points. 
	  //Postcondition: The nodes of the binary tree to which
	  //			   p points are deallocated.
	  //			   p = NULL.

	void inorder(nodeType<elemType> *p);
	  //Function to do an inorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the inorder sequence.
	void preorder(nodeType<elemType> *p);
	  //Function to do a preorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the preorder sequence.
	void postorder(nodeType<elemType> *p);
	  //Function to do a postorder traversal of the binary
	  //tree to which p points.  
	  //Postcondition: The nodes of the binary tree to which p
	  //			   points are output in the postorder sequence.

	int height(nodeType<elemType> *p);
	  //Function to determine the height of the binary tree
	  //to which p points. 
	  //Postcondition: The height of the binary tree to which p
	  //			   points is returned.

	int max(int x, int y);
	  //Function to determine the larger of x and y.
	  //Postcondition: The larger of x and y is returned.

	int nodeCount(nodeType<elemType> *p);
	  //Function to determine the number of nodes in the binary 
	  //tree to which p points. 
	  //Postcondition: The number of nodes in the binary tree
	  //			   to which p points is returned.

	
};

	//Definition of member functions

template<class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
}

template<class elemType>
bool binaryTreeType<elemType>::isEmpty()
{
	return (root == NULL);
}

template<class elemType>
void binaryTreeType<elemType>::inorderTraversal()
{
	inorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::preorderTraversal()
{
	preorder(root);
}

template<class elemType>
void binaryTreeType<elemType>::postorderTraversal()
{
	postorder(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeHeight()
{
	return height(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeNodeCount()
{
	return nodeCount(root);
}

template<class elemType>
int binaryTreeType<elemType>::treeLeavesCount()
{
	return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
					  (nodeType<elemType>* &copiedTreeRoot,
					   nodeType<elemType>* otherTreeRoot)
{
	if(otherTreeRoot == NULL)
		copiedTreeRoot = NULL;
	else
	{
		copiedTreeRoot = new nodeType<elemType>;
		copiedTreeRoot->info = otherTreeRoot->info;
		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
	}
} //end copyTree

template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		inorder(p->llink);
		cout<<p->info<<" ";
		inorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::preorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		cout<<p->info<<" ";
		preorder(p->llink);
		preorder(p->rlink);
	}
}

template<class elemType>
void binaryTreeType<elemType>::postorder(nodeType<elemType> *p)
{
	if(p != NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout<<p->info<<" ";
	}		
}

   //Overload the assignment operator
template<class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
		   operator=(const binaryTreeType<elemType>& otherTree)
{ 
	 
	if(this != &otherTree) //avoid self-copy
	{
		if(root != NULL)  //if the binary tree is not empty, 
						  //destroy the binary tree
			destroy(root);

		if(otherTree.root == NULL) //otherTree is empty
			root = NULL;
		else
			copyTree(root, otherTree.root);
	}//end else

   return *this; 
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
	if(p != NULL)
	{
		destroy(p->llink);
		destroy(p->rlink);
		delete p;
		p = NULL;
	}
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
	destroy(root);
}

	//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
			  (const binaryTreeType<elemType>& otherTree)
{
	if(otherTree.root == NULL) //otherTree is empty
		root = NULL;
	else
		copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
	destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height(nodeType<elemType> *p)
{
	if(p == NULL)
		return 0;
	else
		return 1 + max(height(p->llink), height(p->rlink));
}

template<class elemType>
int binaryTreeType<elemType>::max(int x, int y)
{
	if(x >= y)
		return x;
	else
		return y;
}

template<class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p)
{
	cout<<"Write the definition of the function nodeCount"
		<<endl;

	return 0;
}

template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
 {

	// make sure node exists
	if (p != NULL)
		{
		// if node is a leaf
		if (p->llink =  NULL && p->rlink == NULL)
			{
			return 1;
			}

		// not a leaf, return how many leaves the children have
		else
			{
			return leavesCount(p->llink) + leavesCount(p->rlink);
			}
		}

	else
		{
		return 0;
		}
	}
	

template<class elemType>
nodeType<elemType> * binaryTreeType<elemType>::getRoot()
	{
		return root;
	}

#endif

bSearchTreeType class

//Header File Binary Search Tree

#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"

using namespace std;

template<class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
	bool search(const elemType& searchItem);
	  //Function to determine if searchItem is in the binary 
	  //search tree.
	  //Postcondition: Returns true if searchItem is found in the 
	  //			 binary search tree; otherwise, returns false.

	void insert(const elemType& insertItem);
	  //Function to insert insertItem in the binary search tree.
	  //Postcondition: If no node in the binary search tree has 
	  //		   the same info as insertItem, a node with the 
	  //		   info insertItem is created and inserted in the
	  //binary search tree.

	void deleteNode(const elemType& deleteItem);
	  //Function to delete deleteItem from the binary search tree 
	  //Postcondition: If a node with the same info as deleteItem 
	  //			   is found, it is deleted from the binary 
	  //			   search tree.

private:
	void deleteFromTree(nodeType<elemType>* &p);
	  //Function to delete the node, to which p points, from the 
	  //binary search tree.
	  //Postcondition: The node to which p points is deleted
	  //			   from the binary search tree.

	void swapSubTrees(nodeType<elemType> * p);
	// Function to swap all of the left and right subtrees in a BST.
};


template<class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem)
{
	nodeType<elemType> *current;
	bool found = false;

	if(root == NULL)
	   cerr<<"Cannot search the empty tree."<<endl;
	else
	{ 
	   current = root;

	   while(current != NULL && !found)
	   {
			 if(current->info == searchItem)
				found = true;
			  else
				  if(current->info > searchItem)
					 current = current->llink;
				  else
					 current = current->rlink;
	   }//end while
	}//end else

	return found;
}//end search

template<class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	nodeType<elemType> *newNode;  //pointer to create the node

	newNode = new nodeType<elemType>;
	assert(newNode != NULL);
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if(root == NULL)
	   root = newNode;
	else
	{
	   current = root;
 
	   while(current != NULL)
	   {
		   trailCurrent = current;

		   if(current->info == insertItem)
		   {
			  cerr<<"The insert item is already in the list -- ";
			  cerr<<"duplicates are not allowed."<<endl;
			  return;
		   }
		   else
			  if(current->info > insertItem)
				 current = current->llink;
			  else
				 current = current->rlink;
	   }//end while

	   if(trailCurrent->info > insertItem)
		  trailCurrent->llink = newNode;
	   else
		  trailCurrent->rlink = newNode;
   }
}//end insert



template<class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
	nodeType<elemType> *current;  //pointer to traverse the tree
	nodeType<elemType> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		cerr<<"Cannot delete from the empty tree."<<endl;
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(current->info == deleteItem)
				found = true;
			else
			{
				trailCurrent = current;

				if(current->info > deleteItem)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
			cout<<"The delete item is not in the tree."<<endl;
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root);
				else
					if(trailCurrent->info > deleteItem)
						deleteFromTree(trailCurrent->llink);
					else
						deleteFromTree(trailCurrent->rlink);
			}//end if
	}
}//end deleteNode

template<class elemType>
void bSearchTreeType<elemType>::deleteFromTree
								 (nodeType<elemType>* &p)
{
	 nodeType<elemType> *current;	//pointer to traverse 
									 //the tree
	 nodeType<elemType> *trailCurrent;   //pointer behind current
	 nodeType<elemType> *temp;		//pointer to delete the node

	 if(p == NULL)
		cerr<<"Error: The node to be deleted is NULL."
			<<endl;
	 else if(p->llink == NULL && p->rlink == NULL)
		  {
			 temp = p;
			 p = NULL;
			 delete temp;
		  }
	 else if(p->llink == NULL)
		  {
			 temp = p;
			 p = temp->rlink;
			 delete temp;
		  }
	 else if(p->rlink == NULL)
		  {
			 temp = p;
			 p = temp->llink;
			 delete temp;
		  }
	 else
	 {
		current = p->llink;
		trailCurrent = NULL;

		while(current->rlink != NULL)
		{
			trailCurrent = current;
			current = current->rlink;
		}//end while

		p->info = current->info;

		if(trailCurrent == NULL) //current did not move; 
								 //current == p->llink; adjust p
		   p->llink = current->llink;
		else
		   trailCurrent->rlink = current->llink;
 
		delete current;
	 }//end else
}//end deleteFromTree

template<class elemtype>
void swapSubTrees(nodeType<elemType> * p)
	{
		while(p != NULL)
			{

			if (p->llink != NULL & p->rlink != NULL)
				{
				// swap p->llink and p->rlink
				nodeType<elemType> * temp = p->llink
					p->llink = p->rlink
					p->rlink = temp
				delete temp;
				}
			
			else
				{
				cout << "node doesn't have 2 children" << endl;

				}
			p = p->llink;
			}
		return;

	}



#endif

stdafx.h

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//

#pragma once


#define WIN32_LEAN_AND_MEAN		// Exclude rarely-used stuff from Windows headers
#include <stdio.h>
#include <tchar.h>



// TODO: reference additional headers your program requires here

stdafx.cpp

// stdafx.cpp : source file that includes just the standard includes
// DS Week 3 Page 716 Exerercise 2.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

// TODO: reference any additional headers you need in STDAFX.H
// and not in this file

Attached File(s)

•  DS_Week_3_Page_716_Exerercise_2.zip (4.05K)
  Number of downloads: 44

[AlexH]

Are you there KYA? I appreciate any help.

[KYA]

I'm having some compilation issues on my machine. Where is template<class elemType> defined? Is it explicit?

[perfectly.insane]

In your getRoot() function, you might want to try referring to root in it's fully qualified form:

return binaryTreeType<elemType>::root;

(as opposed to "return root;")

[AlexH]

KYA, on 24 Nov, 2008 - 05:48 PM, said:

I'm having some compilation issues on my machine. Where is template<class elemType> defined? Is it explicit?

It isn't defined anywhere because it's part of C++. It lets you use any data type in whatever container you are using.

I got it to work. My instructor told me via email that the easiest way to make it work was to have the main method call a public method calls my private method that calculates the number of leaves.

Thank you very much for your help!

[KYA]

Oh i see. I thought it was a user defined template. Glad you got it to work.