Проблема деструктора общего бинарного узла дерева

Question

Я работал над заданием, и теперь я застрял с глючными деструкторами. Я должен создать общее двоичное дерево со всеми обычными функциями-членами и некоторыми специальными операторами. Также есть ограничение: все должно работать итеративно, поэтому на этот раз никаких неприятных рекурсивных хаков.

Очевидно, что с деструктором класса BinTreeNode что-то не так, потому что, если я удаляю узел следующим образом:

BinTreeNode<int> * node = new BinTreeNode<int>();
delete node; 

Я все еще могу получить доступ к его данным:

node->getData(); //should fail miserably

поэтому удаление не имеет никакого эффекта, но я не могу понять, как мне следует исправить деструктор. Мне кажется, что алгоритм должен быть примерно правильным, поэтому я подозреваю, что что-то не так с тем, как я использую указатели, но в этот момент я настолько растерялся, что даже не понимаю свой собственный код.

Код У меня так далеко:

BinTree.h

#ifndef BINTREE_H_
#define BINTREE_H_

#ifndef NULL
#define NULL 0
#endif

#include "BinTreeNode.h"

template <class T>
class BinTree
{
    private:
        BinTreeNode<T> * root;
    public:
        //constructors and destructor
        BinTree():
            root(NULL){}

        BinTree(T data):
            root(new BinTreeNode<T>(data)){}

        ~BinTree();

        //search
        BinTreeNode<T> * search(T data);

        //insert
        bool insert(T data);

        //remove
        bool remove(T data);
};

template <class T>
BinTree<T>::~BinTree()
{
    delete root;
}

template <class T>
BinTreeNode<T> * BinTree<T>::search(T data)
{
    BinTreeNode<T> * node = new BinTreeNode<T>(data);
    BinTreeNode<T> * current = root;

    while (current != NULL)
    {
        if (*current == *node)
        {
            delete node;
            return root;
        }
        else if (*node < *current)
        {
            current = current->getLeft();
        }
        else
        {
            current = current->getRight();
        }
    }
    delete node;
    return NULL;
}

template <class T>
bool BinTree<T>::insert(T data)
{
    BinTreeNode<T> * node = new BinTreeNode<T>(data);
    BinTreeNode<T> * current = root;

    while (current != NULL)
    {
        if (*current == *node)
        {
            delete node;
            return false;
        }
        else if (*node < *current)
        {
            if (current->getLeft() == NULL)
            {
                current->setLeft(node);
                return true;
            }
            else
            {
                current = current->getLeft();
            }
        }
        else
        {
            if (current->getRight() == NULL)
            {
                current->setRight(node);
                return true;
            }
            else
            {
                current = current->getRight();
            }
        }
    }
    return false;
}

#endif

BinTreeNode.h

#ifndef BINTREENODE_H_
#define BINTREENODE_H_

#ifndef NULL
#define NULL 0
#endif

template <class T>
class BinTreeNode
{
    private:
        T data;
        BinTreeNode<T> *left, *right, *parent;
    public:
        //constructors and destructor
        BinTreeNode():
            data(NULL), left(NULL), right(NULL), parent(NULL){}

        BinTreeNode(T data):
            data(data), left(NULL), right(NULL), parent(NULL){}

        ~BinTreeNode();

        //set and get data member
        T getData() const;

        void setData(T data);

        //set and get left and right branches
        BinTreeNode<T> * getLeft() const;

        BinTreeNode<T> * getRight() const;

        void setLeft(BinTreeNode<T> * node);

        void setRight(BinTreeNode<T> * node);

        //set and get parent
        BinTreeNode<T> * getParent() const;

        void setParent(BinTreeNode<T> * node);

        //comparison operators
        bool operator<(const BinTreeNode<T>& node) const;
        bool operator>(const BinTreeNode<T>& node) const;
        bool operator==(const BinTreeNode<T>& node) const;
};

template <class T>
BinTreeNode<T>::~BinTreeNode()
{
    BinTreeNode<T> * current = this;
    BinTreeNode<T> * parent = NULL;
    while (current != NULL)
    {
        parent = current->getParent();
        if (current->getLeft() == NULL)
            current = current->getLeft();
        else if (current->getRight() == NULL)
            current = current->getRight();
        else
        {
            if (parent->getRight() == current)
                parent->setRight(NULL);
            else
                parent->setLeft(NULL);
             current = NULL; // this line (among others) is very suspicious
        }
        current = parent;
    }
}

template <class T>
T BinTreeNode<T>::getData() const
{
    return data;
}

template <class T>
void BinTreeNode<T>::setData(T data)
{
    this->data = data;
}

template <class T>
BinTreeNode<T> * BinTreeNode<T>::getLeft() const
{
    return left;
}

template <class T>
BinTreeNode<T> * BinTreeNode<T>::getRight() const
{
    return right;
}

template <class T>
void BinTreeNode<T>::setLeft(BinTreeNode<T> * node)
{
    node->setParent(this);
    left = node;
}

template <class T>
void BinTreeNode<T>::setRight(BinTreeNode<T> * node)
{
    node->setParent(this);
    right = node;
}

template <class T>
BinTreeNode<T> * BinTreeNode<T>::getParent() const
{
    return parent;
}

template <class T>
void BinTreeNode<T>::setParent(BinTreeNode<T> * node)
{
    parent = node;
}

template <class T>
bool BinTreeNode<T>::operator<(const BinTreeNode<T>& node) const
{
        return this->data < node.data;
}

template <class T>
bool BinTreeNode<T>::operator>(const BinTreeNode<T>& node) const
{
    return this->data > node.data;
}

template <class T>
bool BinTreeNode<T>::operator==(const BinTreeNode<T>& node) const
{
    return this->data == node.data;
}

#endif /* BINTREENODE_H_ */

Answer 1

Ваш BinTreeNode деструктор должен быть просто:

template <class T>
BinTreeNode<T>::~BinTreeNode() {
    delete left;
    delete right;
}

Это рекурсивно вызовет левый и правый деструкторы, освобождая память, выделенную для этих узлов и их дочерних узлов. Это, как следствие, освободит все дерево.

Назначение NULL указателю не освобождает указанную им память.

С другой стороны, что вы упоминаете, что после удаления, эта строка:

node->getData();

Все еще возвращает данные, это совершенно нормально. Удаление освобождает память, но данные, хранящиеся в ней, могут быть доступны некоторое время, пока в этот адрес памяти не будет записано что-то новое. Доступ к уже свободному адресу памяти подразумевает неопределенное поведение.

Кстати, вы должны использовать «0» (без кавычек) в C ++ вместо NULL. Поэтому там нет необходимости использовать #ifndef NULL (...).

РЕДАКТИРОВАТЬ : Я не видел комментарий "нет рекурсии". Вот нерекурсивный алгоритм:

#include <deque>

/* ... */

template <class T>
BinTreeNode<T>::~BinTreeNode() {
    std::deque deq;
    // we're going to delete our children
    deq.push_back(this);
    while(deq.size()) {
        BinTreeNode<T> *ptr = deq.front();
        deq.pop_front();
        if(ptr) {
            deq.push_back(ptr->left);
            deq.push_back(ptr->right);
            // we don't want the child nodes
            // to double delete the children
            ptr->left = 0;
            ptr->right = 0;
            // avoid deleteing ourselves
            if(ptr != this)
                delete ptr;
        }
    }
}

Я не проверял его, но он должен работать.