字典树是一种多叉树，一般用来存储一个字符串集合。字典树的边记录了字符串的一个字符，从根节点出发，不同路径就相当于不同的单词（或者单词前缀），为了确定字符串是不是到头了，需要为每个节点记录一个标志，用以判断。下面是字符串集合和字典树的对应关系。

字典树的数据结构：

1 struct TrieNode{
2     bool isEnd;
3     TrieNode*next[26]; //标准对应的字符
4     Trie(){
5         isEnd = false;
6         memset(next,0,sizeof(next));
7     }
8 };

字典树的优点

使用字典树主要有两个好处

1. 能维护字符串集合并降低存储开销。

2. 便于确定单个字符串和字符串集合之间的关系。

字典树的常见操作

1. 插入

　　字典树最重要的操作是插入字符串，采用的方式非常简单，即同时遍历字符串和字典树，如果当前字符存在，即检测下一字符，否则插入新的边和节点，以表示这个字符。

 1 void insert(TrieNode*node,string word) {
 2     for(auto&ch:word){
 3         if(node->next[ch-'a']==nullptr){
 4             Trie*newNode = new Trie();
 5             node->next[ch-'a'] = newNode;
 6         }
 7         node = node->next[ch-'a'];
 8     }
 9     node->is_End = true;
10 }

2. 查找

　　通过字典树可以很方便的判断是不是字符串是不是在字符串集合里面。判断方式和插入方式类似，也是同时遍历字符串和字典树，如果所有字符在字典树中都能找到对应的边，且遍历到最后一个字符串时，字典树对应节点标志位为单词结束，则该字符串存在于集合中。　

 1 bool search(TrieNode*node,string word) {
 2     for(auto&ch:word){
 3         if(node->next[ch-'a']==nullptr){
 4             return false;
 5         }else{
 6             node = node->next[ch-'a'];
 7         }
 8     }
 9     return node->is_End;
10 }