如何在Java中打印Trie？

Question

我有一個trie實現，我想打印出我的trie，所以我可以看到它裏面有什麼。優選在深度優先遍歷中，所以這些詞實際上是有意義的。這裏是我的代碼：

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

只是一個解釋如何去做它或一些僞代碼是我所需要的。謝謝你的時間。

Answer 1

我記得大學時代，當我試圖在控制檯上打印樹時。 Trie在打印IMO方面是一樣的......這就是我所做的，這也是我建議你做的事情： 拿一些文件並在那裏繪製你的裁決。 現在想想如何打印trie。 我認爲trie的構成像N-tree（不是一個二元組，而是一個擁有很多孩子的樹）。除了它像樹一樣的遞歸結構。 所以你真的可以在這裏應用深度優先的方法。

讓我們假設你要打印特里這樣的（節點 'a' 是根）：

一個

b 

    e 

    f 

    g 
    d 

這就像一個包含字的線索： ad abe abf abg

所以，你從一個根開始，累積偏移量和遞歸遍歷：

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

與啓動遞歸：

printTrie(root, 0) 

而且你會做

我用2作爲一個常量偏移改變係數，改玩它到3,4或什麼，看看會發生什麼。

希望這會有所幫助。 祝你好運！

Answer 2

visitor設計模式在處理像Trie這樣的複合數據結構時通常很有用。它使開發人員能夠將複合數據結構的遍歷與每個節點檢索到的信息分開。

可以使用訪客設計模式打印Trie。

Answer 3

這可能有幫助。

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

    } 
} 

嘗試調用函數，

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

Answer 4

在這裏，我只是把在一起的例子。不是打印的美女，只能打印一次Trie，但它完成了工作。希望能幫助到你。

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