traverse a Binary search tree

Question

I am trying to do a preorder traverse

Answer 1

Preorder traversal just means the "visit" function looks like:

• process contents of this node;
• visit left child;
• visit right child;

Addendum:

It's not entirely clear from your code, but you might try something like this:

void BST::displayPreOrder(std::ostream &out, int parent)
{
    if (parent < size) 
    {
        if (!items[parent].empty)
        {
            out << items[parent].instanceData;
            out << endl;
        }

        this->displayPreOrder(out, 2 * parent + 1);   
        this->displayPreOrder(out, 2 * parent + 2);   
    }
}

(If "empty" nodes never have any child nodes, then you can combine that into a single if statement).

Answer 2

Here is some psuedo code of a preorder that may help.

void Preorder( out, int parent )
{
    out << items[parent];
    left = parent * 2 + 1;
    right = parent * 2 + 2;

    if( left> -1 )
        Preorder( out, left );

    if( right > -1 )
        Preorder( out, right );
}

Answer 3

Your function for visiting nodes only goes left or right. Try something more like this:

void BST::displayPreOrder(std::ostream &out, int parent)const
{    
   if (parent>=0 && parent<size && !items[parent].empty) 
   {
       out << items[parent].instanceData;
       out << endl;

       if (true )
       {
            // go left
            int next = (2 * parent)+ 1; 
            this->displayPreOrder(out,next);    
       }

       if( true )
       {
           // go right
           int next = (2 * parent)+ 2; 
           this->displayPreOrder(out,next);
       }
    }
}

The calculations I show for 'next' may or may not be right ... you haven't given us a full description of how you're embedding this tree in the array, so I can only guess based on what you did show us.