Binary Search Tree Array Imp. C++

Question

Hello,

I'm just having trouble with Inserting into the array...And having the children branch off from the root, or "parent"..

I've been trying to insert data into an array based implementation of a BST:

BST::BST(int capacity) : items(new item[capacity]), size(0)
{
     // define the constructor to the BST Class.
}

void BST::insert (const data& aData)
{
    if ( items[root].empty ) // make the first data the root.
    {
     items[root].theData = aData;
     items[root].empty = false;
     size++;
    }
    else if ( items[root].theData.getName() < aData )
    {
     items[leftChild].theData = aData; // will be overwritten...
     this->insert(aData);
    }
    else if ( aData < items[root].theData.getName() )
    {
     items[rightChild].theData = aData;
     this->insert(aData);
    }  
}

A few things are wrong with this. Let me start by saying that the first incoming data will be the root. All other data will be compared against it. When I make the recursive calls to "insert" that is essentially how I "think" i am "traversing" (if it were a linked list). The main problem for me is knowing that my left and right children will be overwritten. I'm wondering How I can keep branching from the child "nodes"...?

Here is my header file for the BST class, I'm also concerned if I have set the members up right and everything..?

class BST
{ 
public:
    BST(int capacity = 5);
    BST(const BST& aTable);

    void insert(const data& aData);
         ....
 private:
    int size;  // size of the ever growing/expanding tree :)

    struct item
    {
     bool empty;
     data theData;
    };

    item  * items;    // The tree array
    int   rightChild; // access to the RHS
    int   leftChild;  // access to the LHS
    int   root;   // index to the root
};

I have another source file, "data" to which i am making the calls, "getname". Three simple methods I have defined so far are the assignment operator overload, comparison '<' overload and the ctor to the data class:

data::data(char const * const name) : name(new char[strlen(name)+1])
{
    if (name)
    {
     strcpy(this->name , name);
    }  
    else this->name = NULL;
}

data& data::operator=(const data& data2)
{ 
    if ( this != &data2 ) // check for selfassignment
    {
     delete [] name;
     name = NULL;

     this->name = new char[strlen(data2.name)+1];
     strcpy(this->name , data2.name);
    }
    return *this;
     }

bool operator< (const data& d1, const data& d2)
{
    if ( strcmp( d1.getName(), d2.getName() ) == -1 )
    {
     return false;
    }
    else if ( strcmp( d1.getName(), d2.getName() ) == 1 )
    {
     return true;
    }
    return false; // if they are equal return false
}

Answer 1

I see a few problems. leftChild and rightChild should be members of the item struct, not of BST, because they are different for every item (or they should not exist as fields and be computed dynamically). I see no code that ever sets leftChild and rightChild to anything.

It looks like you're trying to recursively define insert. You should probably define an insert helper function that takes both an item and an index of the insertion point. That should set you on the right track.

The wikipedia article has more pseudocode you can look at.