1、字典树

字典树，是一种空间换时间的数据结构，又称Trie树、前缀树。其优点在于利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。其特点主要有以下三点：

1：根节点不包含字符，除了根节点每个节点都只包含一个字符。root节点不含字符这样做的目的是为了能够包括所有字符串。

2：从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。

3：每个节点的子节点字符不同，也就是找到对应单词、字符是唯一的。

2、字典树C++实现

1、插入单词

从根节点开始遍历，从单词的第一个字符开始进行判断是否为nullptr空指针，是则表示未出现过，新建节点加入树。重复以上操作直至所有单词插入完毕，在最后的节点定义状态isEnd = true表示遍历完成。

2、查找单词

从单词第一个字符开始判断，观察能否找到下一个节点，若不能则返回false，能则继续进行遍历，直至单词查找完成。若此时isEnd = false表示当前不为字典树中对应单词的结尾，因此字典树中不包含单词只包含其前缀。

class Trie{
private:
    // 定义节点
    bool isEnd = false;
    Trie* next[26] = {nullptr};
public：
    Trie(){}    // 构造函数

    void insert(string word){   // 插入
        Trie* node = this;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(node->next[c-'a']==nullptr){
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;  // 单词串的尾节点为true
    }

    bool search(string word){   // 查找单词是否存在Trie中
        Trie* node = this;
        for(int i=0; i<word.length(); i++){
            char c = word[i];
            if(node->next[c-'a']==nullptr)  return false;
            node = node->next[c-'a'];
        }
        return node->isEnd ;  // 如果该节点是串尾节点，则为true
    }

    bool starsWith(string prefix){  //查找前缀
        Trie * node = this;
        for(int i=0; i<prefix.length(); i++){
            char c = prefix[i];
            if(node->next[c-'a']==nullptr)  return false;
            node = node->next[c-'a'];
        }
        return true;
    }
};