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

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

Я предполагаю создать функцию 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;

c++ trie removeall
person user3265963    schedule 25.02.2014    source источник
comment
Не могли бы вы опубликовать код для своей структуры/класса NodePtr?   -  person Seyon    schedule 25.02.2014

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Ashalynd    schedule 25.02.2014

arrow_upward
1
arrow_downward

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

    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: извините, я сделал ошибку в: init(). Я забыл разыменовать указатель.

person Brolf    schedule 25.02.2014