java多路查找树代码
时间: 2023-11-26 08:05:42 浏览: 24
下面是一个简单的 Java 多路查找树(Trie)的代码示例:
```java
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return node.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (node.children[c - 'a'] == null) {
return false;
}
node = node.children[c - 'a'];
}
return true;
}
private class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
}
}
}
```
在这个示例中,我们定义了一个 Trie 类,其中包含一个内部 TrieNode 类,用于表示 Trie 树中的节点。TrieNode 类有一个布尔型变量 isEndOfWord,用于指示该节点是否是一个单词的结尾。Trie 类有三个方法:insert、search 和 startsWith。insert 方法用于将单词插入到 Trie 树中,search 方法用于查找单词是否在 Trie 树中,startsWith 方法用于查找是否存在以给定前缀开头的单词。
在 insert、search 和 startsWith 方法中,我们首先将指针 node 初始化为根节点。然后,对于单词中的每个字符,我们检查该字符的子节点是否存在。如果子节点不存在,则创建一个新的 TrieNode,并将其设置为该字符的子节点。最后,我们将指针 node 移动到该字符的子节点。在查找单词时,如果我们到达一个节点,其 isEndOfWord 变量为 true,则说明该单词在 Trie 树中,如果到达的节点没有对应的子节点,则该单词不在 Trie 树中。在查找以给定前缀开头的单词时,我们只需要检查 Trie 树中是否存在以该前缀开头的单词即可。
注意,在这个示例中,我们假设输入的单词只包含小写字母。如果输入包含其他字符,我们需要对代码进行适当的修改。