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;
}
