Alle Woerter in Trie ausgeben. Rekursive und iterative Loesung
-
Hi,
ich versuche alle Woerter in einem Trie auszugeben. Dafuer habe ich zwei Funktionen geschrieben: printAllRecursive und printAllIterative.
Die Rekursive funktion gibt das Wort richtig aus, aber die Iterative funktion generiert eine endlos Schleife.
Warum funktioniert die Iterative funktion nicht?Vielen Dank
#include <iostream> #include <string> using namespace std; struct TrieNode{ string word; TrieNode *next[26]; }; void printAllRecursive(TrieNode *r){ for(int i=0;i<26;i++){ if(r->next[i]){ cout << (char)(i+'a'); printAllRecursive(r->next[i]); } } } void printAllIterative(TrieNode *r){ while(r){ for(int i=0;i<26;i++){ if(r->next[i]){ cout << (char)(i+'a'); r = r->next[i]; } } } } int main(){ string s = "testwort"; TrieNode *root = new TrieNode(); TrieNode *r = root; for(char c : s){ char pos = c-'a'; if(!r->next[pos]){ r->next[pos] = new TrieNode(); } r = r->next[pos]; } r->word= s; r = root; cout << "Print all recursive.\n"; printAllRecursive(r); r = root; cout << "\nPrint all iterative.\n"; printAllIterative(r); return 0;
-
Überlege mal, was bei deiner iterativen Version passiert, wenn
r->next[i]
(bzw. besondersr->next[25]
) gleichnull
ist.
Für eine iterative Lösung benötigst du selber einStack
-Objekt (um die rekursive nachzubauen).