Wie alle Wörter in einem Trie gedruckt werden?

Question

Ich versuche eine Trie Implementierung in C++ zu erstellen. Ich kann nicht herausfinden, wie alle Wörter gedruckt werden, die in Trie gespeichert werden.

Dies ist, wie ich die TrieNode implementiert habe.

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

Ich weiß, dass ich ein pointer zu dem übergeordneten Knoten speichern könnte, Tiefensuche für alle Knoten in dem isWord==True und rekursiv jedes Wort aus diesen Knoten drucken.

Aber ich frage mich, gibt es eine Möglichkeit, jedes Wort in der Trie mit meiner Implementierung eines TrieNode auszudrucken.

Danke für jede Hilfe.

Answer 1

Hier ist eine einigermaßen effiziente Version von Konrad Rudolph, ohne davon auszugehen, dass Daten ein Zeichen sind. Ich entfernte auch den O (n^2) Gesamtspeicher, der in Konrads Version zugewiesen wurde, auf Kosten von std::string&. Die Idee besteht darin, das Präfix weiterzuleiten und es bei jeder Rekursion zu modifizieren, indem man die Zeichen auf das Ende drückt und es anschließend wieder öffnet, was schließlich effizienter ist, als es irre zu kopieren.

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

Sie benötigen Ihren Elternknoten nicht, Ihr Code passt sich durch Rekursion leicht dem Traversal an. Pseudocode:

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

Dies ist mehr oder weniger gültig C++. Definieren Sie einfach print entsprechend.

EDIT Als Reaktion auf Yakk Kommentar und Ihre Klarstellung, hier ist eine Version, die das aktuelle Zeichen nicht davon ausgehen, dass data enthält (schlechten Beleg auf meiner Seite!):

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

Ich werde verlassen die effizientere Umsetzung zu Yakks Antwort.

Answer 3

Ich glaube nicht, dass hier ein Wort benötigt wird. Die Existenz des Zeigers für Kinder reicht aus, um den Trie für verfügbare Wörter im Trie durchqueren zu können. Um ein Wort zu finden, beginnen Sie mit der Wurzel und suchen Sie während eines rekursiven Schritts nach dem aktuellen Zeichen innerhalb des Wortes.

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

// Aufruf

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