Come stampare tutte le parole memorizzate in un albero, dove è stato implementato trie usando Hashmap in Java?

Question

Voglio stampare o recuperare tutte le parole memorizzate in Trie Data Structure. Questo perché voglio calcolare la distanza tra una parola errata e una parola nel dizionario. Quindi stavo pensando di recuperare ogni parola da Trie e calcolare Modifica distanza. Ma non sono in grado di recuperare. Voglio qualche frammento di codice per questo. Ecco come ho implementato il Trie usando HashMap in Java

Ora dimmi come scrivere codice per stampare tutte le parole memorizzate in Trie. Qualsiasi aiuto è molto apprezzato

TrieNode.java

package triehash; 
import java.io.Serializable; 
import java.util.HashMap; 

public class TrieNode implements Serializable { 

HashMap<Character, HashMap> root; 

public TrieNode() { 
    root = new HashMap<Character, HashMap>(); 
    } 
} 

TrieDict.java

package triehash; 

import java.io.FileOutputStream; 
import java.io.ObjectOutputStream;; 
import java.io.Serializable; 
import java.util.HashMap; 
import java.io.Serializable; 

public class TrieDict { 
public TrieNode createTree() 
{ 
    TrieNode t = new TrieNode(); 
    return t; 
} 

public void add(String s, TrieNode root_node) { 
    HashMap<Character, HashMap> curr_node = root_node.root; 
    s = s.toLowerCase(); 
    for (int i = 0, n = s.length(); i < n; i++) { 
     Character c = s.charAt(i); 
     if (curr_node.containsKey(c)) 
      curr_node = curr_node.get(c); 
     else { 
      curr_node.put(c, new HashMap<Character, HashMap>()); 
      curr_node = curr_node.get(c); 
     } 
    } 
    curr_node.put('\0', new HashMap<Character, HashMap>(0)); // term 
    } 

public void serializeDict(TrieNode root_node) 
{  
    try{ 
     FileOutputStream fout = new FileOutputStream("/home/priya/NetBeansProjects/TrieHash/dict.ser"); 

    ObjectOutputStream oos = new ObjectOutputStream(fout); 
    oos.writeObject(root_node); 
    oos.close(); 
    System.out.println("Done"); 

    }catch(Exception ex){ 
     ex.printStackTrace(); 
    } 
} 

public void addAll(String[] sa,TrieNode root_node) { 
    for (String s: sa) 
     add(s,root_node); 
} 

public static void main(String[] args) 
{ 
    TrieDict td = new TrieDict(); 
    TrieNode tree = td.createTree(); 

    String[] words = {"an", "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"}; 
    for (int i = 0; i < words.length; i++) 
     td.add(words[i],tree);  
    td.serializeDict(tree); /* seriliaze dict*/ 
} 
} 

Answer 1

primo luogo, vale la pena notare che il tipo dichiarato della variabile di istanza è un root un po 'strano (In particolare, il tipo di valore di HashMap<Character,HashMap> esclude alcuni dei generici che preferiresti usare). Il codice seguente dovrebbe funzionare, ma in questo modo riceverai alcuni avvisi. Potresti provare a rielaborare il codice per utilizzare invece il tipo HashMap<Character,TrieNode>. Scusa se è pedante. :)

Prova questa, aggiunto come metodi per TrieNode:

public Set<String> computeWords() { 
    Set<String> result; 

    if(root.size() == 0) 
     result = new HashSet<String>(); 
    else 
     result = computeWords(root, ""); 

    return result; 
} 

protected static Set<String> computeWords(HashMap tree, String prefix) { 
    Set<String> result=new HashSet<String>(); 

    if(tree.size() == 0) 
     result.add(prefix); 
    else 
     for(Object o : tree.keySet()) { 
      Character c=(Character) o; 
      prefix = prefix+c; 
      result.addAll(computeWords((HashMap) tree.get(c), prefix)); 
      prefix = prefix.substring(0, prefix.length()-1); 
     } 

    return result; 
} 

Per un dato oggetto TrieNodet, t.computeWords() restituirebbe l'insieme di tutte le parole parole codificate in t.

Credo che questo risponda alla domanda che stavi cercando di fare. Tuttavia, per rispondere alla domanda, come indicato nell'intestazione, devi stampare tutte le parole per lo stesso t in questo modo:

for(String word : t.computeWords()) 
    System.out.println(word); 

Inoltre, questo sicuramente non è la più efficace attuazione, soprattutto perché creiamo una mazzo di oggetti HashSet in computeWords(HashMap,String), ma dovrebbe funzionare!

MODIFICA: questo codice presuppone anche la chiusura di parole con uno HashMap vuoto. Se si terminano le parole con null, è necessario aggiornare il controllo if(tree.size() == 0) nel metodo static con if(tree == null). Scusa, avrei dovuto chiamarlo.

MODIFICA: Spiegato come stampare tutte le parole, nel caso in cui non fosse chiaro.

MODIFICA: risolto caso vuoto trie.