如图为一颗字典树，该树插入了7个单词，abc，abcd，b，bcd，efg，hij
字典树模板：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e6+5; // Trie 树上的最大结点数 4 5 int tot; // 总结点个数（不含根结点），初始为 0 6 int trie[maxn][26]; // trie 保存了每个结点的 26 个可能的子结点编号，26 对应着 26 种小写字母 7 int cnt[maxn]; // 以当前结点为终端结点的 Trie 树中的字符串个数 8 bool vis[maxn]; //标记单词是否出现过 9 10 void init(){ 11 tot=0; 12 memset(cnt,0,sizeof(cnt)); 13 memset(trie,0,sizeof(trie)); 14 } 15 16 void _insert(char str[]){ 17 int root=0; //通常根节点设置为0 18 int len=strlen(str); 19 for(int i=0;i<len;i++){ 20 int id=str[i]-'0'; 21 22 if( !trie[root][id] ) trie[root][id]=++tot; // 该子结点不存在,新增结点 23 24 root=trie[root][id]; // 在 Trie 树上继续插入字符串 str 25 26 } 27 cnt[root]++; //单词出现的次数 28 vis[root]=true; //标记单词出现过 29 } 30 31 bool find_(char str[]){ 32 33 int len=strlen(str); 34 int root=0; //查找一个单词有没有还是要从根节点开始查找 35 for(int i=0;i<len;i++){ 36 int id=str[i]-'0'; 37 if( !trie[root][id] ) return false; //如果节点下面没有该字母对应的字母，说明之前没有插入过该单词 38 root=trie[root][id]; //若是有继续向下找 39 } 40 if( vis[root] ) return true; //要是标记数组该位不为0，说明有该单词，不然说明有以这个单词为前缀的单词 41 else return false; 42 }