Alright, so I am designing a program that contains binary trees to function as a parser. I have encounted a very strange problem that is causing my program to fail while it is running. I have done several tests and narrowed down the incidents.

Ok, so this results in a successful test:

#include <iostream>
#include <cstdlib>
#include "BinaryTree.cpp"
#include "Stack.cpp"

using namespace std;

int main()
{
    BinaryTree<char> treeL, treeR;
    Stack< BinaryTree<char> > stack1;

    BinaryTree<char> tree1('a'); 
    cout << "Test";

    return 0;
}

Output:

Test
RUN SUCCESSFUL (total time: 93ms)

Now, whenever I throw in the push function (the method that causes the program to crash the most):

#include <iostream>
#include <cstdlib>
#include "BinaryTree.cpp"
#include "Stack.cpp"

using namespace std;

int main()
{
    BinaryTree<char> treeL, treeR;
    Stack< BinaryTree<char> > stack1;

    BinaryTree<char> tree1('a'); 
    cout << endl << endl << endl << "Test";
    stack1.push(tree1);

    return 0;
}

I get this output (periods added to show newlines):

.
.
.
RUN FAILED (exit value 1, total time: 271ms)

Notice how it still prints the newlines but fails to print the text. Even stranger is that the push function comes after the cout, it shouldn't affect it.

Lastly, whenever I do the pop function instead:

#include <iostream>
#include <cstdlib>
#include "BinaryTree.cpp"
#include "Stack.cpp"

using namespace std;

int main()
{
    BinaryTree<char> treeL, treeR;
    Stack< BinaryTree<char> > stack1;

    BinaryTree<char> tree1('a'); 
    cout << endl << endl<< endl << "Test";
    stack1.pop();

    return 0;
}

I get this:

.
.
.
Test
The stack is already empty.

RUN FAILED (exit value 1, total time: 168ms)

With that method, it prints the text correctly and completes the method, but fails immediately after. I can't for the life of me understand why it does these things but maybe you can help. Here is my push and pop functions:

template <class elemType>
void Stack<elemType>::push(elemType x)
{
    Stack_Node<elemType> *newNode;

    newNode = new Stack_Node<elemType>;
    newNode->value = x;
    newNode->link = stackTop;
    stackTop = newNode;
}

template <class elemType>
elemType Stack<elemType>::pop() 
{
    Stack_Node<elemType> *temp;

    if (!IsEmpty())
    {
        temp = stackTop;
        stackTop = stackTop->link;
        return temp->value;             //Returns the value of the top node.
        delete temp;                    //Deletes the top node in the stack.
    }

    else
        cout << endl << "The stack is already empty." << endl;
}

here is the BinaryTree constructor being used:

//Constructor #2
template<class Node_Type>
BinaryTree<Node_Type>::BinaryTree(Node_Type nodeValue)
{
    root = new Tree_Node;
    root->Node_Info = nodeValue;        //Store value into root node.
    root->left = NULL;
    root->right = NULL;
}

and stack.h:

#ifndef STACK_H
#define STACK_H

//Node definition.
template<class elemType>
struct Stack_Node
{
    elemType value;
    Stack_Node<elemType> *link;
};

template<class elemType>
class Stack
{
    public:
        const Stack<elemType>& operator=(const Stack<elemType>&);
        //Overloaded assignment operator.

        void initialize();
        //Function to initialize the stack.
        //Postcondition: stack is empty.

        void push(elemType x);
        //Function to add x to the stack.
        //Precondition: The stack exists and is not full.
        //Postcondition: x is added to the top of the stack.

        elemType pop();
        //Function to return and remove the top element of the stack.
        //Precondition: The stack exists and is not empty.
        //Postcondition: The top element is returned then removed from the stack

        bool IsEmpty() const;
        //Function to determine if the stack is empty.
        //Postcondition: Returns true if stack is empty, else returns
        //               false.

        Stack();
        //Default constructor.
        //Postcondition: The top of the stack is set to NULL.

        Stack(const Stack<elemType>& otherStack);
        //Copy constructor.

        ~Stack();
        //Destructor.
        //Removes all elements from the stack.
        //Postcondition: The list is deleted.

    private:
        Stack_Node<elemType> *stackTop;
        //Pointer to the top of the stack.

        void copyStack(const Stack<elemType>& otherStack);
        //Function to make a copy of otherStack.
        //Postcondition: A copy of otherStack is made and assigned to this one.
};

#endif  /* STACK_H */

The IsEmpty function works fine. If any of you need any of the BinaryTree.h , BinaryTree.cpp , or operation overloading code let me know. I'm trying to keep this post as clean as possible. Thanks.

Edited 4 Years Ago by happygeek: undeleted

In the code you posted, the only error I can spot is this bit:

return temp->value;             //Returns the value of the top node.
delete temp;                    //Deletes the top node in the stack.

You can't have a statement after the return statement. That statement will never execute. You need to do:

elemType tmp_val = temp->value; //Returns the value of the top node.
delete temp;                    //Deletes the top node in the stack.
return tmp_val;

I see nothing fundamentally wrong with your push and pop functions. Your error must be in the copy-constructor, copy-assignment and/or destructor of your BinaryTree class. These can be tricky to implement and you are using plenty of them in the push-pop functions.

Notice how it still prints the newlines but fails to print the text. Even stranger is that the push function comes after the cout, it shouldn't affect it.

This is simply because the text is outputed without a flushing of the standard output. Newlines have the effect of flushing the output buffer (i.e., actually printing it to the screen). Basically, the error occurs before the standard output buffer is flushed on its own (without being explicitly triggered), and because the error message appears on the standard error output, it never actually prints out the text before the end of the program. In the pop case, it is different, because you print something else to the standard output before the error occurs. To fix that little quirk, just use this:

cout << endl << endl << endl << "Test" << flush;
stack1.push(tree1);

Ah thanks, can't believe I didn't notice that mistake in pop. That fixes the pop incident, but the program still fails with push. Here is the rest of my code:

stack copy constructor:

//Copy Constructor
template <class elemType>
Stack<elemType>::Stack(const Stack<elemType>& otherStack)
{
    stackTop = NULL;
    copyStack(otherStack);              
}

stack copyStack function:

template <class elemType>
void Stack<elemType>::copyStack(const Stack<elemType>& otherStack)
{
    Stack_Node<elemType> *newNode, *current, *last;

    if (!IsEmpty())
        initialize();

    if (otherStack.IsEmpty())
        stackTop = NULL;
    else
    {
        current = otherStack.stackTop;
        stackTop = new Stack_Node<elemType>;
        stackTop->value = current->value;
        stackTop->link = NULL;
        last = stackTop;
        current = current->link;

        while (current != NULL)
        {
            newNode = new Stack_Node<elemType>;

            newNode->value = current->value;
            newNode->link = NULL;
            last->link = newNode;
            last = newNode;
            current = current->link;
        }
    }
}

stack overloaded =:

//Overloaded assignment operator
template <class elemType>
const Stack<elemType>& Stack<elemType>::operator=(const Stack<elemType>& 
                                                  otherStack)
{
    if (this != &otherStack)
        copyStack(otherStack);

    return *this;
}

BinaryTree copy constructor:

//Copy constructor
template<class Node_Type>
BinaryTree<Node_Type>::BinaryTree(const BinaryTree<Node_Type>& otherTree)
{
    if (otherTree.IsEmpty())
        root = NULL;
    else
        copyTree(otherTree.root);
}

PRETTY SURE THIS IS WHERE THE ERROR IS HAPPENING
BinaryTree copyTree function:

template<class Node_Type>
typename BinaryTree<Node_Type>::Tree_Node* BinaryTree<Node_Type>::
                                copyTree(const Tree_Node* otherTree)
{
    if(otherTree == NULL)
        return NULL;
    else
    {
        Tree_Node *copy = new Tree_Node;
        copy->Node_Info = otherTree->Node_Info;
        copy->left->root = copyTree(otherTree->left->root);     
        copy->right->root = copyTree(otherTree->right->root);
        return copy;
    }
}

BinaryTree overloaded =:

template<class Node_Type>
const BinaryTree<Node_Type>& BinaryTree<Node_Type>::operator=
      (const BinaryTree<Node_Type>& otherTree)
{
    if (this != &otherTree)     //Avoid self-copy
    {
        if (root != NULL)       //If the binary tree is not empty, destroy it.
            destroyTree(root);

        if(otherTree.IsEmpty())
            root = NULL;
        else
            copyTree(root);
    }

    return *this;
}

BinaryTree overloaded <<: (Probably something wrong with this one)

template <class Node_Type>
ostream& operator<<(ostream& out, const BinaryTree<Node_Type>* other)
{
    out << other->Info();
    return out;
}

BinaryTree Destructor:

//Destructor
template<class Node_Type>
BinaryTree<Node_Type>::~BinaryTree()
{
    delete root; //Will recursively delete all nodes below it.
}

and the struct used:

private:
        //Node definition
        struct Tree_Node
        {
                Node_Type Node_Info;
                BinaryTree<Node_Type> *left;
                BinaryTree<Node_Type> *right;
        };

        Tree_Node *root;

Sorry for all the code but this should be everything you asked for.

Edited 4 Years Ago by tvm78

In this code:

    copy->left->root = copyTree(otherTree->left->root);     
    copy->right->root = copyTree(otherTree->right->root);

Where do you allocate the memory that copy->left and copy->right point to? Are you sure that neither of otherTree->left or otherTree->right are NULL?

In this code:

delete root; //Will recursively delete all nodes below it.

"Will recursively delete all nodes below it", how so? I don't see a destructor for the class Tree_Node that deletes the left and right branches.

You have a lot of work to fix this up, my friend.

I am aware that I have a lot that needs to be fixed. From what I have seen that is the basic copyTree function for binary tree programs, except most of those programs have the left and right pointers of type Tree_Node rather than type BinaryTree<Node_Type>, so I improvised. Not really sure how to work around the type difference.

Alright so I have done some adjustments and I feel like I am much closer to getting it working. Here is my new copyTree, destroyTree, copy constructor, destructor, and operator= code:

template<class Node_Type>
void BinaryTree<Node_Type>::copyTree(const BinaryTree<Node_Type> otherTree)
{
    if(otherTree.IsEmpty())
        root = NULL;
    else
    {
        root = otherTree.root;        
    }
}

template<class Node_Type>
void BinaryTree<Node_Type>::destroyTree()
{
    if(root != NULL)
    {
        root->left->destroyTree();
        root->right->destroyTree();
        delete root;
    }
    root = NULL;
}



//Copy constructor
template<class Node_Type>
BinaryTree<Node_Type>::BinaryTree(const BinaryTree<Node_Type>& otherTree)
{
    if (otherTree.IsEmpty())
        root = NULL;
    else
        copyTree(otherTree);
}

//Destructor
template<class Node_Type>
BinaryTree<Node_Type>::~BinaryTree()
{
    destroyTree();
}

template<class Node_Type>
const BinaryTree<Node_Type>& BinaryTree<Node_Type>::operator=
      (const BinaryTree<Node_Type>& otherTree)
{
    if (this != &otherTree)     //Avoid self-copy
    {
        if (root != NULL)       //If the binary tree is not empty, destroy it.
            destroyTree();

        if(otherTree.IsEmpty())
            root = NULL;
        else
            copyTree(otherTree);
    }

    return *this;
}

My program, however, is still crashing. See anything that needs to be fixed?

EDIT: Fixed some more code (changed post to reflect it) and now program runs successfully, however with no output. I changed my visit() function (its used to output the values during inorder, preorder, and postorder) to cout << Info() << " " << flush; but still no output. Pretty sure all I have left to fix is this:

template <class Node_Type>
ostream& operator<<(ostream& out, const BinaryTree<Node_Type>* other)
{
    out << other->Info();
    return out;
}

any tips for overloading the << operator?

Edited 4 Years Ago by tvm78

Your copyTree function only performs a "shallow copy", meaning that you just copy the "root" pointer, not the actual tree it points to. You need to do a "deep copy".

In your destroyTree function, you don't check that the left and right pointers are non-NULL before dereferencing them.

I highly suggest you read my tutorial on the topic of writing resource-holding classes in C++.

This article has been dead for over six months. Start a new discussion instead.