用Java语言实现Trie树的数据设计
时间: 2023-02-25 07:49:41 浏览: 65
实现Trie树的数据设计的Java代码如下:
class TrieNode {
private TrieNode[] children;
private boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
public TrieNode[] getChildren() {
return children;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
int index = currentChar - 'a';
if (node.getChildren()[index] == null) {
node.getChildren()[index] = new TrieNode();
}
node = node.getChildren()[index];
}
node.setEnd();
}
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
int index = currentChar - 'a';
if (node.getChildren()[index] == null) {
return false;
}
node = node.getChildren()[index];
}
return node.isEnd();
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char currentChar = prefix.charAt(i);
int index = currentChar - 'a';
if (node.getChildren()[index] == null) {
return false;
}
node = node.getChildren()[index];
}
return true;
}
}
此代码中的TrieNode类代表Trie树的节点,包含26个子节点和一个布尔变量isEnd,用于标识当前节点是否为单词的结尾。Trie类定义了Trie树,包含三个主要操作:插入单词、搜索单词和搜索单词前缀。