Как обрабатывать недопустимое использование элемента данных non-stati c в реализации класса Tr ie

Question

Я пытался решить вопрос Word Search II на LeetCode, который требует использования Tr ie, чтобы помочь сделать звонки с возвратом более эффективными, и в основном нужно использовать попытки, я пытался реализовать свой собственный tr ie class, но я сталкиваюсь с дорожным блоком в моей функции remove, для нее требуется копия root, но я не уверен, как ее получить. Вот часть, с которой у меня возникают проблемы:

TrieNode* crawl = root в функции remove(string word, TrieNode* crawl = root, int depth = 0)

Ошибка: недопустимое использование non-stati c data member ' Тр ie :: root '

Я не знаю, как правильно это сделать.

TrieNode* remove(string word, TrieNode* crawl = root, int depth = 0) { 
    if(!crawl) return nullptr; 

    if(depth == word.size()) { 
        if(crawl->isLeaf) crawl->isLeaf = false; 
        if(isEmpty(crawl)) { 
            delete crawl; 
            crawl = nullptr; 
        } 
        return crawl; 
    }

    int index = word[depth] - 'a';            
    crawl->arr[index] = remove(word, crawl->arr[index], depth + 1); 

    if(isEmpty(crawl) && crawl->isLeaf == false) { 
        delete crawl; 
        crawl = nullptr; 
    } 

    return crawl; 
} 

Вот как выглядит мой класс Tr ie:

class Trie {
    private:
        TrieNode* root;

    public:            
        Trie() : root(new TrieNode()) {};

        void insert(const string &word) {
            auto crawl = root;
            // does it's thing
        }

        bool search(const string &word) {
            auto crawl = root;
            // does it's thing
        }

        bool isPrefix(const string &word) {
            auto crawl = root;
            // does it's thing
        }


        bool isEmpty(TrieNode* root) { 
            for(int i = 0; i < 26; i++) if(root->arr[i]) return false; 
            return true; 
        } 

        TrieNode* remove(string word, TrieNode* crawl = root, int depth = 0) { 

С этим именем TrieNode:

struct TrieNode {
    bool isLeaf;
    vector<TrieNode*> arr;
    TrieNode() : isLeaf(false), arr(26, nullptr) {};
};

Редактировать: Отдельное спасибо @SPD за предложение об улучшении функции удаления

Answer 1

Альтернативой ответу @ darune будет перегрузка:

TrieNode* remove(const string& word)
{
    return remove(word, root);
}
TrieNode* remove(string word, TrieNode* crawl, int depth = 0) { 
//...

Answer 2

Несколько предложений:

1. вам на самом деле не нужен класс Tr ie, достаточно TrieNode. Все операции вставки / удаления можно переместить в TrieNode, вы, вероятно, сочтете более «естественным» писать функции-члены TrieNode
2. Если вы придерживаетесь существующего дизайна и удаляете само сканирование, а затем crawl = nullptr, Я думаю, вам нужно передать обход по указателю, а не только по указателю.
3. Альтернативой # 2 является удаление сканирования в стеке вызовов. Метод remove () теперь возвращает логическое значение, указывающее, может ли вызывающая сторона безопасно удалить этот узел. Пример кода ниже.
4. Наконец, рассмотрите возможность использования управляемых ptrs, а не raw ptrs. (Возможно, это не имеет значения для упражнения с использованием кода leetcode)

bool remove(string word, TrieNode* crawl, int depth = 0) { 
    if(!crawl) return true; 

    if(depth == word.size()) { 
        if(crawl->isLeaf) crawl->isLeaf = false; 
        return isEmpty(crawl);
    }

    int index = word[depth] - 'a';
    if (remove(word, crawl->arr[index], depth + 1)) {
        // it's empty or nullptr, safe to remove
        delete crawl->arr[index];
        crawl->arr[index] = nullptr; 
    }
    return !crawl->isLeaf && isEmpty(crawl);
} 

Answer 3

Нельзя использовать переменные-члены в качестве аргументов по умолчанию.

Однако вместо:

TrieNode* remove(string word, TrieNode* crawl = root, int depth = 0) { 
//...

Вы можете сделать

TrieNode* remove(string word, TrieNode* crawl = nullptr, int depth = 0) { 
  if (!crawl) {
    crawl = root;
  }
  //...