Trie树的概念
Trie树是数据结构比较简单的一种。Trie 树的基本用法是高效的存储和查找字符串集合的数据结构。Trie树也叫做字典树，它是一个树形结构。是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串。Trie树本质，利用字符串之间的公共前缀，将重复的前缀合并在一起。
例如：
插入
abcdef
abdef
aced
bcdf
bcff
cdaa
bcdc
abc
1.首先插入abcdef
先判断根节点有没有a这个点作为子节点，没有就创建出来，以此类推，再从a往下走，判断a有没有b这个子节点，没有就创建出来,以此类推，把剩下的插入进来，（存的时候会在结尾的单词后面打上一个标记，表示在这个字母结尾是有一个的单词的）如图：
2.依次插入其他
最终结果
模板：
static int N=100010; static int [][]son=new int[N][26]; //son[][]存储树中每个节点的子节点 static int []cnt=new int[N]; //记录以每个结点结尾的单词数量 static int idx; //当前用的的哪个下标，下标0：既是根节点又是空节点 //插入操作 public static void insert(char []str){ int p=0;//根节点 for (int i = 0; i < str.length; i++) {//从根节点开始依次遍历 int x=str[i]-'a';//把当前这个节点的下标取出来 //如果当前这个点上不存在对应的字母的话，创建出来 if(son[p][x]==0){ son[p][x]=++idx; } //走到下一个点,p可以理解为父节点 p=son[p][x]; } cnt[p]++; //记录下这个单词出现次数 } //查询操作 public static int query(char []str){ int p=0; for (int i = 0; i < str.length; i++) { int x=str[i]-'a'; //如果不存在这个子节点的话，说明集合中不存在这个单词 if(son[p][x]==0) return 0; p=son[p][x]; } return cnt[p]; }
