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