tags:

views:

88

answers:

0

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