Удаление всего из дерева три

Question

Удаление всего из дерева три

Кажется, у меня всегда возникают проблемы, когда я удаляю все узлы из дерева. Я пытаюсь освободить всю память, выделенную при создании дерева Trie.

Я полагаю, чтобы создать функцию remove_all

Достаточно ли удалить только «корень»

что-то вроде этого:

void PrefixStringSet::remove_all(NodePtr node)
{
delete root;

}

Или я должен удалить каждый узел с чем-то вроде этого:

void PrefixStringSet::remove_all(NodePtr node)
{
if(!root)
{
return;
}
remove_all(root->children);delete root;
}

Очевидно, что ни один из них не работает, или я не был бы здесь :).

Другой вопрос. Должен ли я вызывать функцию remove_all в моей основной функции, если мой деструктор реализован следующим образом

PrefixStringSet::~PrefixStringSet()
{
remove_all(root);
}

Или деструктор автоматически удаляет созданные мной деревья / узлы?

редактировать

struct TrieNode
{
TrieNode(bool present = false);
bool is_leaf();

bool present;
TrieNode* children[ALPHABET_SIZE];
};

class PrefixStringSet
{
public:
// Creates an empty prefix string set.
PrefixStringSet();

~PrefixStringSet();

bool insert(string s);

bool contains(string s);

private:
NodePtr root;
void remove_all(NodePtr node);
};
typedef TrieNode* NodePtr;

0

c++removeall trie

Решение

Другие решения

Вы должны написать метод удаления во всех классах, которые вы хотите удалить во время выполнения.
Таким образом, вы можете удалить дерево, не заботясь о сборке мусора.
Использовать указатель легко:

    class a
{
public:
a(){}
~a(){remove();}
init(int v){
var = new int;
*var=v; }
remove(){delete var;}

private:
int *var;
};

class b
{
public:
b(){}
~b(){remove();}
init(int v){
var = new a;
var->init(v); }
remove(){
var->remove();
delete var; }

private:
a *var;
};

Чтобы ответить на ваш вопрос: Нет, удаления root недостаточно.

edit: sry я сделал ошибку в: init (). Я забыл разыменовать указатель.

1

Источник

Accepted Answer

Удаление только root недостаточно: при удалении root вы должны проверить, не являются ли его дочерние элементы пустыми, а если они не пусты, рекурсивно удалить их. C ++ не имеет сборщика мусора, чтобы сделать работу за вас 🙂

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

1