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. besonders r->next[25]) gleich null ist.
    Für eine iterative Lösung benötigst du selber ein Stack-Objekt (um die rekursive nachzubauen).


Anmelden zum Antworten