Удалить двоичное дерево с помощью стека

Question

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

class Tree
{
private:
    int value_;
    Tree *root_;
    Tree *left_;
    Tree *right_;

    std::stack<Tree*> treeStack;

Функция удаления:

int Tree::eraseTree()
{
    while( !treeStack.empty() )
    {
        Tree *temp = treeStack.top();
        treeStack.pop();
        delete temp;
    }
    if( treeStack.empty() )
        return 1;
    else
        return -1;
}

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

Перед тем, как программа закрывается, я получаю System.AccessViolationException, и неисправный код указывает на файл deque.Конечно, этого не может быть, это должен быть некоторый указатель в моем коде.Это заставляет меня поверить, что я неправильно работаю со стеком или неправильно вставляю в стек.

Что я здесь не так делаю?Я действительно удаляю узлы, когда я вызываю .pop в стеке?

РЕДАКТИРОВАТЬ:

if( !root_ )
{
    root_ = new Tree(val, 0, 0);
    treeStack.push(root_);
    return val;
}

И

Tree *parent = findInsertionPoint(val, root_);
    if( val < parent->value_ )
        parent->left_  = new Tree(val, 0, 0);
    else
        parent->right_ = new Tree(val, 0,0);

    treeStack.push(parent);
    return val;

ГдеЯ помещаю свои элементы в стек.

Дополнительный вопрос: Должен ли std :: stack быть встроен в ctor?

Answer 1

Измените root_*, left_* и right_* на auto_ptrs, чтобы гарантировать их уничтожение.Затем, когда вы пришли, чтобы удалить узел, вы можете просто удалить root_.release ();и все в порядке.Должен спросить, почему вы используете стек.

Answer 2

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

Похоже, что последний фрагмент кода помещает неправильный узел в стек; наверняка это должен быть вновь созданный узел, а не точка вставки? Если вы добавите два узла к родительскому, то родительский узел окажется в стеке дважды и будет удален дважды.

Вероятно, это должно быть больше похоже на

Tree *parent = findInsertionPoint(val, root_);
Tree *child = new Tree(val, 0, 0);
if( val < parent->value_ )
    parent->left_  = child;
else
    parent->right_ = child;

treeStack.push(child);
return val;

Но я бы предпочел предложение DeadMG использовать умные указатели для left_ и right_ (но не делать root_ auto_ptr, если оно используется всеми узлами), и позволить им очистить для тебя. Я не уверен, что вижу точку в стеке; если это ускоряет разрушение дерева, задайте себе два вопроса перед добавлением сложной и подверженной ошибкам оптимизации:

• Достаточно ли медленно, чтобы стоить затраты на разработку / отладку оптимизации?
• стоит ли дополнительных затрат времени выполнения и памяти на построение и поддержание стека вместе с деревом?

И ваш дополнительный вопрос: stack будет встроен в конструктор, но вам не нужно писать никакого кода для этого. Его конструктор по умолчанию будет вызываться автоматически, и это даст вам пригодный для использования пустой стек.

Кроме того, если это не учебное упражнение, вы должны использовать std::multiset, а не изобретать его заново.

Answer 3

Вы получили ошибку в deque , потому что по умолчанию std :: stack использует этот класс как внутренний контейнер. Посмотрите на определение стека:

template<class _Ty, class _Container = deque<_Ty> > class stack;

Answer 4

Звучит так, как будто вы что-то удаляете дважды.

Убедитесь, что удаляемый материал нигде не используется и не удаляется, особенно после вызова метода eraseTree ().