Binary Tree Deep Copy Designer

Question

I am trying to create a deep copy of my binary tree data structure in C ++. The problem is that the code I use seems to only give me a shallow copy (which seems to cause problems with my deconstructor).

the code below is my binary tree copy constructor:

BinaryTreeStorage::BinaryTreeStorage(const BinaryTreeStorage &copytree):root(NULL) { root = copytree.root; copyTree(root); } BinaryTreeStorage::node* BinaryTreeStorage::copyTree(node* other) { //if node is empty (at bottom of binary tree) /* This creates a shallow copy which in turn causes a problem with the deconstructor, could not work out how to create a deep copy. */ if (other == NULL) { return NULL; } node* newNode = new node; if (other ->nodeValue == "") { newNode ->nodeValue = ""; } newNode->left = copyTree(other->left); newNode->right = copyTree(other->right); return newNode; } 

Any help would be greatly appreciated. Thanks

Here is a deconstructor that throws a memory exception (which, in my opinion, is related to the shallow copy that I am doing above)

 BinaryTreeStorage::~BinaryTreeStorage(void) { try { destroy_tree();//Call the destroy tree method delete root;//delete final node } catch(int &error) { cout << "Error Message : " << error << endl; } } void BinaryTreeStorage::destroy_tree() { destroy_tree(root); } void BinaryTreeStorage::destroy_tree(node *leaf) { if(leaf!=NULL) { //Recursively work way to bottom node destroy_tree(leaf->left); destroy_tree(leaf->right); //delete node delete leaf; } } 

Answer 1

You are not doing a deep copy of your root node, but only its children.

Must not be:

 root = copyTree(copytree.root); 

?

EDIT: Also , you kill root twice:

 destroy_tree();//Call the destroy tree method //once here //remove this line delete root;//delete final node 

and

 if(leaf!=NULL) { //Recursively work way to bottom node destroy_tree(leaf->left); destroy_tree(leaf->right); //one more time here delete leaf; } 

If you perform only one of these fixes, the problem will not be resolved.

Answer 2

In fact, I think we can directly use the copy constructor to recursively deep copy the tree. Suppose a class is defined as follows:

 class TreeNode { public: TreeNode() : value(), count(0), left(nullptr), right(nullptr) {} TreeNode(const TreeNode &); ~TreeNode(); TreeNode &operator=(const TreeNode &); // Other members... private: std::string value; int count; TreeNode *left; TreeNode *right; // Note that the valid state for the `left` and `right` pointer is either // `nullptr` or a subtree node. So that we must check these pointers every // time before dereferencing them. }; 

Then copy constructor

 TreeNode::TreeNode(const TreeNode &n) : value(n.value), count(n.count), left(nullptr), right(nullptr) { if (n.left) left = new TreeNode(*n.left); // recursively call copy constructor if (n.right) right = new TreeNode(*n.right); // recursively call copy constructor } 

Recursion will stop on the node sheet, as both of its children are nullptr .

And the destructor too.

 TreeNode::~TreeNode() { delete left; // recursively call destructor on left subtree node delete right; // recursively call destructor on right subtree node } 

When left or right is nullptr , delete do nothing, so the recursion will stop.

You can see the full code here .