博主今天新开一系列写“结构”,简单的单链表,普通队列,普通栈,普通二叉树就不写了,今天从Trie树写起。
Trie树(又叫字典树,前缀树,单词查找树,键树)是一种树形数据结构,直接来看图:
我们来看看Trie树的特点:根节点为空值,剩下每一个节点保存一个字母。知道这些就够了!
我们再来看看这棵树能干什么?如果从根节点遍历到某一个节点把路径节点的值连在一起就构成了一个字符串,利用这个特点很容易想到这棵树的第一个功能能帮我们查找某一个单词是否在树中(需要在每一个节点设置一个标志,表示从根节点到此节点是否构成一个单词);如果该单词存在,我们可以利用它实现第二个功能:去除重复单词;同样如果该词存,在我们还可以看出它的第三个功能:统计单词频率;因为这是一个树形结构我们利用这个特点很容易看出它的第四个功能能帮我们查找N个单词的最长公共前缀;如果我们按顺序遍历输出整棵树,发现它的第五个功能:对字符串排序。
这棵树创建看起来比较容易,就有一个问题需要我们考虑:父节点如何保存孩子节点? 主要有两种方式供大家参考:
1.因为是英文字符,我们可以用Node[26]来保存孩子节点(如果是数字我们可以用Node[10]),这种方式最快,但是并不是所有节点都会有很多孩子,所以这种方式浪费的空间太多
2.用一个链表根据需要动态添加节点。这样我们就可以省下不小的空间,但是缺点是搜索的时候需要遍历这个链表,增加了时间复杂度。
下面我用数组保存孩子节点的方式实现的trie树:
class TrieNode{//结点类
private static final int NUMBER = 26;
private char _value;
private boolean _isWord;//从根节点到这个节点存不存在一个单词
TrieNode[] _children = new TrieNode[NUMBER];//子结点集合
public TrieNode(char c) {
this.setValue(c);
}
public char getValue() {
return _value;
}
public void setValue(char _value) {
this._value = _value;
}
public boolean isWord() {
return _isWord;
}
public void setIsWord(boolean _isWord) {
this._isWord = _isWord;
}
}
public class TrieTree {
static String[] _words = {"add","am","good","the","think"};//待插入单词
private boolean searchWord(TrieNode _root, String _word) {
if(null == _root || null == _word || "".equals(_word))
return false;
char[] cs = _word.toCharArray();//将字符串转化为字符数组
for(int i = 0; i < cs.length; i++){
int index;
if(cs[i] >= 'A' && cs[i] <= 'Z'){
index = cs[i]-'A';
}
else if(cs[i] >= 'a' && cs[i] <= 'z')
index = cs[i] - 'a';
else
return false;
TrieNode child_node = _root._children[index];
if(null != child_node){//找到相同字符
if(child_node.isWord())//如果找到该单词
return true;
}
if(null == child_node)//如果在i层没找到相同字符
return false;
_root = child_node;//重设根节点
}
return false;
}
private void insertIntoTree(TrieNode _root, String _word) {//插入一个单词
if(null == _root || null == _word || "".equals(_word))
return;
char[] cs = _word.toCharArray();//将字符串转化为字符数组
for(int i = 0; i < cs.length; i++){
int index;//对应的索引值
if(cs[i] >= 'A' && cs[i] <= 'Z'){
index = cs[i]-'A';
}
else if(cs[i] >= 'a' && cs[i] <= 'z')
index = cs[i] - 'a';
else
return;
TrieNode child_node = _root._children[index];
if(null == child_node){//如果没找到
TrieNode new_node = new TrieNode(cs[i]);//创建新节点
if(i == cs.length-1)//如果遍历到该单词最后一个字符
new_node.setIsWord(true);//把该单词存在树中
_root._children[index] = new_node;//连接该节点
_root = new_node;
}else
_root = child_node;//更新树根
}
}
private void printTree(TrieNode _root,char[] _word,int index) {
if(_root == null)
return;
if(_root.isWord()){//如果根节点到此节点构成一个单词则输出
for(char c : _word){
if(c != ' ')
System.out.print(c);
}
System.out.println();
}
for(TrieNode node : _root._children){//遍历树根孩子节点
if(node != null){//回溯法遍历该树
_word[index++] = node.getValue();
printTree(node,_word,index);
_word[index] = ' ';
index--;
}
}
}
public static void main(String[] args){
TrieTree _tree = new TrieTree();//创建一棵树
TrieNode _root = new TrieNode(' ');//创建根节点
for(String word : _words)//插入单词
_tree.insertIntoTree(_root,word);
char[] _word = new char[20];
_tree.printTree(_root,_word,0);//打印树中单词
boolean status = _tree.searchWord(_root,"think");//查询树中是否存在某单词
System.out.println(status);
}
}
==================================================================================================
作者:nash_ 欢迎转载,与人分享是进步的源泉!
转载请保留原文地址:http://blog.csdn.net/nash_/article/details/8227610
===================================================================================================
分享到:
相关推荐
一个简单的C语言程序:用Trie树实现词频统计和单词查询
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
Trie树是一棵度 m ≥ 2 的树,它的每一层分支不是靠整个关键码的值来确定,而是由关键码的一个分量来确定
Trie 树实现的源码,用C++编写实现,做自然语言处理的朋友可以参考一下
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
很容易上手的Trie树入门,特别适合于acm初学者
ACM Trie树 模板,字典树模板,数据结构
字典树:又称为Trie,是一种用于快速检索的多叉树结构。
这是一个ACM算法,Trie树,他能很好的解决字符问题
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
算法实现,C++实现trie树,完成该算法的实现,运用运用
能学到什么:Trie树是一种比较独特的数据结构。它对于字符串的搜索有比较高的效率。尤其在字符的取值范围比较有限而且长度并不大的情况下表现非常理想。大多数情况下,它的查找和插入元素的复杂度只是和给定串的长度...
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
基于Trie树模仿谷歌百度搜索框提示。写的比较简单、代码漏洞之处欢迎指正。
trie树模板,acm竞赛,可以进行适当的修改就可以解决问题,在进行字符串处理的时候尤其能用到。
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
hash trie树 字典树,完整的sdk开发包 具有说明文档