Trie字典树又称前缀树，顾名思义，是查询前缀匹配的一种树形数据结构
可以分为插入(创建) 和 查询两部分。参考地址极客时间
创建完成后，每个字符串最后一个字母标记为终结点（图中显示为红色）
树形结构，类比于二叉树的存储嘛，每个结点两条分支(二叉树)；
而字典树，每个节点可以最多有 26个分支(存储英文字母)。
1-1二维数组存储字母
MAX_NODE表示结点数量，每个结点有26个字母结点
Trie[i][j]的值是0，表示trie树中i号节点，并没有一条连出去的边满足边上的字符标识是字符集中第j个字符（从0开始）；
trie[i][j]的值是正整数x表示trie树中i号节点，有一条连出去的边满足边上的字符标识是字符集中第j个字符，并且
这条边的终点是x号节点。
1-2链表
我这里用C++中的vector实现，
也可以写一个真正的链表，包含二元组字段<char,int>型的对应关系
1-3hash，
每次我们想找i号节点有没有标识
是某个字符ch的边时，只要看trie[i][ch]的值即可
但是实际上map时空复杂度的常数都比较大
插入 查询 实际上是类似的，就是从树的根开始往下遍历，
2-1插入：从树的根开始往下遍历，到达一个结点，没有这个字母就插入到这个结点下，作为这个结点的子节点
插入的时间复杂度：O(N)，N为所有待插入字符串的长度之和
查询的时间复杂度：O(K)，K为待查询字符串的长度
占内存：如果用二维数组实现，每个节点就会额外需要 26*8=208 个字节
优化思路：将每个节点中的数组换成其他数据结构，比如有序数组(可以二分查找)、跳表、散列表、红黑树等。
Trie变体，缩点优化：对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并
因为字典树是查找 “与前缀匹配的字符串”，又称为前缀树。
关键词提示就是 查寻找前缀匹配的前缀合适关键词，当然还有更复杂的关键词排名问题，这里不再展开。
原理与搜索引擎类似。
hihoCoder1014
解题思路：Trie字典树
首先我们把集合中的N个字符串都插入到trie中。
对于每一个查询s我们在trie中查找s，如果查找过程中无路可走，那么一定没有以s为前缀的字符串。
如果最后停在一个节点p，那我们就要看看以p为根的子树里一共有多少终结点。
终结点的数目就是答案。
但是如果我们每次都遍历以P为根的子树，那时间复杂度就太高了。解决的办法是用空间换时间，我们增加一个数组intcnt[MAX_NODE]
cnt[i]记录的是以i号节点为根的子树中，有几个终结点。
然后我们每次insert一个字符串的时候，顺便就把沿途的节点的cnt值都+1。
这样就不用每次遍历以P为根的子树，而是直接输出cnt[P]即可。
hihoCoder1107
首先我们知道一个整数可以用二进制表示成一个01串。比如3=(011)2, 5=(101)2, 4=(100)2……。
我们假设输入的整数都在0~2^32-1之间，于是我们可以用一个长度是32位的01串表示一个整数。
然后对于给定的N个整数A1, A2, A3, … AN，我们把它们对应的01串都插入到一个trie中。注意这里字符集只有0和1，所以整个trie是一棵二叉树。
下面我们举一个例子，为了描述方便，我们假设整数都在0~7之间，也就是可以用3位01串表示。
现在假设S={1, 2, 7}，也就是说我们要在Trie中插入{001, 010, 111}：