Comment imprimer un Trie en Java?

Question

J'ai une implémentation trie et je veux imprimer mon trie afin que je puisse voir ce qu'il y a dedans. Préférable dans une première traversée en profondeur, les mots ont donc un sens. Voici mon code:

package trie; 

public class Trie { 
    public TrieNode root; 

    public Trie(){ 
     root = new TrieNode(); 
    } 

    /* 
    public Trie(char c){ 
     TrieNode t = new TrieNode(c); 
     root = t; 
    }*/ 

    public void insert(String s, int phraseNb){ 
     int i = 0; 
     TrieNode node = root; 
     char[] string = s.toCharArray(); 
     TrieNode child = null; 

     while(i < string.length){ 
      child = node.getChild(string[i]); 
      if(child == null){ 
       child = new TrieNode(string[i]); 
       node.addChild(child); 
      } 
      else{ 
       node = child; 
      } 
      i++; 
     } 

     node.endOfWord(); 
     node.setNb(phraseNb); 
    } 

    public int[] search(char[] c){ 
     TrieNode node = root; 
     for(int i = 0; i < c.length-1; i++){ 
      node = root; 
      int s = 0; 
      while(i+s < c.length){ 
       TrieNode child = node.getChild(c[i + s]); 
       if(child == null){ 
        break; 
       } 
       if(child.isWord()){ 
        return new int[] {i, s+1, node.getNb()}; 
       } 
       node = child; 
       s++; 
      } 
     } 
     return new int[] {-1, -1, -1}; 
    } 

    public void print(){ 

    } 
} 

package trie; 

import java.io.*; 
import java.util.*; 

public class TrieNode { 
    private boolean endOfWord; 
    private int phraseNb; 
    private char letter; 
    private HashSet<TrieNode> children = new HashSet<TrieNode>(); 

    public TrieNode(){} 

    public TrieNode(char letter){ 
     this.letter = letter; 
    } 

    public boolean isWord(){ 
     return endOfWord; 
    } 

    public void setNb(int nb){ 
     phraseNb = nb; 
    } 

    public int getNb(){ 
     return phraseNb; 
    } 

    public char getLetter(){ 
     return letter; 
    } 

    public TrieNode getChild(char c){ 
     for(TrieNode child: children){ 
      if(c == child.getLetter()){ 
       return child; 
      } 
     } 
     return null; 
    } 

    public Set<TrieNode> getChildren(){ 
     return children; 
    } 

    public boolean addChild(TrieNode t){ 
     return children.add(t); 
    } 

    public void endOfWord(){ 
     endOfWord = true; 
    } 

    public void notEndOfWord(){ 
     endOfWord = false; 
    } 
} 

Juste une explication sur la façon de s'y prendre ou un pseudo code est tout ce dont j'ai besoin. Merci pour votre temps.

Answer 1

Je me souviens de l'époque où j'ai essayé d'imprimer l'arbre sur la console. Trie est le même en termes d'impression IMO ... C'est ce que j'ai fait et c'est ce que je vous suggère de faire aussi: Prenez du papier et dessinez votre trie là. Maintenant, pensez comment voulez-vous imprimer le trie. Je pense que trie est composé comme N-tree (pas un binaire mais un arbre qui a beaucoup d'enfants). En outre, c'est une structure récursive comme un arbre. Donc, vous pouvez vraiment appliquer ici la première approche en profondeur.

laisse supposer que vous voulez imprimer une structure arborescente comme celui-ci (noeud 'a' est une racine):

un

b 

    e 

    f 

    g 
    d 

c'est comme un Trie qui contient des mots: annonce abe abf abg

Donc, vous commencez avec une racine, accumuler le décalage et traversent récursive:

printTrie(Node node, int offset) { 
    print(node, offset) 
    // here you can play with the order of the children 
    for(Node child : node.getChildren()) { 
      printTrie(child, offset + 2) 
    } 
} 

Démarrez votre récursion avec:

printTrie(root, 0) 

Et vous allez être

Je l'ai utilisé 2 comme une constante de jouer avec le coefficient de modifier le décalage, le changement à 3,4 ou peu importe et voir ce qui se passe.

Espérons que cela aide. Bonne chance!

Answer 2

Le motif de conception visitor est souvent utile lorsqu'il s'agit de structures de données composites telles que Trie. Il permet à un développeur de découpler la traversée de la structure de données composite des informations récupérées sur chaque noeud.

On pourrait utiliser le modèle de conception de visiteur pour imprimer le Trie.

Answer 3

Cela pourrait aider.

public void printTrie(TrieNode node,String s) { 
    String strSoFar = s; 
    strSoFar += String.valueOf(node.c); 
    if(node.isLeaf) 
    { 
     System.out.println(strSoFar); 
     return; 
    } 
    else 
    { 
     Stack<TrieNode> stack = new Stack<TrieNode>(); 
     Iterator<TrieNode> itr = node.children.values().iterator(); 
     while(itr.hasNext()) 
     { 
      stack.add(itr.next()); 
     } 
     while(!stack.empty()){ 
      TrieNode t = stack.pop(); 
      printTrie(t,strSoFar); 
     } 

    } 
} 

Essayez d'appeler la fonction,

trieObject.printTrie(trieObject.getRoot(), ""); 

Answer 4

Voici un exemple que je viens de jeter ensemble. Pas l'impression de pretties et peut seulement imprimer le Trie une fois mais il fait le travail. J'espère que cela aide.

import java.util.*; 

    public class Trie 
    { 
     static TrieNode root = new TrieNode(); 
     static char endMarker = '?'; 
     public static void main(String[] args) 
     { 
     System.out.println(checkPresentsAndAdd("test")); 
     System.out.println(checkPresentsAndAdd("taser")); 
     System.out.println(checkPresentsAndAdd("tester")); 
     System.out.println(checkPresentsAndAdd("tasters")); 
     System.out.println(checkPresentsAndAdd("test")); 
     System.out.println(checkPresentsAndAdd("tester")); 

     printTrie(root); 
     } 

     public static boolean checkPresentsAndAdd(String word) 
     { 
     TrieNode node = root; 
     for(int i = 0; i < word.length(); i++) 
     { 
      char c = word.charAt(i); 
      if(node.checkIfNeighbor(c)) 
      { 
       node = node.getNeighbor(c); 
      } 
      else 
      { 
      node.addNeighbor(c); 
      node = node.getNeighbor(c); 
      } 
     } 

     boolean nord = false; 
     if(!node.checkIfNeighbor(endMarker)) 
     { 
      nord = true; 
      node.addNeighbor(endMarker); 
     } 

     return nord; 
     } 

     public static void printTrie(TrieNode node) 
     { 

     if(node == null || node.visited) 
      return; 

     LinkedList<TrieNode> q = new LinkedList<TrieNode>(); 

     System.out.println(node); 
     node.visited = true; 
     q.add(node); 

     while (!q.isEmpty()) 
     { 
      TrieNode x = q.removeFirst(); 
      for(Map.Entry<Character,TrieNode> i : x.neighbors.entrySet()) 
      { 
       if(i.getValue().visited == false) 
       { 
        System.out.println(i); 
        i.getValue().visited = true; 
        q.add(i.getValue()); 
       } 
      } 
     } 
     } 
    } 

    class TrieNode 
    { 
     Map<Character, TrieNode> neighbors = new HashMap<Character, TrieNode>(); 

     boolean visited = false; 
     public TrieNode(){} 

     public boolean checkIfNeighbor(char c) 
     { 
     return neighbors.containsKey(c); 
     } 

     public TrieNode getNeighbor(char c) 
     { 
     if(checkIfNeighbor(c)) 
     { 
      return neighbors.get(c); 
     } 

     return null; 
     } 

     public void addNeighbor(char c) 
     { 
     TrieNode node = new TrieNode(); 
     neighbors.put(c, node); 
     } 

     public String toString() 
     { 
     StringBuilder sb = new StringBuilder(); 
     sb.append("Node:[neighbors: "); 
     sb.append(neighbors); 
     sb.append("]\n"); 

     return sb.toString(); 
     } 
    }