印刷アウトトライ内のすべての単語は、マップ

Question

次のように私は定義されTrieNodeクラスを持っていると実装しました私はこの時点で何かを解決するだろうが）。私は再帰的なソリューションを実装しようとしてきましたが、まともなスタートをすることができませんでした。

EDIT：トライのすべての単語を印刷する方法については、地図ではなく配列として子どもを格納する方法について他の質問があります。

Answer 1

代わりにマップを使用することで、各ノードの26スロットアレイよりも少ないメモリを節約したいと思いますか？しかし、地図の初期建設費がどれほど高いかを見ると、各ノードに1つずつ保存するのではなく、すべてのノードに対して相互マップを使用することができます。

Answer 2

ここで深さ優先再帰トラバーサルです。 生ポインタの使用はお勧めしませんが、あなたが尋ねたので私はここで行いました。 AddTrieによって割り当てられた子ノードは削除しませんでした。実装全体を記述するのではなく、トラバーサルを実証したかったからです。 これを使用する場合は、これらを削除するコードを追加する必要があります。

#include <iostream> 
#include <map> 
#include <string> 

class TrieNode { 
public: 
    std::map<char, TrieNode*> children; 
    bool isLeaf = false; // if node represents end of word 
    int wordCount = 0; // How many times the word appears 
    TrieNode() {} 
}; 

void AddTrie(TrieNode& trie, const char* word) { 
    auto c = *(word++); 
    auto next = trie.children[c]; 
    if(!next) { trie.children[c] = next = new TrieNode; } 
    if(*word) { AddTrie(*next, word); } 
    else  { next->isLeaf = true; } 
} 

void DumpTrie(const TrieNode& trie, std::string word={}) { 
    for(const auto& child : trie.children) { 
     const auto next_word = word + child.first; 
     if(child.second->isLeaf) { std::cout << next_word << '\n'; } 
     DumpTrie(*child.second, next_word); 
} } 

int main() { 
    TrieNode trie; 
    AddTrie(trie, "goodbye"); 
    AddTrie(trie, "hello"); 
    AddTrie(trie, "good"); 
    AddTrie(trie, "goodyear"); 
    DumpTrie(trie); 
} 

すでに試してみましたがどのような出力

good 
goodbye 
goodyear 
hello