c++ – BST destructor aux function being called infinitely for the same node

Im trying to implement a BST with templates, however the destructor is being called for the same node indefinitely. I think the destructor code is fine, however, maybe there is something wrong when the tree is being created, due to the fact that some Node may be pointing to itself.

main.cpp

#include "BSTArbre.hh"
#include <iostream>
using namespace std;


int main() {
    BSTNode<int, int> root(1, {1,2});

    //cout << res << endl;

    BSTArbre<int, int> arbre(root);
    arbre.insert(2, 2);
    arbre.insert(-1, 6);

    arbre.insert(5, 3);


}

BSTNode.hh

#ifndef BSTNODE_HH
#define BSTNODE_HH

#include <list>
#include <algorithm>
using namespace std;

template <class K, class V>
class BSTNode
{
public:
    BSTNode(const K &key) {
        this->key = key;
        this->left = nullptr;
        this->right = nullptr;
        this->parent = nullptr;
    }

    BSTNode(const K &key, const list<V>& values) {
        this->key = key;
        this->values = values;
        this->left = nullptr;
        this->right = nullptr;
        this->parent = nullptr;
    }

    BSTNode(const BSTNode<K, V> &orig) 
    {
        this->key = orig.key;
        this->values = orig.values;
        if (orig.left != nullptr)
        {
            this->left = new BSTNode<K, V>(*orig.left);
            //this->left->setValues()
            left->setParent(this); // Goes back to the new child to set the parent as this
        }

        if (orig.right != nullptr)
        {
            this->right = new BSTNode<K, V>(*orig.right);
            right->setParent(this); // Goes back to the new child to set the parent as this
        }
    };

    virtual ~BSTNode() { }

    /* Modificadors */
    // Declareu-hi aquí els modificadors (setters) dels atributs que manquen
    /* Consultors */
    void setParent(BSTNode<K, V> *parent) { this->parent = parent; }
    void setRight(BSTNode<K,V> *right){this->right = right;}
    void setLeft(BSTNode<K,V>*left){this->left= left;}
    void setValues(const list<V>& v) {this->values = v;}
    
    // Declareu-hi aquí els consultors (getters) dels atributs que manquen
    const K &getKey() const { return key; }
    const list<V> &getValues() const { return this->values; }
    BSTNode<K, V>* getLeft() const {return this->left;}
    BSTNode<K, V>* getRight() const {return this->right;}
    BSTNode<K, V>* getParent() const {return this->parent;}

    /* Operacions */
    bool isRoot() const { return this->parent == nullptr; }
    bool hasLeft() const { return left != nullptr; }
    bool hasRight() const { return right != nullptr; }
    bool isExternal() const { return !hasLeft() and !hasRight(); }
    void insertValue(const V &v) { values.push_back(v); }
    int depth() const
    {
        if (this->isRoot())
            return 0;
        else
            return 1 + parent->depth();
    }

    int height() const
    {
        if (isExternal())
            return 1;
        else
            return 1 + max(left->height(), right->height());
    }
    bool operator==(const BSTNode<K, V> &node) const
    {
        if (key != node.key)
            return false;
        auto it1 = values.begin();
        auto it2 = node.values.begin();

        for (; it1 != values.end() && it2 != node.values.end(); it1++, it2++)
        {
            if (*it1 != *it2)
                return false;
        }

        return it1 == values.end() && it2 == node.values.end();
    }

private:
    K key;
    list<V> values;
    // Afegiu-hi aquí els atributs que manquen
    BSTNode<K, V> *left;
    BSTNode<K, V> *right;
    BSTNode<K, V> *parent;
};

#endif

BSTArbre.hh

#ifndef BSTARBRE_HH
#define BSTARBRE_HH

#include "BSTNode.hh"
#include <iostream>
#include <exception>
using namespace std;

template <class K, class V>
class BSTArbre
{
public:
    BSTArbre() : root(nullptr), _size(0){};
    BSTArbre(const BSTArbre<K, V> &orig)
    {
        this->_size = orig._size;
        // TODO: revisar que este bien
        this->root = new BSTNode<K, V>(orig.root);
    };

    BSTArbre(const BSTNode<K, V>& r)
    {
        // TODO: revisar que este bien
        this->_size = 0;
        this->root = new BSTNode<K, V>(r);
    };

    virtual ~BSTArbre()
    {
        destroyRec(root);
    };

    void destroyRec(BSTNode<K, V> *n)
    {
        if (n != nullptr)
        {
            cout << "Visitando " << n->getKey() << endl;
            destroyRec(root->getLeft());
            destroyRec(root->getRight());
            delete n;
        }
    }

    bool empty() const { return root == nullptr; }
    int size() const { return _size; };
    int height() const
    {
        if (empty())
            return 0;
        return root->height();
    };

    BSTNode<K, V> *insert(const K &k, const V &value) {
        return _insert(this->root, nullptr, k, value, false); 
        // el padre de root es nullptr
    }

    BSTNode<K,V>* _insert(BSTNode<K, V> *r, BSTNode<K, V> *parent,
                    const K &k, const V &value, bool left) {
        if (r == nullptr) {
            r = new BSTNode<K, V>(k);
            r->insertValue(value);
            r->setParent(parent);
            if (!left) {
                parent->setRight(r);
            }
            else parent->setLeft(r);
            return r;
        }
        else {
            if (k > r->getKey()) {
                return _insert(r->getRight(), r, k, value, false);
            }
            else return _insert(r->getLeft(), r, k, value, true);
        }
    }

        

    const list<V> &valuesOf(const K &k) const
    {
        BSTNode<K, V> *n = search(k);
        if (n == nullptr)
            throw invalid_argument("Key not found!");
        else
            return n->getValues();
    }

    void printValues(const list<V> &values) const
    {
        for (auto it = values.begin(); it != values.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }

    void printPreorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printPreorder(n->getLeft());
            printPreorder(n->getRight());
        }
    }

    void printInorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            printInorder(n->getLeft());
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printInorder(n->getRight());
        }
    }
    void printPostorder(const BSTNode<K, V> *n = nullptr) const
    {

        if (n != nullptr)
        {
            printPostorder(n->getLeft());
            printPostOrder(n->getRight());
            cout << n->getKey() << endl;
            printValues(n->getValues());
        }
    }

    BSTNode<K, V>* getRoot() {
        return this->root;
    }


    const list<BSTNode<K, V> *> &getLeafNodes() const;
    void printSecondLargestKey() const;
    void mirrorTree();

protected:
    BSTNode<K, V> *root;
    BSTNode<K, V> *search(const K &k) const
    {
        BSTNode<K, V> *act = root;
        while (act != nullptr)
        {
            if (act->getKey() < k)
            {
                act = act->getLeft();
            }
            else if (act->getKey() > k)
            {
                act = act->getRight();
            }
            else
                return act;
        }
        return nullptr;
    }

private:
    int _size;
    /* Mètodes auxiliars definiu aquí els que necessiteu */
};

#endif

Leave a Comment