字典树Java代码实现
时间: 2023-09-04 13:04:12 浏览: 93
### 回答1:
字典树的Java实现可以使用递归来构建。首先需要定义一个TrieNode类,其中包含一个Map用于存储子节点,以及一个布尔值表示当前节点是否是一个单词的结尾。然后,定义一个Trie类来维护根节点。在Trie类中实现insert、search和startsWith方法。
下面是一个简单的字典树Java代码实现示例:
```java
class TrieNode {
Map<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
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 ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
node = new TrieNode();
current.children.put(ch, node);
}
current = node;
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return true;
}
}
```
这是一个简单的Trie字典树的Java代码实现,其中包括了插入、查询和查询前缀三个常用操作。
### 回答2:
字典树,也称为前缀树或Trie树,是一种非常常用的数据结构,主要用于高效地存储和搜索字符串集合。
字典树的Java代码实现如下:
```java
// 定义字典树的节点
class TrieNode {
boolean isEnd; // 表示该节点是否为字符串的结尾
TrieNode[] children; // 子节点数组
public TrieNode() {
isEnd = false;
children = new TrieNode[26]; // 假设只包含小写字母
}
}
// 字典树类
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 向字典树中插入一个字符串
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true; // 最后一个节点表示字符串的结尾
}
// 判断字典树中是否包含某个字符串
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
// 判断字典树中是否有以给定前缀开头的字符串
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
// 查找字典树中以给定前缀开头的节点
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return null; // 若当前字符不存在于子节点中,则前缀不存在
} else {
node = node.children[index];
}
}
return node;
}
}
// 测试代码
public class Main {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // 输出true
System.out.println(trie.search("app")); // 输出false
System.out.println(trie.startsWith("app")); // 输出true
trie.insert("app");
System.out.println(trie.search("app")); // 输出true
}
}
```
以上就是字典树(前缀树)的Java代码实现。通过字典树数据结构,可以高效地进行字符串的插入、查找和前缀匹配操作。
### 回答3:
字典树(Trie树)是一种用于快速检索的数据结构,它可以高效地存储和搜索字符串集合。以下是一个简单的字典树Java代码实现示例:
```java
// TrieNode类表示字典树的节点
class TrieNode {
// 标记当前节点是否为一个单词的结束
boolean isEndOfWord;
// 子节点数组,大小为26,用于存储字母
TrieNode[] children;
// 构造函数初始化节点
public TrieNode() {
isEndOfWord = false;
children = new TrieNode[26];
for (int i = 0; i < 26; i++) {
children[i] = null;
}
}
}
// 字典树类
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++) {
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 = root;
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 = root;
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;
}
}
// 使用示例
public class Main {
public static void main(String[] args) {
// 创建一个字典树对象
Trie trie = new Trie();
// 插入单词
trie.insert("apple");
trie.insert("banana");
trie.insert("orange");
// 搜索单词
System.out.println(trie.search("apple")); // 输出 true
System.out.println(trie.search("grape")); // 输出 false
// 判断是否有以给定字符串开头的单词
System.out.println(trie.startsWith("b")); // 输出 true
System.out.println(trie.startsWith("g")); // 输出 false
}
}
```
以上是一个基本的字典树Java代码实现示例,它包含了字典树的插入、查询和判断是否有以给定字符串开头的单词的功能。通过这个代码示例,你可以更好地理解字典树的实现和使用方法。