package com.myway.study;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 字典树 城市相关查询 (现针对26个英文字母)
* User: zhangyong
* Date: 14-8-10
* Time: 上午11:21
* To change this template use File | Settings | File Templates.
*/
public class DictionaryTree {
private static char SPACE = ' ';
private static char[] BASE_CHARS = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
private TrieNode root = null;
public DictionaryTree() {
root = new TrieNode(SPACE);
}
public class TrieNode {
private TrieNode[] childrenNodes = null;
private char charValue;
private boolean wordEnd = false;
public TrieNode(char charValue) {
this.charValue = charValue;
childrenNodes = new TrieNode[26];
}
public void setWordEnd(boolean wordEnd) {
this.wordEnd = wordEnd;
}
public boolean isWordEnd() {
return wordEnd;
}
}
public void insert(String word) {
char[] charArray = word.toCharArray();
TrieNode currentNode = root;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
trieNode = new TrieNode(temp);
currentNode.childrenNodes[index] = trieNode;
}
currentNode = trieNode;
}
currentNode.setWordEnd(true); //是一个单词
}
public boolean search(String key) {
boolean flag = true;
char[] charArray = key.toCharArray();
TrieNode currentNode = root;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
flag = false;
break;
} else {
currentNode = trieNode;
}
}
return flag;
}
public Set<String> travel(String key) {
char[] charArray = key.toCharArray();
TrieNode currentNode = root;
boolean flag = true;
for (char temp : charArray) {
int index = (temp - 'a');
TrieNode trieNode = currentNode.childrenNodes[index];
if (trieNode == null) {
flag = false;
break;
} else {
currentNode = trieNode;
}
}
if (flag) {
Set<String> set = new HashSet<String>();
TrieNode[] childrenNodes = currentNode.childrenNodes;
for (TrieNode child : childrenNodes) {
if (child != null) {
Recursion(child, key, set);
}
}
return set;
}
return null;
}
public void Recursion(TrieNode trieNode, String append, Set<String> set) {
TrieNode currentNode = trieNode;
if (currentNode != null) {
String temp = append + currentNode.charValue;
if (currentNode.isWordEnd()) {
set.add(temp);
}
TrieNode[] childrenNodes = currentNode.childrenNodes;
for (TrieNode child : childrenNodes) {
if (child != null) {
Recursion(child, temp, set);
}
}
}
}
public static void main(String[] args) {
//比如查询 b 输出 beijing beidaihe baoding
DictionaryTree dictionaryTree = new DictionaryTree();
dictionaryTree.insert("shanghai");
dictionaryTree.insert("shenzhen");
dictionaryTree.insert("beijing");
dictionaryTree.insert("beidaihe");
dictionaryTree.insert("baoding");
dictionaryTree.insert("guangzhou");
dictionaryTree.insert("hangzhou");
System.out.println(dictionaryTree.search("beijing"));
System.out.println(dictionaryTree.travel("b"));
System.out.println(dictionaryTree.travel("guang"));
}
}
分享到:
相关推荐
字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的...通过阅读和理解提供的"字典树"代码,你可以深入学习字典树的具体实现细节,包括节点的定义、插入和查找算法的实现,以及如何处理不同字符集的问题。
给出的C++代码实现了字典树的基本功能,包括节点创建、字符串插入和搜索。其中: 1. `createNew()`函数负责创建一个新的节点,并初始化其子节点指针数组和计数器。 2. `Insert_str()`函数实现字符串的插入,通过...
在这个"trim"压缩包文件中,可能包含了一个用Java实现字典树的项目或代码示例。你可以解压后查看源码,了解如何将上述理论知识应用到实际编程中。同时,学习如何读取文件、构建字典树,以及执行插入、搜索和删除操作...
ACM 算法字典树模板 在算法竞赛中,字典树(Trie)是一种常用的数据结构,用于解决字符串匹配问题。下面是字典树的基本概念和实现细节。 字典树的基本概念 字典树是一种树形数据结构,用于存储字符串集合。它的每...
在给定的代码片段中,字典树的实现主要由两个类构成:`TrieNode` 和 `TrieTree`。接下来将对这两个类进行详细解析。 ##### 3.1 TrieNode 类 `TrieNode` 类定义了字典树中的节点结构,包含以下属性和方法: - **...
在IT领域,字典树(Trie)是一种高效的数据结构,用于存储字符串集合。它能够快速地进行前缀查找、插入和删除操作。字典树的每个节点代表一个字符串的前缀,根节点代表空字符串,每个节点的子节点对应一个字符,节点...
自己写的字典树简单实现代码,实现了插入和查找功能。
在编程领域,可变长数组(也称为动态数组)和字典树(又称Trie树或前缀树)是两种非常重要的数据结构。它们在不同的场景下有着广泛的应用,尤其在处理大量数据时能展现出高效的性能。 首先,我们来详细讨论可变长...
在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...
### 字典树(Trie Tree)相关知识点 #### 一、什么是字典树? 字典树,也称为前缀树或Trie树,是一种用于存储字符串的高效数据结构。它利用了字符串之间的公共前缀来减少存储空间的需求,并且能够快速进行插入、...
通过阅读和理解这段代码,你可以更深入地了解字典树的内部运作机制,并且可以将其应用于实际项目,如搜索引擎的关键词检索、IP地址解析等场景。 总之,字典树是一种高效的数据结构,尤其适用于处理大量字符串数据。...
在计算机科学中,字典树(也称为Trie或前缀树)是一种高效的数据结构,尤其适用于快速查找和插入字符串。在C语言中实现字典树可以帮助我们构建一个高效的字符串处理程序,例如搜索引擎或者自动补全功能。在这个示例...
在本课程设计中,我们将深入探讨C++编程语言如何实现字典树,也称为Trie。字典树是一种高效的数据结构,特别适用于处理字符串查询,如查找、插入和删除单词。这种数据结构允许我们快速地搜索一个单词是否存在于词汇...
在IT领域,特别是编程和数据结构中,"字典树"是一种非常重要的数据结构,它在处理字符串相关的问题时表现出高效性。在这个“字典树python算法.rar”压缩包中,我们关注的是如何使用Python实现字典树算法。Python作为...
在"DemoNumberTrie"这个压缩包中,可能包含了一个演示如何实现和使用字典树的代码示例,可能包括以下功能: 1. **插入操作**:将一个字符串插入到字典树中。这涉及到遍历字符串的每个字符,并在树中创建或更新相应...
它结合了字典树(Trie树)的数据结构,能够一次性查找多个模式串在文本中的出现情况。接下来,我们将深入探讨AC自动机的工作原理、实现方法以及它与字典树的关系。 **AC自动机的基本概念** AC自动机是由Aho和...
总结来说,解决“字典树练习 POJ 1056”可能需要深入理解字典树的数据结构,实现插入和查询操作,并在Java环境中编写和测试代码。对于初学者,这是一次很好的机会来提高数据结构和算法的应用能力。
本文将深入探讨几种重要的数据结构,包括AVL树、B树、红黑树、二叉搜索树、并查集、哈夫曼树和字典树,并概述它们的实现原理和应用场景。 首先,我们来看**AVL树**,它是一种自平衡的二叉搜索树。在AVL树中,任意...
在“DT_字典树前缀推荐_源码”中,我们可以推断出该压缩包包含了一套用于实现前缀推荐的源代码。这种推荐系统通常的工作流程是: 1. **构建字典树**:首先,我们需要从给定的数据集(例如,用户历史搜索记录或商品...