Thread: Missing a line from the output

I'm not too sure why I'm missing a line from the output. I've been going over my code like crazy and something seems to cause a line which would be size = 0: [nothing here] missing in my output. Here's my code:

Code:

class binSTree: public binTree<T>{
public:
    void insert(const T& x); //insert node with value x
    bool search(const T& x); //searches leaf with value x
    bool remove(const T& x); //removes leaf with value x
private:  //implemented recursively
    void insert(binTreeNode<T>*&, const T&); //private version of insert
    bool search(binTreeNode<T>*, const T&) const; //private version of search
    void remove(binTreeNode<T>*&, const T&); //private version of remove
    bool leaf(binTreeNode<T>* node) const; //checks if node is leaf
};


//public
template <class T>
void binSTree<T>::insert(const T& x)
{
    insert(this->root, x);
}


template <class T>
bool binSTree<T>::search(const T& x)
{
    return search(this->root, x);
}


template <class T>
bool binSTree<T>::remove(const T& x)
{
    //search(x);
    /*if( this->size() == 0 )
    {
        this->root = NULL;
        return false;
    }*/
    
    if( this->size() > 1 )
    {     
        if( search(x) )
            remove( this->root, x );
        return true;
    }
    else
    {
        return false;
    }
}
/**********************************
private
***********************************/
template <class T>
void binSTree<T>::insert(binTreeNode<T>*& p, const T& x)
{
    if (p == NULL)
        {
                binTreeNode<T>* newNode;
                newNode = new binTreeNode<T>(x);
                p = newNode;
        }
      else
        {
                if (x < p -> data)
                        insert(p -> left, x);
                if (x > p -> data)
                        insert(p -> right, x);
        }                
}
template <class T>
bool binSTree<T>::search(binTreeNode<T>*p, const T& x) const
{
    //x is data value of a leaf to be searched for
    if( p == NULL ) return false;
    else
    {
        if(x == p->data)
        {
            if( leaf(p) ) return true;
            else return false;
        }
        if( x < p->data )
        {
            return search( p->left, x );
        }
        else
        {
            return search( p->right, x );
        }
    }
}//end search


template <class T>
void binSTree<T>::remove(binTreeNode<T>*& p, const T& x)
{
    binTreeNode<T>* curr;
    binTreeNode<T>* parent;
    curr = p;


    while( curr != NULL )
    {
         if( curr->data == x )
         {
            break;
         }
         else
         {
             parent = curr;


             if( x > curr->data ) curr = curr->right;
             else curr = curr->left;
         }
    }


    if( curr != NULL )
    {
        if( parent->right == curr ) parent->right = NULL;
        else parent->left = NULL;


        delete curr;
        curr = 0;
    }
}


template <class T>
bool binSTree<T>::leaf(binTreeNode<T>* node) const
{
    if(node->left == NULL && node->right == NULL)
        return true;
    else
        return false;
}

Other files are included but they are 100% correct as I used them in my past couple of assignments. The public version of remove is suppose to call the search function and determine the result of the search for a leaf with value x. Calls private remove and returns true. Otherwise it returns false if the search isn't successful. Any tips?

Originally Posted by kmdv

Interesting. A problem with output, but no single line responsible for it.

Maybe post something with "main()" ("int main()" preferably)?

Sure thing.

Code:

 int main(){
    vector <int> v(N); //holds rand ints
    binSTree <int> t; //binary search tree(BST)
    
    //generate rand ints
    generate(v.begin(), v.end(), RND());
    
    //printout contents of vector
    SZ = v.size(); COUT_SZ;
    for_each(v.begin(), v.end(), print<int>); cout << endl;


    //insert ints in vector into BST
    for(unsigned i = 0; i < v.size(); i++) t.insert(v[i]);
    
    //remove leaves of BST until it becomes empty
    bool flag = true; //to check if BST empty
    while(flag)
    {
        //printout contents of BST
        SZ = t.size(); COUT_SZ;
        t.inorder(print<int>); cout << endl;
        
        //remove all leaves of BST
        flag = false;
        for(unsigned i = 0; i < v.size(); i++)
            if(t.remove(v[i])) flag = true;
    }
    system("pause");
    return 0;
}

When I go through the build via Visual Studio, it skips the while loop and doesn't spit out my last line.

HAHA NIU 340?
I had the same issue but for the 1=
Here was my fix, hope it helps.

Code:

// removes leaf with value x
template <class T>
bool binSTree<T>::remove ( const T& x )
{
    if(this->size()==-1)
    {
        this->root = NULL;
    return false;
    }
    if(this->size()>0)
    {    
        if( search(x) )
            remove( this->root, x );
        return true;
    }
    else
        return false;
}

Originally Posted by Morfus

HAHA NIU 340?
I had the same issue but for the 1=
Here was my fix, hope it helps.

Code:

// removes leaf with value x
template <class T>
bool binSTree<T>::remove ( const T& x )
{
    if(this->size()==-1)
    {
        this->root = NULL;
    return false;
    }
    if(this->size()>0)
    {    
        if( search(x) )
            remove( this->root, x );
        return true;
    }
    else
        return false;
}

Thanks! Funny visual studio didn't want to do that this whole time :/. Kept telling me that parent in private remove needed to be initialized. Drives me nuts sometimes when one compiler says no and the other says yes.

Originally Posted by raz23

Thanks! Funny visual studio didn't want to do that this whole time :/. Kept telling me that parent in private remove needed to be initialized. Drives me nuts sometimes when one compiler says no and the other says yes.

Yeah, I always had issues using my own comiplers. Whenever I get strange compiler errors I try hopper and it usually fixes it. Glad that code helped!