tags:

views:

173

answers:

2

Hello. I need just a little more help on my BST. This is what my BST looks like when inserting:

R, L, J, G

                      R   --Root at Index 0
                     / \
     L @ Index1     L   NULL
                   / \
     J @ Index3   J   NULL
                 / \
     G @ Index7 G  NULL

Here is the code that makes it happen.

void BST::insert(const data &aData)
{   
    if ( items[Parent].empty ) 
    {
     items[Parent].theData = aData; // insert at leaf.
     items[Parent].empty = false;
     size++;

     return;
    }   
    for ( int i = 0; i <= size; i++ )
    {
     if ( aData < items[Parent].theData )
     {
       if ( items[2*i+1].empty )
      {
   items[2*i+1].theData = aData;
   items[2*i+1].empty = false;
      }
      else 
                           {
   // we must already have a left child to some root.
                                Parent++;  So make the previous data the root???
   if ( items[Parent].empty )
   {
    items[Parent].theData = items[2*i+1].theData;
    items[Parent].empty   = false;
    Parent = (i-1)/2;
   }
                           } 
     }
     else
     { ...// do the same for data greater than but with items[2*i+2] }

MY question is that when would i need to make a new root? When would I need to make a new root? For recomparison?

Is this approach correct? Thank you to those who even both to look at my posts :)

// The constructor the BST Class and its private section.

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0)
{
    items->empty = true;
    maxSize = capacity;
}
private:
    int size;  // size of the ever growing/expanding tree :)
    int Parent;
    int maxSize; 
    int leftChild;
    int rightChild;
    struct item
    {
     bool empty;
     data theData;
    };
    item *items;    // The tree array
+1  A: 

Your logic (rather fuzzy I must say) appears to be wrong: What kind of "if" sequence is that?

if ( items[2*i+1].empty )
{
}
else if (!items[2*i+1].empty)
{
   if ( items[2*i+1].empty )
   {
        // any code here is unreachable
   }
}
BostonLogan
I wondered that myself. It kept going so i didnt question it.
I thought that if i could at least construct it. Going back to make it better would be easy. Its hard for me to write efficient code the first time around.
I guess what I needed it to do their is for the loop to iterate
+1  A: 

I suggest you reimplement this to work recursively. Something like this:

void BST::insert(const data& aData, int pos) {
    if (items[pos].empty) {
        // insert it here
    }
    else (aData < items[pos].theData) {
        // go to left child
        insert(aData, 2*pos + 1);
    }
    else {
        // go to right child
        insert(aData, 2*pos + 2);
    }
}

It's not really clear what Parent, leftChild, and rightChild are doing in your class, but that's a separate issue.

Andrey