CODEWITHSUNDEEP
c++trieremoveall
user3265963
user3265963

Reputation: 273

Deleting all from trie tree

I always seem to get in trouble when I'm deleting all nodes from a tree. I am trying to release all the memory I allocated when creating a trie tree.

I am suppose to create a function remove_all

Is it enough to delete just the "root"

something like this:

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

    }

Or do I have to delete each node with something like this:

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


   delete root;
}

Obviously neither of these are working or I wouldn't be here :).

Other question. Do I have to call the remove_all function in my main function if my destructor is implemented like this

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

Or does the destructor automatically delete the trees/nodes I create?

Edit

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;

Upvotes: 0

Views: 6613

Answers (3)

recycle_bin
recycle_bin

Reputation: 11

Solution for me in C++:

void deleteAll(Node* curNode) {
    for (int i = 0; i < 26; i++) {
        if (NULL != curNode->child[i]) {
            deleteAll(curNode->child[i]);
        }
    }
    delete curNode;
}

deleteAll(root);

Upvotes: 0

Brolf
Brolf

Reputation: 81

You should write a remove method in all classes you want to delete at runtime. So you can delete a tree with little care about garbage collection. It's easy to use pointer in this way:

    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;
    };

To answer your question: No, deleting root is not enough.

edit: sry i made a mistake at a:init(). I forgot to derefer the pointer.

Upvotes: 1

Ashalynd
Ashalynd

Reputation: 12573

Deleting only root is not enough: when deleting a root, you should check whether its children aren't empty, and if they are not empty, recursively delete them. C++ doesn't have garbage collector to do the work for you :)

If your remove_all method is within the destructor of the wrapper object, then you don't have to call it separately.

Upvotes: 1

Related Questions