1
\$\begingroup\$

I implemented a binary tree in the following code. Its node's copy constructor and assignment operator should copy itself and all its descendents. Similarity a node's destructor should delete itself and all nodes descended from it.The print function just prints each node in a new line. How can I pretty-print it? Please point to errors(if any) and suggestions.

#include <iostream>

struct Node
{
    Node(int);
    Node(const Node&);
    Node& operator=(const Node&);
    ~Node();

    Node* left;
    Node* right;
    int value;
};

Node::Node(int v)
:left(nullptr),
right(nullptr),
value(v)
{}

Node::Node(const Node& other)
:left(nullptr),
 right(nullptr),
 value(other.value)
{
    if (other.left != nullptr )
    {
        left = new Node(*other.left);
    }
    if (other.right != nullptr)
    {
        right = new Node(*other.right);
    }
}

Node& Node::operator=(const Node& other)
{
    value = other.value;

    Node * left_orig = left;
    left = new Node(*other.left);
    delete left_orig;

    Node * right_orig = right;
    right = new Node(*other.right);
    delete right_orig;

    return *this;
}

Node::~Node()
{
    if (left != nullptr )
    {
        delete left;
    }
    if (right != nullptr)
    {
        delete right;
    }
}

Node* make_copy(Node* other)
{
    Node * new_node = new Node(*other); // copy constructor invoked
    return new_node;
}


void print(Node* n)
{
    if (n == nullptr)
    {
        return;
    }
    std::cout << n << std::endl;
    print(n->left);
    print(n->right);

}


int main()
{
    Node* n = new Node(1);

    n->left = new Node(2);
    n->right = new Node(3);

    n->left->left = new Node(4);
    n->left->right = new Node(5);

    n->right->left = new Node(6);
    n->right->right = new Node(7);

    print(n);
    auto nc =  make_copy(n);
    print(nc);
}
\$\endgroup\$
  • \$\begingroup\$ 1) I would make three functions for printing: {pre, in, post}-order. 2) Use std::shared_ptr<T> instead of raw pointers - you will not need to implement your own destructor in that case. \$\endgroup\$ – Ryan May 19 '15 at 5:28
  • \$\begingroup\$ An interesting addition would be to try and implement the move assignment operator and move constructor as well. \$\endgroup\$ – Miklas May 19 '15 at 9:38
2
\$\begingroup\$

Assignment operator.

The assignment operator is not 100% exception safe.
You should not modify the current object while you have not yet finished making the copy.

Node& Node::operator=(const Node& other)
{
    value = other.value;

    Node * left_orig = left;
    left = new Node(*other.left);
    delete left_orig;

    // You have modified the left side.
    // If while makeing the copy of the right side
    // it throws an exception (that is caught). Then you
    // have an object that is half one thing (new stuff)
    // and half the other (old stuff on the right).
    Node * right_orig = right;
    right = new Node(*other.right);
    delete right_orig;

    return *this;
}

It should look more like this:

Node& Node::operator=(const Node& other)
{
    Note* newleft  = nullptr;
    Node* newright = nullptr;

    // Do the dangerous stuff in isolation.
    // without changing the chaging the current object.
    try {
        newleft  = new Node(*other.left);
        newright = new Node(*other.right);
    }
    catch(...) {
        // If there was a problem
        // clean up any temporary objects.
        delete newleft;
        delete newright;
        // Then re-throw
        throw;
    }
    // Now perform the exception safe change of state.
    // None of these operations are allowed to throw.
    value = other.value;
    std::swap(left,  newLeft);
    std::swap(right, newRight);

    // Now that the object is in a consistent state.
    // we can delete the old data.
    // Do this last (in other types where the data is not in
    // this can potentially throw).
    delete newLeft;
    delete newRight;

    return *this;
}

Now that looks like a lot of hard work.
There is an easier way to achieve exactly the same affect. You can use the copy and swap idiom.

Node& Node::operator=(Node other)    // Pass by value to generate a copy.
{
    other.swap(*this);               // Swap the state of this and the
                                     // copy we created in `other`
    return *this;
}                                    // destructor of other now
                                     // does the tidy up.

Destructor

Calling delete on a nullptr is valid and does nothing.

Node::~Node()
{
    if (left != nullptr )
    {
        delete left;
    }
    if (right != nullptr)
    {
        delete right;
    }
}

So we can simplify this too.

Node::~Node()
{
    delete left;
    delete right;
}

Why do you need a make_copy?

Node* make_copy(Node* other)
{
    Node * new_node = new Node(*other); // copy constructor invoked
    return new_node;
}

It is quite normal to call the copy constructor directly.

Print statement

You can make the print function a method. Also to make it more versatile you should pass a stream to which you want to print (so it can also print to file). If you want a no argument version just make the stream parameter default to std::cout.

void Node::print(std::iostream& str = std::cin)
{
    std::cout << value << std::endl;
    if (left) {
        left->print(str);
    }
    if (right) {
        right->print(str);
    }
}

This makes it easy to define the output operator for your class.

std::ostream& operator<<(std::ostream& str, Node& data)
{
    data.print(str);
    return *this;
}
\$\endgroup\$
  • \$\begingroup\$ Why are you deleting left and right in assignment operator's catch block? \$\endgroup\$ – sank May 19 '15 at 23:32
  • \$\begingroup\$ Also, why didn't you use std::swap in the copy and swap idiom based assignment operator? \$\endgroup\$ – sank May 19 '15 at 23:45
  • \$\begingroup\$ @sank: Opps. That's wrong. Fixed. \$\endgroup\$ – Martin York May 20 '15 at 20:16
  • \$\begingroup\$ @sank: Normally in the copy and swap idium you would use the class's own swap method (which is also called by a custom swap function). The swap method would use swap to swap the state of the objects internal members. That way you only have one place where the state of the object is swapped (and thus one place to update when you update the state of the object). \$\endgroup\$ – Martin York May 20 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.