Copy constructor for a binary tree C++

Question

I have a Tree class with the following definition:

class Tree {
  Tree();
private:
  TreeNode *rootPtr;
}

TreeNode represents a node and has data, leftPtr and rightPtr.

How do I create a copy of a tree object using a copy constructor? I want to do something like:

Tree obj1;
//insert nodes

Tree obj2(obj1); //without modifying obj1.

Any help is appreciated!

Solution 1

It depends on whether you want a shallow or deep copy. Assuming a deep copy, you need to be able to copy whatever's at the "leaves" hanging off a TreeNode object; so ideally the functionality should be in TreeNode (unless Tree is a friend class of TreeNode that you've designed to be deeply familiar with its implementation, which is often the case of course;-). Assuming something like...:

template <class Leaf>
class TreeNode {
  private:
    bool isLeaf;
    Leaf* leafValue;
    TreeNode *leftPtr, *rightPtr;
    TreeNode(const&Leaf leafValue);
    TreeNode(const TreeNode *left, const TreeNode *right);
  ...

then you could add to it a

  public:
    TreeNode<Leaf>* clone() const {
      if (isLeaf) return new TreeNode<Leaf>(*leafValue);
      return new TreeNode<Leaf>(
        leftPtr? leftPtr->clone() : NULL,
        rightPtr? rightPtr->clone() : NULL,
      );
    }

If Tree is taking care of this level of functionality (as a friend class), then obviously you'll have the exact equivalent but with the node being cloned as an explicit arg.

Solution 2

Two basic options:

If you have an iterator available, you can simply iterate over the elements in the tree and insert each one manually, as R. Pate described. If your tree class doesn't take explicit measures to balance the tree (e.g. AVL or red-black rotations), you'll end up effectively with a linked list of nodes this way (that is, all the left child pointers will be null). If you are balancing your tree, you'll effectively do the balancing work twice (since you already had to figure it out on the source tree from which you're copying).

A quicker but messier and more error-prone solution would be to build the copy top down by doing a breadth-first or depth-first traversal of the source tree structure. You wouldn't need any balancing rotations and you'd end up with an identical node topology.

Solution 3

Here's another example I used with a binary tree. In this example, node and tree are defined in separate classes and a copyHelper recursive function helps the copyTree function. The code isn't complete, I tried to put only what was necessary to understand how the functions are implemented.

copyHelper:

void copyHelper( BinTreeNode<T>* copy, BinTreeNode<T>* originalNode ) {
    if (originalTree == NULL)
        copy = NULL;
    else {
        // set value of copy to that of originalTree
        copy->setValue( originalTree->getValue() );
        if ( originalTree->hasLeft() ) {
            // call the copyHelper function on a newly created left child and set the pointers
            // accordingly, I did this using an 'addLeftChild( node, value )' function, which creates
            // a new node in memory, sets the left, right child, and returns that node. Notice
            // I call the addLeftChild function within the recursive call to copyHelper.
            copyHelper(addLeftChild( copy, originalTree->getValue()), originalTree->getLeftChild());
        }
        if ( originalTree->hasRight() ) { // same with left child
            copyHelper(addRightChild(copy, originalTree->getValue()), originalTree->getRightChild());
        }
    } // end else
} // end copyHelper

copy: returns a pointer to the new tree

Tree* copy( Tree* old ) {
    Tree* tree = new Tree();
    copyHelper( tree->root, oldTree->getRoot() );
    // we just created a newly allocated tree copy of oldTree!
    return tree;
} // end copy

Usage:

Tree obj2 = obj2->copy(obj1);

I hope this helps someone.