用java写一段 trie树代码
时间: 2023-09-21 10:06:28 浏览: 55
### 回答1:
下面是 Java 的 Trie 树代码:
```
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
}
class Trie {
TrieNode root;
Trie() {
root = new TrieNode();
}
void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEndOfWord;
}
boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
}
```
你可以使用这个 Trie 类来进行插入、查询和前缀匹配操作。
### 回答2:
Trie树又称字典树,是一种用于高效存储和检索字符串集合的数据结构。下面是一个用Java编写的Trie树的示例代码:
```java
public class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // 假设只包含小写字母
isEndOfWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (current.children[index] == null) {
return false; // 未找到
}
current = current.children[index];
}
return current.isEndOfWord; // 是否为一个完整的单词
}
public boolean startsWith(String prefix) {
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
int index = c - 'a';
if (current.children[index] == null) {
return false; // 未找到
}
current = current.children[index];
}
return true; // 存在以该前缀开头的单词
}
}
```
在以上代码中,我们定义了TrieNode类表示节点,包含一个长度为26的子节点数组和一个标志位以指示节点是否代表一个完整的单词。而Trie类则是Trie树的实现,包含插入、搜索和判断是否存在以给定前缀开头的单词的方法。在插入和搜索过程中,我们根据字符串的每个字符依次遍历树的节点,若某个节点的子节点不存在,则在相应位置新建一个子节点。最后,我们可以通过调用insert方法向Trie树中添加单词,search方法搜索某个单词是否在树中,startsWith方法判断是否存在以某个前缀开头的单词。
希望以上代码能帮助你理解和实现Trie树的基本功能。
### 回答3:
Trie树,又称字典树或前缀树,是一种多叉树结构,用于统计和处理字符串数据集。以下是用Java语言编写的一个简单的Trie树代码示例:
```java
class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // 假设只包含小写字母
isEndOfWord = false;
}
public void insert(String word) {
TrieNode current = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return current.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode current = this;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return true;
}
}
```
在上述代码中,我们定义了一个TrieNode类,其中包括一个children数组用于保存子节点,一个布尔值isEndOfWord用于判断是否是单词的结尾。
TrieNode类中的insert方法用于向Trie树中插入一个单词。它遍历单词的每个字符,并根据字符的ASCII码将其插入到对应的子节点中。
search方法用于查询一个单词是否存在于Trie树中。它遍历单词的每个字符,并检查对应的子节点是否存在。
startsWith方法用于判断是否有单词以给定的前缀开头。它遍历前缀的每个字符,并检查对应的子节点是否存在。
使用这个Trie树,我们可以快速插入、搜索和判断以及前缀开头的操作,对于处理大量字符串数据非常高效。