Trie 实施

我试图在Java中实现一个非常简单的Trie，支持3个操作。我希望它有一个插入方法，一个有方法（即是trie中的某个单词），以及一个toString方法以字符串形式返回trie。我相信我的插入工作正常，但事实证明，toString很困难。以下是我到目前为止所拥有的。

三类。

public class CaseInsensitiveTrie implements SimpleTrie {

    //root node
    private TrieNode r;

    public CaseInsensitiveTrie() {
        r = new TrieNode();
    }

    public boolean has(String word) throws InvalidArgumentUosException {
        return r.has(word);
    }

    public void insert(String word) throws InvalidArgumentUosException {
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        CaseInsensitiveTrie t = new CaseInsensitiveTrie();

        System.out.println("Testing some strings");
        t.insert("TEST");
        t.insert("TATTER");
        System.out.println(t.has("TEST"));
    }
}

和节点类

public class TrieNode {

    //make child nodes
    private TrieNode[] c;
    //flag for end of word
    private boolean flag = false;

    public TrieNode() {
        c = new TrieNode[26]; //1 for each letter in alphabet
    }

    protected void insert(String word) {
        int val = word.charAt(0) - 64;

        //if the value of the child node at val is null, make a new node
                //there to represent the letter
        if (c[val] == null) {
            c[val] = new TrieNode();
        }

        //if word length > 1, then word is not finished being added.
        //otherwise, set the flag to true so we know a word ends there.
        if (word.length() > 1) {
            c[val].insert(word.substring(1));
        } else {
            c[val].flag = true;
        }
    }

    public boolean has(String word) {
        int val = word.charAt(0) - 64;
        if (c[val]!=null && word.length()>1) {
            c[val].has(word.substring(1));
        } else if (c[val].flag==true && word.length()==1) {
            return true;
        }

        return false;
    }

    public String toString() { 
        return "";
    }
}

因此，基本上，在创建Trie时，TrieNode被创建为具有26个子级的根。尝试插入时，将在该根节点上调用 insert，该根节点以递归方式在正确的位置创建新节点，并一直持续到单词完成为止。我相信这种方法是正常工作的。

我的 has 函数非常破碎，因为出于某种原因，我必须在括号外使用该 return 语句。我不能将其包含在 else 子句中，否则编译器会抱怨。除此之外，我认为这种方法应该经过一些调整，但我无法为我的生活弄清楚。

toString是我试图解决的野兽，但我扔给它的东西都不起作用，所以我会离开它，直到我解决了有问题。如果我有工作，我也许能够找到一种方法将其重新格式化为toString函数。

int val 的用途 = word.charAt（0） - 64;是因为输入的每个字符串都必须全部大写（我将创建一个字符串格式化函数以确保这一点），因此第一个字母的int值 - 64将是它在数组中的位置。即数组索引 0 是 A，因此 A = 64，A - 64 = 0。B = 65，B - 64 = 1，依此类推。