Jak wydrukować wszystkie słowa w Trie?

Question

Próbuję utworzyć implementację Trie w C++. Nie mogę wymyślić, jak wydrukować wszystkie słowa zapisane w Trie.

W ten sposób zaimplementowałem TrieNode.

struct TrieNode{ 
    bool isWord; 
    int data; //Number of times Word Occured 
    TrieNode *Child[ALPHABET_SIZE]; //defined as 26 
}; 

wiem mogę przechowywać pointer do węzła nadrzędnego, Depth-First Search dla wszystkich węzłów, gdzie isWord==True i rekurencyjnie wydrukować każde słowo z tych węzłów.

Ale zastanawiam się, czy istnieje sposób wydrukowania każdego słowa w Trie z moją implementacją TrieNode.

Dzięki za pomoc.

Answer 1

Oto stosunkowo wydajna wersja Konrada Rudolpha, bez zakładania, że ​​dane to postać. Usunąłem również całkowitą pamięć O (n^2) przydzieloną w wersji Konrada kosztem korzystania z std::string&. Chodzi o to, aby przekazać prefiks i zmodyfikować go przy każdej rekursji, przesuwając postacie na koniec i później je wyrzucając, co okazuje się nieco bardziej skuteczne niż kopiowanie tego szaleńczo.

void traverse(std::string& prefix, TrieNode const& node) { 
    if (node.isWord) 
    print(prefix); 

    for (char index = 0; index < ALPHABET_SIZE; ++index) { 
    char next = 'a'+index; 
    TrieNode const* pChild = node.Child[index]; 
    if (pChild) { 
     prefix.push_back(next); 
     traverse(prefix, *pChild); 
     prefix.pop_back(); 
    } 
    } 
} 

Answer 2

Nie potrzebujesz swojego węzła nadrzędnego, Twój kod może łatwo przechodzić przez rekursję. Pseudokod:

void traverse(string prefix, TrieNode const& n) { 
    prefix += static_cast<char>(n.data); 

    if (n.isWord) 
     print(prefix); 

    for (auto const next : n.Child) 
     if (next) 
      traverse(prefix, *next); 
} 

To jest mniej więcej poprawny C++. Po prostu zdefiniuj odpowiednio print.

EDIT W odpowiedzi na komentarz Yakk i swojej wyjaśnienia, oto wersja, która nie zakłada, że ​​data zawiera aktualny znak (złe poślizg z mojej strony!):

void traverse(string const& prefix, TrieNode const& n) { 
    if (n.isWord) 
     print(prefix); 

    for (std::size_t i = 0; i < ALPHABET_SIZE; ++i) 
     if (n.child[i]) 
      traverse(prefix + ('a' + i), *n.child[i]); 
} 

Zostawię bardziej efektywna implementacja odpowiedzi Yakka.

Answer 3

Nie sądzę, że tutaj jest potrzebne słowo. Istnienie wskaźnika dla dzieci będzie wystarczające, aby przemieścić trie dla dostępnych słów w trie. , aby znaleźć słowo, zacznij od korzenia i poszukaj bieżącego znaku w słowie podczas dowolnego kroku rekursywnego.

struct trie { 
    trie *children[ALPHABET_SIZE]; 
}; 


void traversal(trie *&t, string &str) { 
    bool is_seen = false; 
    for(int i = 0; i < ALPHABET_SIZE; i++) { 
     if(t->children[i]) { 
      if(!is_seen) { 
       is_seen = true; 
      } 
      str.push_back(t[i]); 
      traversal(t->children[i], str); 
      str.pop_back(); 
     } 
    } 
    if(!is_seen) { 
     cout << str << "\n"; 
    } 

} 

Answer 4

void traversePrint(TrieNode* sr,char* out,int index) 
{ 
    if(sr!=NULL) 
    { 
     for(int i=0;i<SIZE;i++) 
     { 
      if(sr->child[i]!=NULL) 
      { 
       out[index] = 'a'+i; 
       traversePrint(sr->child[i],out,index+1); 
      } 
     } 
     if(sr->isEnd) 
     { 
      out[index]='\0'; 
      cout << out << endl; 
     } 
    } 
} 

// Wywołanie

char out[MAX_WORD_SIZE]; 
traversePrint(root,out,0);