概念：
简述：又名单词查找树，tries树，一种多路树形结构，常用来操作字符串（但不限于字符串），和hash效率有一拼（二者效率高低是相对的，后面比较）。
性质：不同字符串的相同前缀只保存一份。
操作：查找，插入，删除等。
举个例子：
假设有这么几个单词
abcd
abc
abd
bcq
edj
前缀树画出如下
如上图可以看出，abcd等字符是在边上的，a的那条边和指向的节点我们可以看成一个整体，存储的信息是在节点上
定义的数据结构：
//节点
public static class TrieNode{
//以此节点结尾
int end;
//走过的路径的次数,可以理解为一个节点和指向 它的路径的值
int path;
//节点
private TrieNode[] arr;
public TrieNode(){
end = 0;
path = 0;
arr= new TrieNode[26];
}
}
操作：
插入：
先创建一个根节点，根节点代表起点，起点可以有26条不同的路，代表26个字母，你可以想想一个根节点走出26个字符的路径。然后用 index = chs[i] - 'a' 来计算属于哪条路，在这里解释一下，-'a' 减去的是'a'的阿斯克码，比如传进来的是b 就相当于用b的阿斯克码减去a的阿斯克码，求出的就是由当前结点出去的那条路径，其中end代表以当前结点结尾，path代表经过当前结点的个数，如上所说，当前结点和指向它的路径可以看成一个整体，比如一个节点，指向它的由a,b,c，它的path就是3，知道了变量的意思，插入就简单了，就判断现在要加入的节点之前有没有，没有就加入，加完之后，把尾节点的end++即可
代码：
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.arr[index] == null) {
node.arr[index] = new TrieNode();
}
node = node.arr[index];
node.path++;
}
node.end++;
}
}
查询：
查询的整体操作和插入类似，查询就随着字符串向下查询，如果查的当前节点没有，就返回false，直到查完，看尾节点的end是否大于零，大于零说明有该字符，如果为0就说明没有，比如有字符串abcd，你要查有没有abc，虽然一直能查到c，但是c的end不是1，所以没有
代码：
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public boolean search(String word) {
if (word == null) {
return false;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.arr[index] == null) {
return false;
}
node = node.arr[index];
}
return node.end != 0;
}
}
删除：
删除就判断当前节点的--path是否为0，为0就说明要删除的就是这个路径，而且只有要删除的那一个字符串在这条大路径上，删除就行，另一种情况，abcd，abc，要删除abc，就相当于大路径还在，只不过把每个节点的--path，然后c的end--就行了
代码：
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void delete(String word) {
if (search(word)) {
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.arr[index].path-- == 1) {
node.arr[index] = null;
return;
}
node = node.arr[index];
}
node.end--;
}
}
查找是否包含此前缀：
如果当前结点的下一个节点不为空，就一直找下去，为空就返回0，查到最后就，返回当前结点的path值，代表有几个字符串有此前缀
代码：
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.arr[index] == null) {
return 0;
}
node = node.[index];
}
return node.path;
}
}
