Разрушитель бинарного дерева поиска

Question

Работаю над реализацией своего собственного BST на C ++ для опыта работы с такими структурами.

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

Чтобы компенсировать это, я создал вспомогательную функцию - однако это приводит к появлению нерешенной внешней ошибки в строке 'delete n'.Любые советы?

Код:

void BinSearchTree::Clear(tNode* n)
{
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    n = NULL;
    size--;
}

Answer 1

Вы можете иметь рекурсивный деструктор;то, что вы не можете сделать, это удалить один и тот же объект дважды.

Типичный способ удаления дерева в C ++ может выглядеть примерно так:

BinSearchTree::~BinSearchTree()
{
   delete _rootNode;  // will recursively delete all nodes below it as well
}

tNode::~tNode()
{
   delete left;
   delete right;
}

Относительно неразрешенной внешней ошибки -эта ошибка выдается при попытке скомпилировать / связать программу?Если это так, то это, вероятно, потому, что код для класса tNode (и в частности деструктора tNode, если вы его объявили) не существует или не компилируется в ваш проект.

Answer 2

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

Однако у вас есть вторая ошибка:Вы, кажется, верите, что установка n на ноль делает то, чего не делает.Значение указателя n передается по значению, а не по ссылке, так что изменение его значения (например, путем присвоения NULL) не имеет никакого эффекта после возврата функции.

Это, вероятно, приведет к ошибкам при очистке дерева иожидать, что указатель корневого узла был установлен в NULL, когда он остается висящим указателем на освобожденную память.Результатом будет ошибка времени выполнения, а не ошибка компоновщика.

void BinSearchTree::Clear(tNode **N)
{
    tNode * n = *N;
    if (n->left != NULL)
        Clear(n->left);
    if (n->right != NULL)
        Clear(n->right);
    delete n;
    *N = NULL;
    size--;
}

Будет делать то, что вы ожидаете.

Answer 3

Проблема в том, что в вашем классе вы, вероятно, объявили, что структура узла имеет собственный деструктор, но вы не предоставляете его, поэтому во время компиляции компилятор жалуется, что кусок отсутствует.

Если вам больше не нужен пользовательский код в деструкторе, вы можете просто удалить деструктор из объявления структуры, и ваша программа будет хорошо скомпилирована.

Обратите внимание, однако, что вообще нет проблем с деструктором для уничтожения дочерних узлов (см. Ответ Брендана Лонга). Если вы столкнулись с проблемами при попытке решить проблему, с которой вы столкнулись, я должен заняться чем-то другим.

Answer 4

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

Все, что вам нужно, это:

~BinSearchTree() {
    delete left;
    delete right;
}

delete назовет их деструкторами.

Примечание: delete NULL совершенно безопасно, не имеет никакого эффекта .

Answer 5

Как насчет автоматизации:

class BinSearchTree
{
    std::auto_ptr<tNode>   left;
    std::auto_ptr<tNode>   right;

    BinSearchTree(BinSearchTree const&);
    BinSearchTree& operator=(BinSearchTree const&); // private
};

Теперь уничтожение происходит автоматически. : -)

Answer 6

Вы также можете использовать рекурсию, вам просто нужно изменить заголовок функции на:

void remove(node*& root) 

и будет работать.