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

Question

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

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 в стеке?

EDIT:

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 :: стек в ctor?

Answer 1

Вы рушитесь в 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; 

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

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

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

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

Answer 2

Похоже, вы можете что-то удалить дважды.

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

Answer 3

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

Answer 4

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

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