Reputation: 177
I am trying to write a copy constructor for my binary search but it is giving a segmentation fault for some reason.Here is my implementation:
template <typename T>
BTree<T>::BTree(const BTree<T>& other)
{
copy_helper(this->root, other.root);
}
template <typename T>
void BTree<T>::copy_helper(Node<T>* copy_to, const Node<T>* copy_from) const
{
if(copy_from == NULL){
copy_to = NULL;
} else{
copy_to = new Node<T>;
copy_to->value = copy_from->value;
copy_helper(copy_to->left, copy_from->left);
copy_helper(copy_to->right, copy_from->right);
copy_helper(copy_to->parent, copy_from->parent);
}
}
Upvotes: 1
Views: 12712
Reputation: 15
For copy constructor (or assignment operator overload) for AVL Trees having 'parent' as one of the node pointer, you 'll need two separate steps: First you deep copy the contents of all nodes (without touching the pointers), secondly, you pass the root of the newly constructed tree to a function that adjusts the pointers (in a recursive fashion).
E.g.
structure of node:
struct tree_node
{
int key;
std::string element;
int balanceFactor;
int height;
tree_node* left;
tree_node* right;
tree_node* parent;
tree_node() : key(0), element(""), balanceFactor(0), height(0), left(nullptr), right(nullptr), parent(nullptr) {}
explicit tree_node(int key, std::string element, tree_node* parent) : key(key), element(element), balanceFactor(0), height(0), left(nullptr), right(nullptr), parent(parent) {}
explicit tree_node(int key, std::string element) : key(key), element(element), balanceFactor(0), height(0), left(nullptr), right(nullptr), parent(nullptr) {}
void copyContent(tree_node* rhs)
{
//copies only the items/data/information
//doesn't touch the poinetrs
this->key = rhs->key;
this->element = rhs->element;
this->height = rhs->height;
this->balanceFactor = rhs->balanceFactor;
}
};
Now, here is the copy c-tor:
AVLTree::AVLTree(const AVLTree& rhs)
{
this->ROOT = deepCopyContent(rhs.ROOT);
adjustPointers(this->ROOT);
this->numberOfNodes = rhs.numberOfNodes;
}
And the functions:
AVLTree::Node AVLTree::deepCopyContent(AVLTree::Node X)
{
if (!X) return nullptr;
else
{
Node _creation_ = new tree_node();
_creation_->copyContent(X);
_creation_->left = deepCopyContent(X->left);
_creation_->right = deepCopyContent(X->right);
return _creation_;
}
}
void AVLTree::adjustPointers(AVLTree::Node X)
{
if (!X) return;
else
{
if (X->left) X->left->parent = X;
if (X->right) X->right->parent = X;
adjustPointers(X->left);
adjustPointers(X->right);
}
}
Hope, this helps.
Upvotes: 1
Reputation: 76523
If the member named parent
is what its name suggests, copy_helper(copy_to->parent, copy_from->parent)
will do terrible things. In particular, it will call copy_helper
to copy the two children of the parent, and those copies will each copy their parent (again), and that copy will copy the two children (again), ad infinitum or until it crashes.
Copy down the tree only. Don’t go back up.
Upvotes: 2
Reputation: 311186
The problem is that the pointer cooy_to
is a local variable of the method copy_helper.
As result changing the variable copy_to
does not change the original pointer this->root
.
You should pass the argument either by refernce or indirecdtly through a pointer. For example
void BTree<T>::copy_helper(Node<T>* ©_to, const Node<T>* copy_from) const
{
if(copy_from == NULL){
copy_to = NULL;
} else{
copy_to = new Node<T>;
copy_to->value = copy_from->value;
copy_helper(copy_to->left, copy_from->left);
copy_helper(copy_to->right, copy_from->right);
copy_helper(copy_to->parent, copy_from->parent);
}
}
In fact the data method should be declared either as a static function or a member function with one parameter const Node<T>* copy_from
.
Upvotes: 3