Binary Search Tree Using an array
Hello, i am trying to add items to a tree. I am finding no information in my book or the web about BST and arrays.
Since all i can find is pointer based i am trying to convert
that to array based and implement that. I am checking
if ( aData < items[parent].instanceData)
then add to the left or right . However, it seems all the items to be adding to the right.
The indexes are not in the right order either. I was told i need a helper function that knows the index. I dont know why i would need one.
driver
Code:
data aData;
cout << "Database Of Great Computer Scientists\n\n";
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"));
Code:
void BST::insert (const data& aData)
{
if ( items[parent].empty )
{
items[parent].instanceData = aData;
items[parent].empty = false;
size++;
}
else if ( aData < items[parent].instanceData)
{
if ( parent >= maxsize )
{
this->expand();
}
parent = (2 * parent)+ 1;
this->insert(aData);
}
}
else
{
if ( parent >= maxsize )
{
this->expand();
}
parent = (2 * parent)+ 2;
this->insert(aData);
}
}
Code:
bool operator< (const data& d1, const data& d2)
{
if ( strcmp( d1.getName(), d2.getName() ) == 1 )
{
return true;
}
else if ( strcmp( d1.getName(), d2.getName() ) == -1 )
{
return false;
}
return false;
}
is my logic off in the operator< function? it seems to want to add all items to the right.
Also, parent goes from 0 to 2 to 6 to 14
any help is much appreciated