Hello,
I used a binary heap concept to insert elements in my items array:
void BST::insert(const data &aData)
{
int slot = size + 1;
if ( size >= maxSize ) this->reallocate();
while ( slot > 1 && aData < items[slot / 2 - 1].theData )
{
items[slot - 1] = items[slot / 2 - 1];
slot = slot / 2;
}
items[slot-1].theData = aData;
items[slot-1].empty = false;
++size;
}
I inserted the following elements in this order:
insert("R"); insert("A"); insert("F"); insert("Z"); insert("B"); insert("X");
Using the insertion function given first, my "items" array now looks like:
A | B | F | Z | R | X | ...
Where A is the 0 slot in memory.
Given this array order I think my tree looks like this:
A
/ \
B F
/ \ /
Z R X
If i were to call a method like pre-order, Printing this would be correct?
I know what to do for inorder, and its weird because of the items inserted, it will resemble that of a linear linked list..bad.
What would post order look like?
To make the traversals at this point i am trying to use formulas for the left and right child indexes..
I know their are formula's i can use for complete tree's, such as items[2*leftChild+1] and items[2*rightChild+2].
But they are not accessing correctly..They are initialized to zero in my BST ctor and private to my BST class object.. // ctor
BST::BST(int capacity) : items(new item[capacity]), size(0),
leftChild(0), rightChild(0)
{
maxSize = capacity-1;
}
// private members to BST
private:
int size; // size of the ever growing/expanding tree :)
int maxSize;
int leftChild;
int rightChild;
struct item
{
bool empty;
data theData;
};
item *items; // The tree array