Awesome, That worked. I am only adding 9 items so using this array shouldn't
be a problem. My parent index starts at zero. When it adds "Goble, Colin" at index 7 like it suppose to, to the left. The next name is "knuth, Donald" that adds to the right like it suppose to. It suppose to go to index 8 however, parent goes
from 7 to 16 and thats not what i want. My problem might be in my expand function?
Am i suppose to always be comparing the new item with the first parent? or the last parent that was added?
this is the order i am hoping to achieve.
Code:
<< "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"));
database.insert(data("Trigoboff, Michael"));
database.insert(data("Turing, Alan"));
Required output...
Ralston, Anthony 0
Liang, Li 1
Von Neumann, John 2
Jones, Doug 3
Trigoboff, Michael 5
Goble, Colin leaf 7
Knuth, Donald 8
Turing, Alan leaf 12
Kay, Alan leaf 17
I changed the code a bit from the first post.
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)
{
parent = (2 * parent)+ 1;
if(parent > maxsize)
{
this->expand();
}
this->insert(aData);
}
else
{
parent = (2 * parent)+ 2;
if(parent > maxsize)
{
this->expand();
}
this->insert(aData);
}
expand array.
Code:
void BST::expand()
{
item *swap = new item[size+1];
for ( int index = 0; index < size*2; index++ )
{
if ( !items[index].empty )
{
swap[index].instanceData = items[index].instanceData;
swap[index].empty = false;
}
}
maxsize += size;
delete [] items;
items = NULL;
items = swap;
}
Code:
BST::BST(int capacity) : size(0), parent(0),
items(new item[capacity])
{
maxsize = capacity;
items->empty = true;
}