定义

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

考点分析

1、n个字符串中找到某个字符串是否存在或出现了几次。
解法：数据小直接顺序查找比较，数据大的时候可以直接用map来查找，如果只能用C语言，那么就需要用前缀树来解决。
2、n个字符串中查找包含某个前缀的的字符串的个数。
解法：这是非常典型的应用方法，建立前缀树即可知道每个前缀的单词个数。

前缀字符串
题目描述：
如果一个字符串s1是由另一个字符串s2的前面部分连续字符组成的，那么我们就说s1就是s2的前缀。比如“ac”是“acm”的前缀，“abcd”是“abcddfasf”的前缀，特别的“kdfa”是“kdfa”的前缀。 现在给你一些字符串，你的任务就是从这些字符串中找出一些字符串放到一个集合中，使得这个集合中任意一个字符串不是其他字符串的前缀，并且要使集合里的字符串尽可能的多。输出这个集合中字符串的个数。
输入描述：
有多组测试数据。每组测试数据以一个整数n开头，随后有n个字符串。 当n=0时表示输入结束。
0<n<100，字符串长度不大于20。
输出描述：
每组测试数据输出一个整数，即所求的最大值。每组数据占一行。
输入样例#:
6
acm
yuou
yuoufsdaf
acmmmdf
acmm
fdsf
0
输出样例#:
3
题目来源：
DreamJudge 1098

题目解析：这道题的数据很小，所以各种办法都可以解决，如果题目的数据大一些，比如有10W个字符串的时候，这个时候就需要用前缀树来解决了，其实这个题就是求前缀树的叶子结点的个数，因为只有是叶子结点才不会是其他字符串的前缀。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 26;//26个字母，如果包含大小写的话改成52  
typedef struct TrieNode {  
    int nCount;//结点出现次数  
    struct TrieNode *next[maxn];  
}Trie;  
Trie root;  
//初始化  
void InitTrie() {  
    for (int i = 0; i < maxn; i++)  
        root.next[i] = NULL;  
}  
//创建Trie树  
void CreateTrie(char *str) {  
    int len = strlen(str);  
    Trie *p = &root, *q;  
    for (int i = 0; i < len; i++) {  
        int k = str[i] - 'a';  
        if (p->nex...

掌握前缀树