一 什么是Trie？
- 定义
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
2.Trie图示在这个图示中我们定义了4个单词（cat dog deer panda），每个节点都存一个字符；如果考虑到不同语言以及其他的不同情况，每一个子节点都需要若干个指向下个节点的指针；由于这里显示空间有限，我们暂时就使用4个单词来表示；Trie图示其实我们可以自己想一下，我们如果要查询cat这个词，我们在查询的时候就已经知道我们要到c这个节点了，所以这个值应该直接存储在到达之前的路径上；Trie图示2然后当查询到最后的子节点是代表这个查询结束；Trie图示3Trie图示4但是有一种情况也是必须要考虑的，如果某一个单词是另外一个单词的词缀需要怎么进行存储呢？这个时候其实可以在维护一个标示，来记录这个这个值；
二 代码简单实现Trie字典树基础
package com.mufeng.Trie;
import java.util.TreeMap;
/**
* Created by wb-yxk397023 on 2018/7/10.
*/
public class Trie {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(false);
}
}
private Node root;
private int size;
public Trie(){
root = new Node();
size = 0;
}
/**
* 获得Trie中存储的单词数量
* @return
*/
public int getSize(){
return size;
}
/**
* 向Trie中添加一个新的单词word
* @param word
*/
public void add(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if (cur.next.get(c) == null){
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord){
cur.isWord = true;
size++;
}
}
}
三 Trie字典树的查询
/**
* 查询单词word是否在Trie中
* @param word
* @return
*/
public boolean contains(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if (cur.next.get(c) == null){
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
四 Trie的前缀查询
- 前缀查询概念解析
前缀查询图示从图中我们可以看出，Trie在进行搜索的时候实际上进行的就是前缀的查询，比如说cat，当查询到c的时候，我们可以认为c就是cat的前缀，所以在Trie上进行的查询本质上就是前缀的查询；
代码实现前缀查询：
/**
* 查询在Trie中是否有单词以prefix为前缀
* @param prefix
* @return
*/
public boolean isPrefix(String prefix){
Node cur = root;
for (int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if (cur.next.get(c) == null){
return false;
}
cur = cur.next.get(c);
}
return true;
}
