从 trie 树中删除所有内容

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;

Answer 1

仅删除根是不够的：删除根时，应检查其子项是否不为空，如果不为空，则递归删除它们。 C++ 没有垃圾收集器来为您完成这项工作:)

如果您的remove_all方法位于包装对象的析构函数内，那么您不必单独调用它。

Answer 2

您应该在所有要在运行时删除的类中编写一个remove方法。 因此，您可以删除一棵树，而无需关心垃圾收集。 这样使用指针就很简单了：

    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 是不够的。

编辑：抱歉，我在 a:init() 处犯了一个错误。我忘记取消引用指针。

Answer 3

Solution for me in Cpp:

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

deleteAll(root);