Im trying to build an array based, "Binary Search Tree". So far I enjoy the concept and drawing by following the diagrams on paper! However, when i do thatalgorithm at:
http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif::600::388::/sites/dl/free/0070131511/25327/tree_insert.gif::TREE-INSERT.
...using the nodes are all linear!algorithm I was wondering if anyone could help me "balance"came up with the tree?following code:
void BST::BSTinsert(int capacity) : items(newconst item[capacity]),data size(capacity-1),&aData tree_index(0), root_index(0)
{
items[root_index].empty = true;
items[tree_index].empty = true;
}
void BST::reallocate()
{
item *new_array = new item[size*2];
for ( int array_index*y = 0; array_index < size; array_index++ )
{
&items[root_index]; //new_array[array_index].theData = items[array_index].theData;
Algorithm calls for NULL new_array[array_index]assignment.empty = false;
}
size *= 2;
delete [] items;
.
items = NULL;
item items*x = new_array;
}
void BST::insert(const data&&items[root_index]; myData)
{
data *aData = newwhile data(myData);
if (! items[root_index].empty == true ) // make the first data the root.
{
root_index++;
items[root_index].theData = *aData;
items[root_index].emptyy->theData = false;
x->theData; // Ptrs are items[tree_index].emptyrequired =or true;
}
else if ( (*aData) < items[root_index].theData ) // then we have a leftcrash childoccurs.
{
if ( items[tree_index].emptyaData ==< falsex->theData ) // we already have a child
{
root_index++;
items[root_index].theDatax->leftChild = items[tree_index].leftChild;aData;
tree_index++;}
else
items[tree_index].empty = true;{
thisx->insert(*aData); // call again for another comparison because we have a>rightChild new= rootitems[root_index]. theData;
}
if (// tree_indexwhat ==is sizep[z] )= //y? preventis overflow
it outside the looping {scheme?
this->reallocate(); root_index++; // and make the call to reallocate items array
new child the root? items[tree_index].empty = false;
}
// construct the left subtree if..
( y->empty else)
{
items[tree_index].leftChild = *aData;
//items[tree_index]items[root_index].theData = *aData;aData;
items[tree_index]items[root_index].empty = false;
root_index = 1;
}
}
else // right child
{
// construct the right subtree in a similar way.
if ( items[tree_index].emptyaData ==< falsey->theData )
{
root_index++;
items[root_index].theDatay->leftChild = items[tree_index].rightChild;
aData; tree_index++;
items[tree_index].empty = true;
this->insert(*aData); // call again for another comparison becauseIf we already have a new root.
}
if ( tree_index == size ) // prevent overflow
{
this->reallocate(); /left/right child...make the call toit reallocatethe itemsroot? arrayre-cmpr?
items[tree_index].empty = false;
}
// construct the left subtree if..
else
{
items[tree_index].rightChildy->rightChild = *aData;
//items[tree_index]items[root_index].theData = *aData;theData;
items[tree_index].empty = false;}
root_index = 1;
}
}
} Questions:
Not actual Code
insert("R");
insert("A");
insert("F");
insert("L");
insert("B");
insert("T");
insert("C");
insert("G");
For a while, it went kinda nice. A and F are both less than R in ascii value. So whenever i had another potential child i simply made the already present child the "root" or "parent" I cannot figure out what p[z] <- y means. And did my recursive call and compared the new data...But after a while itIm just incrementing the code gets confusing and doesnt work..root to imitate a traverse.
R
/
A
\
F
/
L <---- Wrong b/c the root gets mixed up..its not "R" anymore!
If I might be missing an important iterative solution..instead of recursion..
Not good. Im tryingalready have a left/right child then i should make that left/right child taht im about to keepoverwrite the root? Therein i should make it recurisve so it will switch back to the original root, "R" for all comparisons. Either recursively or iteratively.?
Here is my struct where items and its members that im using are defined within the BST private section:Insertions
...insert("R");
insert("A");
insert("F");
insert("L");
insert("B");
insert("C");
insert("T");
struct item
{
bool empty;
data theData;
data leftChild;
data rightChild;
};
item *items; // The tree array
int root_index; // index for the root
int tree_index; // index to for the data items
