CODEWITHSUNDEEP
c++classtemplatesbinary-search-treemember
Pape Sow Traore
Pape Sow Traore

Reputation: 177

Binary Search Tree copy constructor in C++

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

Answers (3)

SogaBan
SogaBan

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

Pete Becker
Pete Becker

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

Vlad from Moscow
Vlad from Moscow

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>* &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);
    }
}

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

Related Questions