Copy constructor question Lippman

Question

Hi, I was trying to solve a copy ctro qs given in lipman n not sure If i got it right. Since the class has pointers to itself it confused me a bit. Here is the code

#include <iostream>
#include <string>

using namespace std;

class BinStrTreeNode{

      public:
         BinStrTreeNode(const string& val):_val(val){ 
              _leftchild = new BinStrTreeNode("nup");
              _rightchild = new BinStrTreeNode("rup");
              cout << "ctor" << endl;
         };
         BinStrTreeNode(const BinStrTreeNode&);
     private:
         string _val;
         BinStrTreeNode *_leftchild;
         BinStrTreeNode *_rightchild;
};

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs):_val(rhs._val){
    cout << "copy ctor" << endl;
    _leftchild = new BinStrTreeNode(*(rhs._leftchild));
    _rightchild = new BinStrTreeNode(*(rhs._rightchild));
}

And it gives segementation fault. I know i need to define a dtor too but first I need to get this right. How should i define a copy ctor, assignment operator for a class like this?

Thanks

Answer 1

Your copy constructor is recursive. You might have exhausted memory or had new throw an out of memory exception or, most likely, dereferenced a null pointer in one of the copy constructor invocations.

Answer 2

Header Files

First, break your constructor declarations into a header file and then define them in a separate CPP file.

Copy Constructor Recursive Problem

Your copy constructor is recursive in that it keeps calling itself until the program runs out of available memory. This is bad.

Cloning (Copying) Tree

Based on the comments below, it seems you need to clone your tree. See example:

BinStrTreeNode* BinStrTreeNode::clone()
{
    if (BinStrTreeNode* tmp = new BinStrTreeNode)
    {
        tmp->value = value;
        if (leftchild) tmp->leftchild = leftchild->clone();
        if (rightchild) tmp->rightchild = rightchild->clone();
        return tmp;
    }
    return 0;
}

Tree Explanation

If I remember correctly from my college Computer Science days, I maintained a global copy of tree and "tagged" each node as either left or right. That way when I mapped it graphically in Qt, I knew how to display the tree.

You are going to have to maintain a left and right node for the tree also.

To get your code to work, I modified it as follows (ignore the TForm stuff, I just used a different IDE):

Unit1.Cpp
---------
#include "Unit1.h"
#include "File1.h"

//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
    BinStrTreeNode *root;
    root = NULL;
}
//---------------------------------------------------------------------------

File1.cpp
---------
#include <iostream>
#include <string>
#include "File1.h"

    using namespace std;

    BinStrTreeNode::BinStrTreeNode(string val) {
           value = val;
           leftchild = NULL;
           rightchild = NULL;
           cout << "ctor" << endl;
    }

File1.h
-------
#include <iostream>
#include <string>

using namespace std;

class BinStrTreeNode{

            public:
                    BinStrTreeNode(string val);

            private:
                    string value;
                    BinStrTreeNode leftchild;
                    BinStrTreeNode rightchild;
};

A good example of a binary sort tree can be defined like this:

struct TreeNode {
         // An object of type TreeNode represents one node
              // in a binary tree of strings.

         string item;      // The data in this node.
         TreeNode left;    // Pointer to left subtree.
         TreeNode right;   // Pointer to right subtree.

         TreeNode(string str) {
                // Constructor.  Make a node containing str.
            item = str;
            left = NULL;
            right = NULL;
         }

};  // end struct Treenode

You then have to create the root and everything is added from there:

TreeNode *root;  // Pointer to the root node in the tree.
root = NULL;     // Start with an empty tree.

Then if you want to add an item to the binary sort tree, then you do something like this:

void treeInsert(TreeNode *&root, string newItem) {
              // Add the item to the binary sort tree to which the parameter
              // "root" refers.  Note that root is passed by reference since
              // its value can change in the case where the tree is empty.
          if ( root == NULL ) {
                 // The tree is empty.  Set root to point to a new node containing
                 // the new item.  This becomes the only node in the tree.
             root = new TreeNode( newItem );
                     // NOTE:  The left and right subtrees of root
                     // are automatically set to NULL by the constructor.
                     // This is important!
             return;
          }
          else if ( newItem < root->item ) {
             treeInsert( root->left, newItem );
          }
          else {
             treeInsert( root->right, newItem );
          }
}  // end treeInsert()

Answer 3

Your main problem is that both the constructors infinitely recurse:

• Your constructor will recurse until you get a stack overflow, or until new throws a std::bad_alloc.
• Your copy constructor will recurse until you get a stack overflow, or until it encounters an invalid leftchild or right child, when it will segfault.

Your underlying problem is that your recursive functions don't have a terminating condition. All functions, including constructors, need a code path that doesn't recurse.

Answer 4

you got it basically correct.
You just forgot to check for NULL pointers.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild(NULL)
    ,_rightchild(NULL)
{
    cout << "copy ctor" << endl;
    if (rhs._leftchild  != NULL) {_leftchild  = new BinStrTreeNode(*(rhs._leftchild));}
    if (rhs._rightchild != NULL) {_rightchild = new BinStrTreeNode(*(rhs._rightchild));}
}

Note trees will not point to a node higher (or self) in the tree (as that would no longer be a tree it would be a graph). If your code is a graph then you need to re-write this so that you do a graph copy which is a lot more complex as you need to track which nodes have been copied in a map.

Though personally I would take it a step further and do everything in the initializer list:
Though I would just say that this is a personal preference.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild ((rhs._leftchild  == NULL)?NULL:new BinStrTreeNode(*(rhs._leftchild)))
    ,_rightchild((rhs._rightchild == NULL)?NULL:new BinStrTreeNode(*(rhs._rightchild)))
{
    cout << "copy ctor" << endl;
}

Cycle trees (AKA Graphs)

Lets start from scratch here:
In this situation we need to track each node we create. Then when a pointer points back a node that has already been copied we use the copied node rather than creating a new one (otherwise we end up in a recursive nightmare following the loop round and around and around).

typedef std::map<BinStrTreeNode*,BinStrTreeNode*>   CopyMap;
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
{
    CopyMap    copyMap;
    copyMap[&rhs] = this;

    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}

private:
BinStrTreeNode* BinStrTreeNode::copyGraph(BinStrTreeNode* node,CopyMap& copyMap)
{
    if (node == NULL)
    {    return NULL;
    }

    if (copyMap[node] != NULL)
    {    return copyMap[ndoe];
    }

    return new BinStrTreeNode(*node, copyMap);
}
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs, CopyMap& copyMap)
    :_val(rhs._val)
{
    copyMap[&rhs] = this;
    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}