模版
struct trie
{
int next[26]; //指向子节点节点的下标，默认值为0则表示没有子节点，并用0-25代表'a'-'z'
int isEnd; //是否为一个单词的结尾
}tree[500005];
int inc; //最后一个分配的字典树下标，用于分配新的节点下标
int insert(string s) //插入单词
{
int p=0; //临时指针，指向子节点，初始指向0，即树的根
for (int i=0;i<s.size();i++) //遍历单词的每一个字符
{
if (tree[p].next[s[i]-97]) p=tree[p].next[s[i]-97]; //如果当前节点存在字母为s[i]的子节点，则将p指向该子节点
else //如果不存在，则创建该节点
{
inc++; //分配新的下标
tree[p].next[s[i]-97]=inc; //将当前节点字母为s[i]的子节点指向新节点
p=inc; //将临时指针指向新节点
}
}
if (tree[p].isEnd) return 1; //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明之前添加过该单词了，返回1。
else tree[p].isEnd=1; //否则说明之前没添加过该单词，将其的单词末尾标记置为1，然后返回0。
return 0;
}
int check(string s) //检查单词是否存在
{
int p=0; //临时指针，指向子节点，初始指向0，即树的根
for (int i=0;i<s.size();i++) //遍历单词的每一个字符
{
if (!tree[p].next[s[i]-97]) return 0; //如果当前节点不存在字母为s[i]的子节点，则表示该单词不存在，返回0
p=tree[p].next[s[i]-97]; //将临时指针指向字母为s[i]的子节点
}
if (tree[p].isEnd) return 1; //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明该单词存在，返回1，否则返回0。
return 0;
}解释
字典树，是一种空间换时间的数据结构，又称Trie树、前缀树，是一种树形结构，典型用于统计、排序、和保存大量字符串。利用字符串的公共前缀来减少查询时间，最大限度地减少不需要的字符串比较，查询效率比哈希树高。
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
定义结构体：该结构体用来存储树的每一个节点，每个节点都包括了指向子节点的指针，以及当前节点是否为单词的结尾。
用数组线性存储树，所以指针记录的是子节点的数组下标值。
inc记录的是当前的数组下标已经分配到多少了，用于分配新的节点。
struct trie
{
int next[26]; //指向子节点节点的下标，默认值为0则表示没有子节点，并用0-25代表'a'-'z'
int isEnd; //是否为一个单词的结尾
}tree[500005];
int inc; //最后一个分配的字典树下标，用于分配新的节点下标插入单词：
int insert(string s) //插入单词
{
int p=0; //临时指针，指向子节点，初始指向0，即树的根
for (int i=0;i<s.size();i++) //遍历单词的每一个字符
{
if (tree[p].next[s[i]-97]) p=tree[p].next[s[i]-97]; //如果当前节点存在字母为s[i]的子节点，则将p指向该子节点
else //如果不存在，则创建该节点
{
inc++; //分配新的下标
tree[p].next[s[i]-97]=inc; //将当前节点字母为s[i]的子节点指向新节点
p=inc; //将临时指针指向新节点
}
}
if (tree[p].isEnd) return 1; //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明之前添加过该单词了，返回1。
else tree[p].isEnd=1; //否则说明之前没添加过该单词，将其的单词末尾标记置为1，然后返回0。
return 0;
}检查单词是否存在：
int check(string s) //检查单词是否存在
{
int p=0; //临时指针，指向子节点，初始指向0，即树的根
for (int i=0;i<s.size();i++) //遍历单词的每一个字符
{
if (!tree[p].next[s[i]-97]) return 0; //如果当前节点不存在字母为s[i]的子节点，则表示该单词不存在，返回0
p=tree[p].next[s[i]-97]; //将临时指针指向字母为s[i]的子节点
}
if (tree[p].isEnd) return 1; //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明该单词存在，返回1，否则返回0。
return 0;
}
Comments | NOTHING