Testing Equality on a BST

[evilsweeps]

Hi,
this is my first post on here so forgive me if my question or code is unclear.
I'm coding a binary search tree and I'm stuck on the overloaded ==operator.

//BSTCLASS.CPP
template <class ItemType>
void BstClass<ItemType>::rFindNode(node<ItemType>* trav,ItemType& item,node<ItemType>* rtTrav,
								   ItemType& rtItem, bool& equal)const
{
	

	rFindNode(trav->left, trav->left->data, rtTrav->left, rtTrav->left->data, equal);

	if(item.key == rtItem.key)//Get an error here".key has no   struct/union 
		equal = true;
	else 
		equal = false;
	rFindNode(trav->right, trav->right->data, rtTrav->right, rtTrav->right->data, equal);
	


template <class ItemType>
bool BstClass<ItemType>::operator==(const BstClass<ItemType>& rtOp)const
{

	bool equal;

	rFindNode(root, root->data,rtOp.root, rtOp.root->data, equal);

	return equal;

}

I know the rFindNode function doesn't need all those parameters
i was just trying different things to see if i could get it to work.

my ItemType definition is in the client code per template standards

//TestClient.CPP
#include <iostream>

typedef int KeyType;

struct ItemType
{
	KeyType key;
	char data;
};


#include "bstTreeClass.h"

using namespace std;

void Display(ItemType& j);


void main() ......

My problem is that i'm getting an error when trying to assess my .key fields, I'm unclear on how i can access them so i can test them for equality

[Ancient Dragon]

replace KeyType with int to see what happens.

>>void main()

Its int main()

[Narue]

item and rtItem aren't nodes, they're the actual keys. You compare them like so:

if ( item == rtItem )

Your algorithm, however, is broken. It won't set equal to the correct value in all cases because you reset it to true. You need to consider more cases as well (such as null nodes). Compare and contrast with something like this:

template <class ItemType>
bool BstClass<ItemType>::rFindNode(node<ItemType>* trav, node<ItemType>* rtTrav) const
{
  // Base case: either node is null
  if (trav == 0 || rtTrav == 0) {
    // Both must be null to remain equal
    return trav == 0 && rtTrav == 0;
  }

  // Don't traverse if there's no need
  if (item->key != rtItem->key)
    return false;

  // Don't traverse the right if the left fails
  return rFindNode(trav->left, rtTrav->left) &&
         rFindNode(trav->right, rtTrav->right);
}

template <class ItemType>
bool BstClass<ItemType>::operator==(const BstClass<ItemType>& rtOp) const
{
  return rFindNode(root, rtOp.root);
}

I rearranged things to use a preorder traversal instead of inorder (this is to avoid unnecessary traversals if the current nodes don't match) and also to return the result rather than store it in a reference parameter. I also removed the redundant key parameters because that data is available from the nodes. The base case is important because without it you'll end up trying to dereference null pointers.

[evilsweeps]

hey, I do understand that my algorithm left out some cases and thank you for the working one, but I'm still having the problem of accessing that key field,

i can't do this

if ( item == rtItem )

b/c they are ItemTypes, unless i overloaded the ==operator for
ItemTypes the above statement throws me a whole mess of errors.

I have the same issue in the lines 10-12 of your example

#
// Don't traverse if there's no need
if (item->key != rtItem->key)
return false;

just like in mine i cannot access the key field, it throws me error
".key or -> key has no struct/class/union"

I'm thinking i might need another function that traverses in preOrder and returns an ItemType from each node and test those key fields, not sure if it'll work though, why can i not find any examples on this? very frustrating

[Narue]

Sorry about that. I misread your code and though ItemType was a typedef'd int. Since you still haven't provided enough code for me to be sure, I'll assume that the node class has an item instance rather than an item pointer, and suggest that this is the correct test:

// Don't traverse if there's no need
if (trav->item.key != rtTrav->item.key)
  return false;

[evilsweeps]

yeah, that's what i thought too, but I'm getting an error that my .key fields do not exist,

Error 1 error C2228: left of '.key' must have class/struct/union c:\documents and settings\lenovo\desktop\bst\bst\bst\bsttreeclass.cpp 346

Error 2 error C2228: left of '.key' must have class/struct/union c:\documents and settings\lenovo\desktop\bst\bst\bst\bsttreeclass.cpp 346

I think I have another problem elsewhere that's giving me the issue. Thanks for the help but i think i might have a syntax issue rather then an algorithm Issue. I have good deal of code, rather then post my whole project on here I will try to seek some help elsewhere.
Again Thanks for the Help :)

[Narue]

>rather then post my whole project on here
...you could trim it down to something reasonable that still gives an error. That's generally better for pinpointing errors because it eliminates a lot of code that isn't relevant to the problem.

>I will try to seek some help elsewhere.
The problem isn't with my qualifications (I'm probably one of the more qualified people to help you), it's with your failure to provide sufficient information. If you seek help elsewhere, you'll not get better answers without showing a more useful amount of code. But you go look elsewhere, don't expect me to jump at the chance to help when you come back. I don't take kindly to having my time wasted.

[evilsweeps]

ok, so i'll give this a shot, just to be clear when i said i'll find help elsewhere i was not attacking you qualifications, I have an issue explaining my problems on threads in an understandable manner , i don't want to waste anyone's time, so if i can even explain myself correctly how will i expect anyone to help.

So that being said, I tried to trim down my code, and this is what i got. The error i am encountering is testing the keys in the rFindNode function. If the code is still unclear, please let me know where the inconsistency is.
Thanks

//BSTCLASS.h
template <class ItemType>
struct node;


template <class ItemType>
class BstClass
{

//Methods to implement are:
  public:
	BstClass();		       					//constructor

    ~BstClass();							//destructor
     BstClass(const BstClass& orig);		//copy constructor	

	  void Insert(ItemType newItem,  bool& inTree); //   --if newItem is not 
	//		present  within the tree, inserts newItem into bst in correct 
	//		position setting inTree to false, otherwise sets inTree to true.

....

	  virtual bool operator==(const BstClass& rtOp)const;
	//		compares two bst's for equality of keys

protected:

void rInsert(node<ItemType>*& trav, ItemType newItem, bool& inTree);
bool rFindNode(node<ItemType>* trav,node<ItemType>* rtTrav)const;
void rDestroy(node<ItemType>* trav);
void rCopyTree(node<ItemType>* copy,const node<ItemType>* origRoot);

//BSTCLASS.cpp
//decleration of node
template <class ItemType>
struct node
{
	ItemType data;			//stores data in the tree
	node<ItemType>* left;	//points to left of the tree
	node<ItemType>* right;	//points to right of the tree
};



template <class ItemType>
BstClass<ItemType>::BstClass() //default constructor
//Pre:     None
//Purpose: Initializes private data member.
//Post:	   Private data member has been initialzed and is ready for
//         processing
{
	root = NULL;
}

template <class ItemType>
void BstClass<ItemType>::Insert(ItemType newItem,  bool& inTree)
{

	rInsert(root,newItem,inTree);

}

template <class ItemType>
BstClass<ItemType>::~BstClass()
//Pre:	   List exists
//Purpose: Returns object memory back to system 
//Post:    Object memory returned back to system
{

	rDestroy(root);

}

template <class ItemType>
BstClass<ItemType>::BstClass(const BstClass<ItemType>& orig)
// copy constructor
//Pre:     Copy constructor called my compiler
//Purpose: Creates a deep copy of class object
//Post:    Deep copy of the class object has created
{
 
	rDestroy(root);
	rCopyTree(root,orig.root); 

}


template <class ItemType>
void BstClass<ItemType>::rDestroy(node<ItemType>* trav)
{

	if(trav != NULL)
	{
		rDestroy(trav->left);
		rDestroy(trav->right);
		delete trav;
	}

}

template <class ItemType>
void BstClass<ItemType>::rCopyTree(node<ItemType>* copy,const node<ItemType>* origRoot)
{
	if(origRoot == NULL)
		copy = NULL;
	else
	{
		copy = Allocate();
		copy->data = origRoot->data;
		rCopyTree(copy->left,origRoot->left);
		rCopyTree(copy->right,origRoot->right);
	}
}

template <class ItemType>
bool BstClass<ItemType>::rFindNode(node<ItemType>* trav,node<ItemType>* rtTrav)const
{
	if(trav != NULL || rtTrav != NULL)
	{
	
	rFindNode(trav->left, rtTrav->left);
	if(trav->data.key == rtTrav->data.key) //***this is what is giving me the error *****
		return true;
	else 
		return false;
	rFindNode(trav->right, rtTrav->right);
	}
	else
		return false;
}

template <class ItemType>
void BstClass<ItemType>::rInsert(node<ItemType>*& trav, ItemType newItem, bool& inTree)
{

	if (trav==NULL)
	{
		trav = Allocate();
		trav->right = NULL;
		trav->left = NULL;
		trav->data = newItem;
	}
	else if(newItem.key == trav->data.key)//**I don't get an error here which makes me think i have a syntax issue with the rFindNode function****
	{
		inTree = true;
	}
	else if(newItem.key < trav->data.key)
	{
		rInsert(trav->left,newItem,inTree);
	}
	else
	{
		rInsert(trav->right,newItem,inTree);
	}


}


template <class ItemType>
bool BstClass<ItemType>::operator==(const BstClass<ItemType>& rtOp)const
{

	return rFindNode(root, rtOp.root);

}

//TestClient.cpp
#include <iostream>

typedef int KeyType;

struct ItemType
{
	KeyType key;
	char data;
};


#include "bstTreeClass.h"

using namespace std;

void Display(ItemType& j);


int main()
{
	
	bool inTree = false;
	ItemType item;
	item.key = 12;
	item.data = 'c';

	BstClass<ItemType> yourTree,thisTree;


	yourTree.Insert(item,inTree);

	thisTree.Insert(item,inTree);

	if(thisTree == yourTree)
cout << "works\n";
else
cout << "failed\n";



return 0;

}

[Narue]

I pieced your code together, fixed a few syntax errors, and shortened it up a bit. The only message I get from two standard compliant compilers is a warning about unreachable code in your rFindNode member function. Can you compile this and see if you get actual errors? If so, please say which compiler and version you're using:

#include <cstddef>

//BSTCLASS.h
template <class ItemType>
struct node;

template <class ItemType>
class BstClass
{
  node<ItemType> *root;
public:
  BstClass();
  ~BstClass();
  void Insert(ItemType newItem,  bool& inTree);
  virtual bool operator==(const BstClass& rtOp)const;
protected:
  void rInsert(node<ItemType>*& trav, ItemType newItem, bool& inTree);
  bool rFindNode(node<ItemType>* trav,node<ItemType>* rtTrav)const;
  void rDestroy(node<ItemType>* trav);
};

//BSTCLASS.cpp
template <class ItemType>
struct node
{
  ItemType data;			//stores data in the tree
  node<ItemType>* left;	//points to left of the tree
  node<ItemType>* right;	//points to right of the tree
};

template <class ItemType>
BstClass<ItemType>::BstClass()
{
  root = NULL;
}

template <class ItemType>
void BstClass<ItemType>::Insert(ItemType newItem,  bool& inTree)
{
  rInsert(root,newItem,inTree);
}

template <class ItemType>
BstClass<ItemType>::~BstClass()
{
  rDestroy(root);
}

template <class ItemType>
void BstClass<ItemType>::rDestroy(node<ItemType>* trav)
{
  if(trav != NULL)
  {
    rDestroy(trav->left);
    rDestroy(trav->right);
    delete trav;
  }
}

template <class ItemType>
bool BstClass<ItemType>::rFindNode(node<ItemType>* trav,node<ItemType>* rtTrav)const
{
  if(trav != NULL || rtTrav != NULL)
  {
    rFindNode(trav->left, rtTrav->left);
    if(trav->data.key == rtTrav->data.key)
      return true;
    else 
      return false;
    rFindNode(trav->right, rtTrav->right);
  }
  else
    return false;
}

template <class ItemType>
void BstClass<ItemType>::rInsert(node<ItemType>*& trav, ItemType newItem, bool& inTree)
{
  if (trav==NULL)
  {
    trav = new node<ItemType>();
    //trav = Allocate();
    trav->right = NULL;
    trav->left = NULL;
    trav->data = newItem;
  }

  else if(newItem.key == trav->data.key)
    inTree = true;
  else if(newItem.key < trav->data.key)
    rInsert(trav->left,newItem,inTree);
  else
    rInsert(trav->right,newItem,inTree);
}

template <class ItemType>
bool BstClass<ItemType>::operator==(const BstClass<ItemType>& rtOp)const
{
  return rFindNode(root, rtOp.root);
}

//TestClient.cpp
#include <iostream>

typedef int KeyType;

struct ItemType
{
  KeyType key;
  char data;
};

using namespace std;

int main()
{
  bool inTree = false;
  ItemType item;
  item.key = 12;
  item.data = 'c';

  BstClass<ItemType> yourTree,thisTree;

  yourTree.Insert(item,inTree);
  thisTree.Insert(item,inTree);

  if(thisTree == yourTree)
    cout << "works\n";
  else
    cout << "failed\n";
}

[evilsweeps]

well your version works, I'm going to go through and test my code and test it against yours, thanks for the help