8 Replies - 2069 Views - Last Post: 04 November 2008 - 03:49 PM Rate Topic: -----

#1 yofat04  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 17-July 08

Binary Search Tree compile errors

Posted 03 November 2008 - 07:19 PM

I am writing a Binary Search Tree class which is derived from a Binary Tree class i wrote for a the last assignment. My ta worked with me to get rid of a few of my errors but then left me on my own because he wanted to goto lunch. I have been staring at my code and reading through my book for hrs to figure out where these errors are coming from. Any help would be greatly appreciated.

My errors:


BST.h: In member function ‚void BST<T>::remove(Node<T>*&, const T&)‚:
BST.h:99: error: expected primary-expression before ‚else‚
BST.h:99: error: expected `;' before ‚else‚
BST.h:103: error: expected primary-expression before ‚else‚
BST.h:103: error: expected `;' before ‚else‚
BST.h:114: error: expected primary-expression before ‚template‚
BST.h:114: error: expected `;' before ‚template‚



The lines that are giving me errors from my Binary Search Tree header file:
#ifndef BST_H
#define BST_H

#include "/home/turing/onyuksel/courses/340/common/340.h"
#include "BT.h"

template <class T>
class BST: public BT<T>
{
public:
	  void insert(const T& x){return insert(BT<T>::root, x);}
	  void remove(const T& x){return remove(this->root,x);}
	  bool search(const T& x, int& len)const {return search(this->root,len);}
private:
	  void insert(Node<T>*&, const T&);
	  void remove(Node<T>*&, const T&);
	   bool search(Node<T>*&, const T&) const;
};

template <class T>
void BST<T>::insert(Node<T>*& node, const T& newItem)
{
 if (!node) //checks if tree is empty
		{
		node= new Node<T>(newItem);//creates new Node
		}
 else
		{
		if (newItem < node->data)
				{
				insert(node->left,newItem);
				}
		else if (newItem > node->data)
				{
				insert(node->right,newItem);
				}
		else if (newItem== node->data)
				{}
		}
}



template <class T>
void BST<T>::remove(Node<T>*& ptr, const T& deleteValue)
{
ptr= this->root;
Node<T>* parentPtr= NULL;
Node<T>* subtreePtr= NULL;
Node<T>* ptrPred= NULL;
bool found= false;

while (!ptr==NULL && !found)
		{
		if(deleteValue < ptr->data)
				{
				parentPtr= ptr;
				ptr= ptr->left;
				}
		else if (deleteValue > ptr->data)
				{
				parentPtr= ptr;
				ptr= ptr->right;
				}
		else
				{
				found = true;
				}
		}

if (found== true)
		{}

else
		{
		if (ptr->left && ptr->right)		   // case 3
				{
				ptrPred= ptr->left;
				parentPtr= ptr;
				while(ptrPred->right)
						{
						parentPtr= ptrPred;
						ptrPred= ptrPred->right;
						}

				ptr->data= ptrPred->data;//node to delete now has pred. value
				ptr= ptrPred;
				}
/* below this -- case 1 and 2 are combined */

		subtreePtr= ptr->left;

		if (subtreePtr==NULL)
				{
				subtreePtr= ptr->right;
				}
		if (parentPtr==NULL)			  //tree consists of root only
				{
				this->root= subtreePtr;
				{
Line 99	  else if(parentPtr->left== ptr)	//if left child is being deleted
				{
				parentPtr->left= subtreePtr;	//then subtree is new left child
				}
Line 103	else							  //right child is being deleted
				{
				parentPtr->right= subtreePtr;   //new right child is subtree
				}
		delete ptr;
		}
}


}

template <class T>   //Line 114
bool BST<T>::search(Node<T>*& node, int &len) const
{
if (!node)
		{
		return false;
		}
if (item < node->data)
		{
//	  len++;
		search(node->left, item);
		}
else if(item > node->data)
		{
		len++;
		search(node->right, item);
		}
else if (item == node->data)
		{
		len++;
		return true;
		}
else
		{
		len++;
		return false;
		}
}




#endif



Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree compile errors

#2 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 07:27 PM

You forgot to paste the last brace in your code. Once I added stubs for the BT and the Node class, I didn't get any errors.

Salindor
Was This Post Helpful? 0
  • +
  • -

#3 yofat04  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 17-July 08

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 08:05 PM

View Postsalindor, on 3 Nov, 2008 - 06:27 PM, said:

You forgot to paste the last brace in your code. Once I added stubs for the BT and the Node class, I didn't get any errors.

Salindor



Where exactly am i missing braces in my code?
I just used quincy to locate missing braces, tried to fix it, and got even more compile errors
Was This Post Helpful? 0
  • +
  • -

#4 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 08:12 PM

just before the #endif.

Just for giggles, here is what I did to get it to compile on my computer:


#ifndef BST_H
#define BST_H

//#include "/home/turing/onyuksel/courses/340/common/340.h"
//#include "BT.h"
template <class T>
class BT
{
};

template <class T>
class Node
{
};

template <class T>
class BST: public BT<T>
{
public:
	void insert(const T& x){return insert(BT<T>::root, x);}
	void remove(const T& x){return remove(this->root,x);}
	bool search(const T& x, int& len)const {return search(this->root,len);}
private:
	void insert(Node<T>*&, const T&);
	void remove(Node<T>*&, const T&);
	bool search(Node<T>*&, const T&) const;
};

template <class T>
void BST<T>::insert(Node<T>*& node, const T& newItem)
{
	if (!node) //checks if tree is empty
	{
		node= new Node<T>(newItem);//creates new Node
	}
	else
	{
		if (newItem < node->data)
		{
			insert(node->left,newItem);
		}
		else if (newItem > node->data)
		{
			insert(node->right,newItem);
		}
		else if (newItem== node->data)
		{}
	}
}



template <class T>
void BST<T>::remove(Node<T>*& ptr, const T& deleteValue)
{
	ptr= this->root;
	Node<T>* parentPtr= NULL;
	Node<T>* subtreePtr= NULL;
	Node<T>* ptrPred= NULL;
	bool found= false;

	while (!ptr==NULL && !found)
	{
		if(deleteValue < ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->left;
		}
		else if (deleteValue > ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->right;
		}
		else
		{
			found = true;
		}
	}

	if (found== true)
	{}

	else
	{
		if (ptr->left && ptr->right)           // case 3
		{
			ptrPred= ptr->left;
			parentPtr= ptr;
			while(ptrPred->right)
			{
				parentPtr= ptrPred;
				ptrPred= ptrPred->right;
			}

			ptr->data= ptrPred->data;//node to delete now has pred. value
			ptr= ptrPred;
		}
		/* below this -- case 1 and 2 are combined */

		subtreePtr= ptr->left;

		if (subtreePtr==NULL)
		{
			subtreePtr= ptr->right;
		}
		if (parentPtr==NULL)              //tree consists of root only
		{
			this->root= subtreePtr;
			{
				Line 99      else if(parentPtr->left== ptr)    //if left child is being deleted
				{
					parentPtr->left= subtreePtr;    //then subtree is new left child
				}
				Line 103    else                              //right child is being deleted
				{
					parentPtr->right= subtreePtr;   //new right child is subtree
				}
				delete ptr;
			}
		}


	}

	template <class T>   //Line 114
	bool BST<T>::search(Node<T>*& node, int &len) const
	{
		if (!node)
		{
			return false;
		}
		if (item < node->data)
		{
			//      len++;
			search(node->left, item);
		}
		else if(item > node->data)
		{
			len++;
			search(node->right, item);
		}
		else if (item == node->data)
		{
			len++;
			return true;
		}
		else
		{
			len++;
			return false;
		}
	}
}

void main()
{
	BST<int> t;
}

#endif



Please keep in mind, I didn't put your code in a .h file; I instead pasted right into my test.cpp file. Because of this, I had to add a main function for the linker.
Was This Post Helpful? 0
  • +
  • -

#5 yofat04  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 17-July 08

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 08:22 PM

View Postsalindor, on 3 Nov, 2008 - 07:12 PM, said:

just before the #endif.

Just for giggles, here is what I did to get it to compile on my computer:


#ifndef BST_H
#define BST_H

//#include "/home/turing/onyuksel/courses/340/common/340.h"
//#include "BT.h"
template <class T>
class BT
{
};

template <class T>
class Node
{
};

template <class T>
class BST: public BT<T>
{
public:
	void insert(const T& x){return insert(BT<T>::root, x);}
	void remove(const T& x){return remove(this->root,x);}
	bool search(const T& x, int& len)const {return search(this->root,len);}
private:
	void insert(Node<T>*&, const T&);
	void remove(Node<T>*&, const T&);
	bool search(Node<T>*&, const T&) const;
};

template <class T>
void BST<T>::insert(Node<T>*& node, const T& newItem)
{
	if (!node) //checks if tree is empty
	{
		node= new Node<T>(newItem);//creates new Node
	}
	else
	{
		if (newItem < node->data)
		{
			insert(node->left,newItem);
		}
		else if (newItem > node->data)
		{
			insert(node->right,newItem);
		}
		else if (newItem== node->data)
		{}
	}
}



template <class T>
void BST<T>::remove(Node<T>*& ptr, const T& deleteValue)
{
	ptr= this->root;
	Node<T>* parentPtr= NULL;
	Node<T>* subtreePtr= NULL;
	Node<T>* ptrPred= NULL;
	bool found= false;

	while (!ptr==NULL && !found)
	{
		if(deleteValue < ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->left;
		}
		else if (deleteValue > ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->right;
		}
		else
		{
			found = true;
		}
	}

	if (found== true)
	{}

	else
	{
		if (ptr->left && ptr->right)           // case 3
		{
			ptrPred= ptr->left;
			parentPtr= ptr;
			while(ptrPred->right)
			{
				parentPtr= ptrPred;
				ptrPred= ptrPred->right;
			}

			ptr->data= ptrPred->data;//node to delete now has pred. value
			ptr= ptrPred;
		}
		/* below this -- case 1 and 2 are combined */

		subtreePtr= ptr->left;

		if (subtreePtr==NULL)
		{
			subtreePtr= ptr->right;
		}
		if (parentPtr==NULL)              //tree consists of root only
		{
			this->root= subtreePtr;
			{
				Line 99      else if(parentPtr->left== ptr)    //if left child is being deleted
				{
					parentPtr->left= subtreePtr;    //then subtree is new left child
				}
				Line 103    else                              //right child is being deleted
				{
					parentPtr->right= subtreePtr;   //new right child is subtree
				}
				delete ptr;
			}
		}


	}

	template <class T>   //Line 114
	bool BST<T>::search(Node<T>*& node, int &len) const
	{
		if (!node)
		{
			return false;
		}
		if (item < node->data)
		{
			//      len++;
			search(node->left, item);
		}
		else if(item > node->data)
		{
			len++;
			search(node->right, item);
		}
		else if (item == node->data)
		{
			len++;
			return true;
		}
		else
		{
			len++;
			return false;
		}
	}
}

void main()
{
	BST<int> t;
}

#endif



Please keep in mind, I didn't put your code in a .h file; I instead pasted right into my test.cpp file. Because of this, I had to add a main function for the linker.



I added the closing brace just before the #endif and it gave me even more compile errors with my main function on top of the original errors I had with my BST class that didnt go away.
Sorry i should have posted this before hand
#include "/home/turing/onyuksel/courses/340/common/340.h"
#include "BST.h"

using namespace std;


//Function Prototypes
void print_data(BST<T>&);
const int randrng= 1000;
static int cnt= 0;

int main()
{
static int len= 0;
int n, s1=1;
int successfulSch=0,totalSearches=0,totSearchPath=0,totalSearches=0;

vector<int> v(n);
BST<int> t;
bool found;


cout<<"How many random intergers: "<<endl;
cin>>n;

srand(s1);				//initiate random number generator w/ s1 seed value

//for loop uses rand to generate integer in range of 0 & N
//Inserts into vector v and
for (int i =0; i <n; i++)
		{
		v.push_back(rand()% randrng);
		}

//inserts random numbers into binary search tree t
srand(s1);
for (int i =0; i <n; i++)
		{
		t.insert(rand()% randrng);
		}

//searches vector and binary search tree f
for (i=0; i<t; i++)
		{
		found= t.search(v[i], len);
		totSearchPath+= len;
		totalSearches++;
		if(found)
				{
				successfulSch++;
				}
		}

cout<<"Number of nodes: "<<t.size()<<endl;
cout<<"Number of leaves: "<<t.leaves()<<endl;
cout<<"Height of the tree: "<<t.height()<<endl;
cout<<"Ratio of successful searches: ";
cout<<(double)successfulSch/totalSearches * 100<<endl;
cout<<"Average search length: "<<totSearchPath/totalSearches<<endl;

//prints data in binary search tree
t.inorder(print_data);

successfulSch=0;
totalSearches=0;
totSearchPath=0;
totalSearches=0;

//seive
//For loop scans the entire set s and removes all multiples of m until
//upper limit n is reached
for (int m= 2; m * m <= n; m++)
		for(int k= 2; k * m <= n; k++)
				{
				found= t.search(k *m, len);
				if (found)
						{
						t.remove(k*m);
						}
				}

cout<<"Number of nodes: "<<t.size()<<endl;
cout<<"Number of leaves: "<<t.leaves()<<endl;
cout<<"Height of the tree: "<<t.height()<<endl;
cout<<"Ratio of successful searches: ";
cout<<(double)successfulSch/totalSearches * 100<<endl;
cout<<"Average search length: "<<(double)totSearchPath/totalSearches<<endl;

t.inorder(print_data);

return 0;
}


void print_data(BST<T>& t)
{
if (cnt++ >= 16)
		{
		cout<<endl;
		}
cout<<t<<" ";
}



Was This Post Helpful? 0
  • +
  • -

#6 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 08:38 PM

That is because the new code you posted has errors in it :P

on the function print_data, I think you meant it to be a template class, so you need to declare it as so.

I don't know what is contained within the class BT; but the classes you have given me don't have a rule to compare an int with a class BST. Did you mean to have a size operator and compare i with the size of BST? I am sorry I can't debug this further.

You never included <vector> or <iostream>

I don't know if there are more errors, as I can not continue parsing it with the information you have provided.

Salindor
Was This Post Helpful? 0
  • +
  • -

#7 yofat04  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 17-July 08

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 09:00 PM

View Postsalindor, on 3 Nov, 2008 - 07:38 PM, said:

That is because the new code you posted has errors in it :P

on the function print_data, I think you meant it to be a template class, so you need to declare it as so.

I don't know what is contained within the class BT; but the classes you have given me don't have a rule to compare an int with a class BST. Did you mean to have a size operator and compare i with the size of BST? I am sorry I can't debug this further.

You never included <vector> or <iostream>

I don't know if there are more errors, as I can not continue parsing it with the information you have provided.

Salindor




In the #include....340.h within my header guards is all the #includes i would need. I would have myself but i guess the course coordinator for this class didn't want us to have our own in our files while he's grading them.

I'm working through my prog5.cc file to find anymore errors

Here is what's in my BT.h
#ifndef BT_H  //start header guards
#define BT_H

#include "/home/turing/onyuksel/courses/340/common/340.h"
#include "Node.h"

template <class T>

//Class Definition
class BT
{
public:
	BT() {root= 0;}   //constructor									  
	BT(const BT<T>&);  //copy constructor									   
	BT& operator=(const BT<T>&);  //assignment operator						  
	virtual ~BT() {clear();}	  //destructor						  
 
	bool empty()const {return root == 0;} //checks if tree empty				   
	int size()const {return size(root);}  //find no of nodes				  
	int height()const {return height(root);} //finds height of tree			  
	int leaves()const {return leaves(root);}  //finds no of leaves			  
	virtual void insert(const T& x) {insert(root, x);} //inserts into subtree	
	void clear() {clear(root); root= 0;}  //destroys binary tree				

	//tree traversal functions
	void preOrder(void (*p)(T&)) { preOrder(root, p);}//preoder transversal
 	void inOrder(void (*p)(T&)) { inOrder(root, p);} //inorder transversal
	void postOrder(void (*p)(T&)) { postOrder(root, p);} //postorder transversal
  
protected:
	Node<T>*root;   //root of binary tree							 
  
private:
	int size(Node<T>*)const;	   //finds no of nodes			
	int height(Node<T>*)const;	//finds height of tree	   
	int leaves(Node<T>*)const;	//finds no of leaves			
	void insert(Node<T>*&, const T&); //inserts into subtree
	void clear(Node<T>*);
   
	void inOrder(Node<T>*, void (*)(T&));	 //inorder transversal
	void preOrder(Node<T>*, void (*)(T&));	//preoder transversal
	void postOrder(Node<T>*, void (*)(T&));   //postorder transversal
   
	Node<T>* copy(const Node<T>*);	 //copy constructor	   
};


//BT Class implementations


/******************************************************************************
FUNCTION:  Copy Constructor

ARGUMENTS: BT object Tree

RETURNS:   Nothing

NOTES:	 Copy constructor copies a binary tree

******************************************************************************/

template <class T>
BT<T>::BT(const BT<T>& Tree)
{
root = copy(Tree.root);
}



/******************************************************************************
FUNCTION:  Assignment Operator

ARGUMENTS: BT object Tree

RETURNS:   A new BT object

NOTES:	Copies a binary tree

******************************************************************************/

template <class T>
BT<T>& BT<T>::operator=(const BT<T>& Tree)
{
if(this != &Tree)
	{
	clear();
	root = copy(Tree.root);
	}

return *this;
}




/******************************************************************************
FUNCTION:  size(Node<T>* Node)const

ARGUMENTS: node

RETURNS:   no of nodes

NOTES:	 None

******************************************************************************/

template <class T>
int BT<T>::size(Node<T>* node)const
{
if(!node)   //while node is true
	{return 0;} //exits function
else 
	{ 
	//finds and returns no nodes
	int left= size(node->left);
	int right= size(node->right);
	return 1 + left +right;
	}
}



/******************************************************************************
FUNCTION:  height(Node<T>* Node)const

ARGUMENTS: node

RETURNS:   height of tree

NOTES:	 None

******************************************************************************/

template <class T>
int BT<T>::height(Node<T>* node)const
{
if(!node) //while node is true
	{return 0;}  //exits function
else
	{
	int right= height(node->right);
	int left= height(node->left);


	if (left >= right) 
		{return left +1;}
	else return right +1; 		  
   	}
}



/******************************************************************************
FUNCTION:  leaves(Node<T>* Node)const

ARGUMENTS: node

RETURNS:   no of leaves

NOTES:	 None

******************************************************************************/

template <class T>
int BT<T>::leaves(Node<T>* node)const
 {
if(!node) //while node is true
	{return 0;}  //exits function
else if (!node->left && !node->right)  
	{return 1;}   //returns if there are no children
else
	{ 
	//adds leaves in left and right of tree and returns number
	return leaves(node->left) + leaves(node->right);  
	}
}




/******************************************************************************
FUNCTION:  insert(Node<T>* Node)const

ARGUMENTS: node, new item to be inserted

RETURNS:   Nothing

NOTES:	 Inserts new item into binary tree once it checks if tree is empty

******************************************************************************/

template <class T>
void BT<T>::insert(Node<T>*& node, const T& newItem)
{
 if (!node) //checks if tree is empty
	{
	node = new Node<T>(newItem);//creates new Node
	}
 else 
	{
	 //inserts item into shortest subtree
 	if (height(node->left) <= height(node->right) )
		{
		//inserts into left of subtree
		insert(node->left, newItem);
		}
 	else 
		{
		//inserts into right of subtree
		insert(node->right, newItem);
		}
 	}
}



/******************************************************************************
FUNCTION:  clear(Node<T>* Node)const

ARGUMENTS: node

RETURNS:   Nothing

NOTES:	 Destroys tree

******************************************************************************/

template <class T>
void BT<T>::clear(Node<T>* node)
{
if (node) //if node is true
	{
	clear(node->left); //deletes left of subtree 
	clear(node->right); //deletes right of subtree
	

	delete node;  
	}
}





/******************************************************************************
FUNCTION:  inOrder(Node<T>* node, void (*f)(T&))

ARGUMENTS: node, function pointer, argument to pointer

RETURNS:   Nothing

NOTES:	 Transverses through binary tree using inorder logic

******************************************************************************/

template <class T>
void BT<T>::inOrder(Node<T>* node, void (*f)(T&))
{
if(node)  //if node is true
	{
	inOrder(node->left, f);  
	f(node->data); 
	inOrder(node->right, f);
   	}
}








/******************************************************************************
FUNCTION:  preOrder(Node<T>* node, void (*f)(T&))

ARGUMENTS: node, function pointer, argument to pointer

RETURNS:   Nothing

NOTES:	 Transverses through binary tree using preoder logic

******************************************************************************/

template <class T>
void BT<T>::preOrder(Node<T>* node, void(*f)(T&)) 
{
if(node)  //if node is true
	{
   	f(node->data);
		preOrder(node->left, f);
		preOrder(node->right, f);
   	}
}





/******************************************************************************
FUNCTION:  postOrder(Node<T>* node, void (*f)(T&))

ARGUMENTS: node, function pointer, argument to pointer

RETURNS:   Nothing

NOTES:	 Transverses through binary tree using postorder logic


******************************************************************************/

template <class T>
void BT<T>::postOrder(Node<T>* node, void (*f)(T&))
{
if(node)   //if node is true
	{
		postOrder(node->left, f);
		postOrder(node->right, f);
		f(node->data);
   	}
}





/******************************************************************************
FUNCTION:  copy(const Node<T>* node)

ARGUMENTS: node

RETURNS:   New node

NOTES:	Copies one BT object to another new BT object


******************************************************************************/

template <class T>
Node<T>* BT<T>::copy(const Node<T>* node)
{
if(!node)  //if tree is empty
	{return 0;}   //exits function
else
	{
	//creates new BT object
		Node<T>* Node2 = new Node<T>(node->data); 
	
		Node2->left = copy(node->left); //copies left of subtree
		Node2->right = copy(node->right);  //copies right of subtree
		return Node2;  //returns new BT object
   	}
}


#endif   //end header guards




This is whats in my Node.h file
*****************************************************************************/

#include "/home/turing/onyuksel/courses/340/common/340.h"

#ifndef H_Node //start header guards
#define H_Node


//Node class definition
template<class T> class BT;
template<class T> class BST;

template<class T> 
class Node
{
//allows access to the private data members of Node<T>
friend class BT<T>;   
friend class BST<T>;

public:
Node(const T& = T(), Node<T>* = 0, Node<T>* = 0); //Node constructor
  
private:
T data;  //variable to store data of various data types
Node<T> *left, *right;  //left & right pointers to children
};




/******************************************************************************
FUNCTION:  Constructor

ARGUMENTS: x variable to store data of various data types, l pointer to left of 
	   subtree, r pointer to right of subtree

RETURNS:   Nothing

NOTES:	

******************************************************************************/

template<class T>
Node<T>::Node(const T& x, Node<T>* l, Node<T>* r):data(x),left(l),right(r)
{ }


#endif  //end header guards






Both of these files compiled correctly and worked properly with the int main() file we used for the previous assignment
Was This Post Helpful? 0
  • +
  • -

#8 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: Binary Search Tree compile errors

Posted 03 November 2008 - 09:40 PM

Ok I was wrong before... templates stink :D . Now that I have the entire program, I gave you some bad advice. Here is what I did to fix.

First thing todo is undo the change I gave you. I forgot the compiler doesn't actually compile templates until you use the function. So while the code I did above compiled, it was still wrong.

In your function remove you put a brace the wrong direction:
template <class T>
void BST<T>::remove(Node<T>*& ptr, const T& deleteValue)
{
	ptr= this->root;
	Node<T>* parentPtr= NULL;
	Node<T>* subtreePtr= NULL;
	Node<T>* ptrPred= NULL;
	bool found= false;

	while (!ptr==NULL && !found)
	{
		if(deleteValue < ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->left;
		}
		else if (deleteValue > ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->right;
		}
		else
		{
			found = true;
		}
	}

	if (found== true)
	{}

	else
	{
		if (ptr->left && ptr->right)           // case 3
		{
			ptrPred= ptr->left;
			parentPtr= ptr;
			while(ptrPred->right)
			{
				parentPtr= ptrPred;
				ptrPred= ptrPred->right;
			}

			ptr->data= ptrPred->data;//node to delete now has pred. value
			ptr= ptrPred;
		}
		/* below this -- case 1 and 2 are combined */

		subtreePtr= ptr->left;

		if (subtreePtr==NULL)
		{
			subtreePtr= ptr->right;
		}
		if (parentPtr==NULL)              //tree consists of root only
		{
			this->root= subtreePtr;
		//	{   // <--------- right here this goes the other way
		}       
		else if(parentPtr->left== ptr)    //if left child is being deleted
		{
			parentPtr->left= subtreePtr;    //then subtree is new left child
		}
		else                              //right child is being deleted
		{
			parentPtr->right= subtreePtr;   //new right child is subtree
		}
		delete ptr;
			}
		}
	}




Next I commented out the internals to the search function
template <class T>   //Line 114
	bool BST<T>::search(const Node<T>* node, int &len) const
	{
		return false;
		/*if (!node)
		{
			return false;
		}
		if (item < node->data)
		{
			//      len++;
			search(node->left, item);
		}
		else if(item > node->data)
		{
			len++;
			search(node->right, item);
		}
		else if (item == node->data)
		{
			len++;
			return true;
		}
		else
		{
			len++;
			return false;
		}*/
	}


Not sure what your trying todo, but there is nothing called item; so I just commented it out for now and return false.

I think I may have deleted a couple more closing braces, so really pay attention and tab all your opening braces and untab all your closing braces. In my software engineering class, they recommended that as soon as you write an open brace, you immediately write a close brace. I am starting to get tired and can't match up where I deleted the braces from, I am sorry. Maybe if your still having problems tomorrow and no one else has offered help, I can try and help then.

in the main function total searches was declared more than once.
in the main function you forgot to declare a new int i in the third for loop. You forgot to compare i with t.size() (at least that is what I think you meant).
in the main function t.inorder( ) does not exist

I think that is everything I did to get it to compile. I did not check to see if it ran.

Salindor

ohh I changed the parameters to search. I made the first parameter const and because it was a pointer I saw no point in passing it by reference snese you can't modify it anyhow. So I removed teh by reference from the node in the search parameter.
Was This Post Helpful? 1
  • +
  • -

#9 yofat04  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 17-July 08

Re: Binary Search Tree compile errors

Posted 04 November 2008 - 03:49 PM

View Postsalindor, on 3 Nov, 2008 - 08:40 PM, said:

Ok I was wrong before... templates stink :D . Now that I have the entire program, I gave you some bad advice. Here is what I did to fix.

First thing todo is undo the change I gave you. I forgot the compiler doesn't actually compile templates until you use the function. So while the code I did above compiled, it was still wrong.

In your function remove you put a brace the wrong direction:
template <class T>
void BST<T>::remove(Node<T>*& ptr, const T& deleteValue)
{
	ptr= this->root;
	Node<T>* parentPtr= NULL;
	Node<T>* subtreePtr= NULL;
	Node<T>* ptrPred= NULL;
	bool found= false;

	while (!ptr==NULL && !found)
	{
		if(deleteValue < ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->left;
		}
		else if (deleteValue > ptr->data)
		{
			parentPtr= ptr;
			ptr= ptr->right;
		}
		else
		{
			found = true;
		}
	}

	if (found== true)
	{}

	else
	{
		if (ptr->left && ptr->right)           // case 3
		{
			ptrPred= ptr->left;
			parentPtr= ptr;
			while(ptrPred->right)
			{
				parentPtr= ptrPred;
				ptrPred= ptrPred->right;
			}

			ptr->data= ptrPred->data;//node to delete now has pred. value
			ptr= ptrPred;
		}
		/* below this -- case 1 and 2 are combined */

		subtreePtr= ptr->left;

		if (subtreePtr==NULL)
		{
			subtreePtr= ptr->right;
		}
		if (parentPtr==NULL)              //tree consists of root only
		{
			this->root= subtreePtr;
		//	{   // <--------- right here this goes the other way
		}       
		else if(parentPtr->left== ptr)    //if left child is being deleted
		{
			parentPtr->left= subtreePtr;    //then subtree is new left child
		}
		else                              //right child is being deleted
		{
			parentPtr->right= subtreePtr;   //new right child is subtree
		}
		delete ptr;
			}
		}
	}




Next I commented out the internals to the search function
template <class T>   //Line 114
	bool BST<T>::search(const Node<T>* node, int &len) const
	{
		return false;
		/*if (!node)
		{
			return false;
		}
		if (item < node->data)
		{
			//      len++;
			search(node->left, item);
		}
		else if(item > node->data)
		{
			len++;
			search(node->right, item);
		}
		else if (item == node->data)
		{
			len++;
			return true;
		}
		else
		{
			len++;
			return false;
		}*/
	}


Not sure what your trying todo, but there is nothing called item; so I just commented it out for now and return false.

I think I may have deleted a couple more closing braces, so really pay attention and tab all your opening braces and untab all your closing braces. In my software engineering class, they recommended that as soon as you write an open brace, you immediately write a close brace. I am starting to get tired and can't match up where I deleted the braces from, I am sorry. Maybe if your still having problems tomorrow and no one else has offered help, I can try and help then.

in the main function total searches was declared more than once.
in the main function you forgot to declare a new int i in the third for loop. You forgot to compare i with t.size() (at least that is what I think you meant).
in the main function t.inorder( ) does not exist

I think that is everything I did to get it to compile. I did not check to see if it ran.

Salindor

ohh I changed the parameters to search. I made the first parameter const and because it was a pointer I saw no point in passing it by reference snese you can't modify it anyhow. So I removed teh by reference from the node in the search parameter.


Thanks I debugged the rest of the file and finally got it working. Most of my errors were pretty easy to fix once i matched all my braces and fixed my search function. Thanks alot for your help
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1