Thread: Array based Binary search tree- Searching

I am trying to retrieve a name as a key in the tree recursively.
my tree is as follows. 0,1,3,7,8,17,2,5,12 atleast thats
how it was added. I am searching for index 5 "Trigoboff, Michael"
parent =0;
it suppose to go from parent(index) 0,2,5 however its going from 0,2,6 in the retrieve function...

Is my comparison wrong? or is it something to do with my retrieve function?
I have been working on this for 4 days and im ready to give up!

main()

Code:

	database.insert(data("Ralston, Anthony"));
	database.insert(data("Liang, Li"));
	database.insert(data("Jones, Doug"));
	database.insert(data("Goble, Colin"));
	database.insert(data("Knuth, Donald"));
	database.insert(data("Kay, Alan"));
	database.insert(data("Von Neumann, John"));
	database.insert(data("Trigoboff, Michael"));
	database.insert(data("Turing, Alan"));
	displayDatabase(true);
	retrieveItem("Trigoboff, Michael", aData);
	retrieveItem("Kaye, Danny", aData);

one header

Code:

#include "data.h"

class BST								// a Binary Search Tree (BST)
{
public:
	BST(int capacity = 5);				// constructor (default if no arg supplied)
	BST(const BST& aTable);				// copy constructor
	~BST();								// destructor

	void insert(const data& aData);		
	bool remove(const char *key);
	bool retrieve(const char *key, data& aData) const;
	void displayArrayOrder(ostream& out) const;		
	void displayPreOrder(ostream& out) const;
	void displayInOrder(ostream& out) const;
	void displayPostOrder(ostream& out) const;
	int getSize(void) const;

private:

    int size;
    int maxsize;  
    int parent;
    
 
    void expand();

	struct item
	{
		bool	empty;
		data instanceData;
		bool  isLeaf;
	};
	
	item *items;
	
	void insert(int index, const data & aData ); 
	void displayHeaders(ostream& out)const;
	void BST::displayPreOrder(std::ostream &out, int parent)const;
	void BST::displayInOrder(std::ostream &out, int parent)const;
	void BST::displayPostOrder(std::ostream &out, int parent)const;
	bool BST::retrieve(const char *key, data& aData, int parent) const;
	void itemsPrinted(ostream &out,int size)const;
};


#endif // BST_H

retrieve functions...

Code:

bool BST::retrieve(const char *key, data& aData) const
{

	retrieve(key, aData, parent);

	if (key == aData)
	{
		return true;
	}
	else
	{
		return false;
	}



}

Code:

bool BST::retrieve(const char *key, data &aData, int parent) const
{


	if (!items[parent].empty )
	{

		if (key == items[parent].instanceData.getName())
		{
			aData.setName(key);
			return true;
		}
		else if (key < items[parent].instanceData.getName() )
		{
			parent =(2*parent) + 1;
			retrieve(key, aData, parent);
		}
		else
		{
			parent =( 2*parent) + 2;
			retrieve(key, aData, parent);
		}
		return 0;

	} 
}

BOTH comparison operators..

Code:

bool operator< (const data& d1, const data& d2)
{

 return strcmp(d1.getName(), d2.getName()) < 0;
	

}

// return true if d1 is "equal to" d2, false otherwise
bool operator== (const data& d1, const data& d2)
{

return strcmp(d1.getName(), d2.getName()) == 0;

	
	
}