2

我有一个 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;
    }
}

我只需要一个关于如何去做的解释或一些伪代码。谢谢你的时间。

4

5 回答 5

1

我记得我大学时尝试在控制台上打印树的时候。Trie 在打印 IMO 方面是相同的……这就是我所做的，这也是我建议你做的事情：拿一些纸并在那里画出你的 trie。现在想想你想如何打印 trie。我认为 trie 的组成类似于 N-tree（不是二叉树，而是一棵有很多孩子的树）。除此之外，它是一个递归结构，就像一棵树。所以你真的可以在这里应用深度优先的方法。

假设您要打印这样的 trie（节点 'a' 是根）：

一个

  b

     e

     f

     g
  d

这就像一个包含单词的 trie：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 或其他值，看看会发生什么。

希望这可以帮助。祝你好运！

于 2012-07-29T07:59:22.493 回答
1

这是使用 HashMap 实现 Trie 的完整示例。

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

class TrieNode{

    private char c;
    private Map<Character,TrieNode> children = new HashMap<>();
    private boolean isLeaf = false;

    TrieNode(){

    }

    /**
     * @param c the c to set
     */
    public void setC(char c) {
        this.c = c;
    }

    /**
     * @return the children
     */
    public Map<Character, TrieNode> getChildren() {
        return children;
    }

    /**
     * @return the isLeaf
     */
    public boolean isLeaf() {
        return isLeaf;
    }

    /**
     * @return the c
     */
    public char getC() {
        return c;
    }

    /**
     * @param isLeaf the isLeaf to set
     */
    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }
}

class Trie{

    TrieNode rootNode;

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

    public void insertWord(String word){
        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Map<Character,TrieNode> children = current.getChildren();
            if(children.containsKey(c)){
                current = children.get(c);
            }
            else{
                TrieNode trieNode = new TrieNode();
                children.put(c, trieNode);
                current = children.get(c);
            }
        }
        current.setLeaf(true);
    }

    public boolean searchWord(String word){
        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            Map<Character,TrieNode> children = current.getChildren();
            char c = word.charAt(i);
            if(children.containsKey(c)){
                current = children.get(c);
            }
            else{
                return false;
            }
        }

        if(current.isLeaf() && current!=null){
            return true;
        }
        else{
            return false;
        }
    }

    public void print(TrieNode rootNode,int level, StringBuilder sequence) {
        if(rootNode.isLeaf()){
            sequence = sequence.insert(level, rootNode.getC());
            System.out.println(sequence);
        }

        Map<Character, TrieNode> children = rootNode.getChildren();
        Iterator<Character> iterator = children.keySet().iterator();
        while (iterator.hasNext()) {
            char character = iterator.next();
            sequence = sequence.insert(level, character); 
            print(children.get(character), level+1, sequence);
            sequence.deleteCharAt(level);
        }
    }
}

class TrieImplementation{
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insertWord("Done");
        trie.insertWord("Dont");
        trie.insertWord("Donor");
        trie.insertWord("Sanjay");
        trie.insertWord("Ravi");
        trie.insertWord("RaviRaj");
        TrieNode root = trie.rootNode;
        trie.print(root,0,new StringBuilder(""));
        System.out.println(trie.searchWord("Dont"));
        System.out.println(trie.searchWord("Donor"));
        System.out.println(trie.searchWord("Jay"));
        System.out.println(trie.searchWord("Saviraj"));
        System.out.println(trie.searchWord("RaviRaj"));
        System.out.println(trie.searchWord("Aaviraj"));
    }
}
于 2020-05-11T13:52:30.123 回答
1

这是我刚刚放在一起的一个例子。不是漂亮的打印，只能打印一次 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();
      }
    }
于 2017-06-29T05:14:06.303 回答
0

在处理像 Trie 这样的复合数据结构时，访问者设计模式通常很有用。它使开发人员能够将复合数据结构的遍历与在每个节点检索到的信息分离。

可以使用访问者设计模式来打印 Trie。

于 2012-07-29T08:44:32.000 回答
0

这可能会有所帮助。

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(), "");
于 2017-06-14T10:02:17.167 回答