一、Trie树：
1、结构：
是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。利用字符串之间的公共前缀，将重复的前缀合并在一起。其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。
2、图示：
<1>、生成方法：
将how、hi、her、hello、so、see加入Trie树中：
<2>、查找方法：
查找字符串“her”，那就将要查找的字符串分割成单个的字符h， e， r，然后从Trie树的根节点开始匹配。如图所示，绿色的路径就是在Trie树中匹配的路径。
要查找的字符串“he”，那就将要查找的字符串分割成单个的字符h， e，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串“he”匹配的路径。但是，路径的最后一个节点“e”并不是红色的。也就是说， “he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。所以，查找字符串时，最后一个节点不一定要是叶子节点(红色的)
3、Trie树的实现：
<1>、多叉树的实现方法：借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。
假设字符串中只有从a到z这26个小写字母，在数组中下标为0的位置，存储指向子节点a的指针，下标为1的位置存储指向子节点b的指针，以此类推，下标为25的位置，存储的是指向的子节点z的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储null。当在Trie树中查找字符串的时候，就可以通过字符的ASCII码减去“a”的ASCII码，迅速找到匹配的子节点的指针。比如，d的ASCII码减去a的ASCII码就是3，那子节点d的指针就存储在数组中下标为3的位置中。
<2>、代码：
public class Trie {
private TrieNode root = new TrieNode('/'); // 存储无意义字符
// 往Trie树中插入一个字符串
public void insert(char[] text) {
TrieNode p = root;
for (int i = 0; i < text.length; ++i) {
int index = text[i] - 'a';
if (p.children[index] == null) {
TrieNode newNode = new TrieNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
}
// 在Trie树中查找一个字符串
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; ++i) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; // 不存在pattern
}
p = p.children[index];
}
return p.isEndingChar；// 如果不能完全匹配，只是前缀，返回false，如果找到pattern，返回true。
}
public class TrieNode {
public char data;
public TrieNode[] children = new TrieNode[26];
public boolean isEndingChar = false;
public TrieNode(char data) {
this.data = data;
}
}
}
<3>、时间复杂度：
构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n)（n表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。
每次查询时，如果要查询的字符串长度是k，那我们只需要比对大约k个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好Trie树后，在其中查找字符串的时间复杂度是O(k)， k表示要查找的字符串的长度。
