字典树

字典树可以解决词频统计、前缀是否重复等问题。
如图，我们可以对cat,cash,apple,aply，ok建一棵字典树

由此可以看出：

1、字典树用边表示字母

2、有相同前缀的单词公用前缀节点，那我们可以的得出每个节点最多有26个子节点（在单词只包含小写字母的情况下）

3、整棵树的根节点是空的。为什么呢？便于插入和查找，这将会在后面解释。

4、每个单词结束的时候用一个特殊字符表示，图中用的‘′，那么从根节点到任意一个‘′，那么从根节点到任意一个‘’所经过的边的所有字母表示一个单词。

基本操作

1.insert 插入单词进字典树
这里有两种方法，一种是用指针实现，一种使用数组实现。相比较指针，数组实现速度会比较快，这里先写一下数组实现字典树的方式。

void insert(string str)
{
    int len = strlen(str);   //获得待插入单词的长度
    int tr = 0;   //从根出发
    for(int i=0;i<len;i++)
    {
        int k = str[i] - 'a';
        if(!trie[tr][k])  //如果没有这条边，则新建
        {
            trie[tr][k] = ++tot;  //给新的节点编号
        }
        //trie[tr].mark = true 如果要判断单词
        tr = trie[tr][k]; //向下延伸
    }
}

2.查找一个前缀(整个单词)
只需要从根出发，判断能不能一直走到所给单词的末尾就行了。如果要判断是否是一个完整的单词，在建树的时候要给单词末尾加标记。

bool search(string str)
{
    int len = str.length();
    int tr = 0;
    for(i=0;i<len;i++)
    {
        int k = str[i] - 'a';
        if(!trie[tr][k])
        {
            return false;  //无法向下走下去了，说明没有这个前缀
        }
        tr = trie[tr][k];
    }
    return true; //走到单词末尾了，说明查找到了
}

留坑