Im stuck with filling my Array Based BST in C++

Question

Hello,

Im trying to build an array based, "Binary Search Tree" by following the algorithm at:

http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/25327/tree%5Finsert.gif%3A%3ATREE-INSERT.

...using the algorithm I came up with the following code:

void BST::insert( const data &aData )
{
     item *y = &items[root_index];   // Algorithm calls for NULL assignment..
     item *x = &items[root_index]; 

while ( ! items[root_index].empty )
{
 y->theData = x->theData; // Ptrs are required or else a crash occurs.
 if ( aData < x->theData )
 {
  x->leftChild = aData;
 }
 else
 {
  x->rightChild = items[root_index].theData;
 } 

 // what is p[z] = y? is it outside the looping scheme?

 root_index++; // and make the new child the root?  
}
 if ( y->empty ) 
 {
  items[root_index].theData = aData;
  items[root_index].empty = false;
 }
 else if ( aData < y->theData )
 {
  y->leftChild = aData; 
 // If we already have a left/right child...make it the root? re-cmpr?
              }
 else
 {
  y->rightChild = items[root_index].theData;
 }

  }

Questions:

I cannot figure out what p[z] <- y means....Im just incrementing the root to imitate a traverse.

If I already have a left/right child then i should make that left/right child taht im about to overwrite the root? Therein i should make it recurisve so it will switch back to the original root, "R" ?

Insertions insert("R"); insert("A"); insert("F"); insert("L"); insert("B"); insert("C"); insert("T");

Answer 1

my guess is that your if/else statement isn't comparing correctly:

aData->getName() < items[root_index].theData

why not do

(*aData) < items[root_index].theData

??

The getName method would have to essentially return a copy of the object for your comparison to work.

Here is the Insert method I wrote for BST:

 /* Insert by node */
 template<class T>
 void Tree<T>::Insert(Node<T> *insertingNode)
 {
  Node<T> *y = NULL;
  Node<T> *x = &this->Root;

  while( x != NULL)
  {
   // y is used as a temp
   y = x;

   // given value less than current
   if(insertingNode->value < x->value)
   {
    // move to left of current
    x = x->ptrLeft;
   }
   else
   {
    // move to right of current
    x = x->ptrRight;
   }
  }

  // now, we're in place
  // parent of inserting value is last node of loop
  insertingNode->ptrParent = y;

  // if there is no node here, insert the root
  if (y == NULL)
  {
   Root = *insertingNode;
  }
  else
  {
   // Place inserting value accordingly
   if(insertingNode->value < y->value)
   {
    // Goes on the left
    y->ptrLeft = insertingNode;
   }
   else
   {
    // Goes on the right
    y->ptrRight = insertingNode;
   }
  }

 };