Deep Copy Constructor for binary tree
-
06-06-2021 - |
سؤال
I am trying to create a deep copy of my binary tree data structure in C++. The problem is the code I am using only seems to be giving 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 ©tree):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 appreciated. Thanks
Here is the deconstructor that throws a memory exception (which i believe is because of the shallow copy i do 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;
}
}
المحلول
You're not performing a deep copy of your root node, only its children.
Shouldn't it be:
root = copyTree(copytree.root);
?
EDIT: In addition, you destroy the 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 only do one of these fixes, the problem won't be solved.
نصائح أخرى
Actually, I think we can directly using the copy constructor to recursively deep copy the tree. Suppose the 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 the copy constructor is
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
}
The recursion will be stopped at the leaf node, since both its two children are nullptr
.
And so does the destructor.
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
will do nothing, so that the recursion will be stopped.
You can see the complete code from here.