java - 如何用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

这是使用 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"));
    }
}