这篇讲讲trie树
什么是trie树，trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计、排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓地字符串比较，查询效率比哈希树搞。
看了这个解释，可能会让你更无法理解什么是trie树，没关系，继续看下面。
首先我们简单看下trie树的样子，
不难看出，这棵trie树是由五个单词（at，bee，ben，bt，q）组成的Trie树，也很容易看出每个字母的父亲节点就是他的前一个字母

我们总结出trie树的三个性质，
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符
3.每个节点的所有子节点包含的字符都不相同

接下来 讲一下如何定义trie树（不截图了，直接手打）

define maxn 2000010

int tot=1,n;
int trie[maxn][26];//trie[i][j]，表示i的第j个孩子在trie中的一维度下标
int cnt[maxn]//cnt[i]表示以该节点结尾的单词数量
（当然你也可以选择用结构体来存储trie树，看个人习惯，有兴趣的可以上网搜一下）

接下来介绍以下插入与查询
以上图为例，假如我们要插入一个and单词 那我们的操作应该是
1.插入第一个字母a，发现根节点存在子节点a，则共享节点a
2.插入第二个字母n，发现节点a不存在子节点n，则新建子节点n
3.插入第三个字母d，发现节点n不存在子节点d，则新建子节点d

废话少说，上代码
(把图中cont改成cnt,本人的习惯性错误了。。。)

接着讲查询，查询有多种，可以找某一个前缀，也可直接查找整个单词。以查找一个前缀是否出现为例子吧
思路挺简单的，也就是从左往右以此扫描每个字母，顺着字典树往下找，能找到这个字母，往下走，否则结束查找，即没有这个前缀；前缀扫完了，表示有这个前缀。上代码
大概到这 trie树的简单应用也就讲完了，再补充解释下查找的另外几种情况
1.查找某个单词，我们可以用bool变量 v[i]表示节点i是否是单词结束的标志。那么最后return的是v[root],所以在插入操作中插入完每个单词是，要对单词最后一个字母的v[i]置为true，其他的都是false。

2.查找前缀出现的次数：那就在开一个cnt[]，表示位置i被访问过的次数，那么最后return的是cnt[root]，插入操作中每访问一个节点，都要让他的cnt++，这里前缀的次数是标记在前缀的最后一个字母所在位置的后一个位置上。