我正在尝试用 Java 实现一个非常简单的 Trie，它支持 3 个操作。我希望它有一个 insert 方法、一个 has 方法（即 trie 中的某个单词）和一个 toString 方法以字符串形式返回 trie。我相信我的插入工作正常，但 has 和 toString 被证明是困难的。这是我到目前为止所拥有的。
trie 类。
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，依此类推。