1.什么事字典树

就是把英文单词中每个字符挂在树上。如果某些单词有共同的字串，就复用树上的边或者节点。

2.字典树的三个基本性质

Tire的核心思想是时间换空间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
（1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
（2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符都不相同。

3.C++代码

#include <iostream>
#include <vector>
#include <string>

class Trie {
public:
    std::vector<Trie*> children;
    bool isEnd;
public:
    Trie() : children(26, nullptr), isEnd(false) {}
    /* 边上是字符 */
    void insert(std::string word) {
        Trie* node = this;
        for (auto ch : word) {
            if (node->children[ch - 'a'] == nullptr) {
                node->children[ch - 'a'] = new Trie();
            }
            node = node->children[ch - 'a'];
        }
        node->isEnd = true;
    }
    
    bool search(std::string word) {
        Trie* node = this;
        for (auto ch : word) {
            if (node->children[ch - 'a'] != nullptr) {
                node = node->children[ch - 'a'];
            } else {
                return false;
            }
        }
        if (node->isEnd == true) {
            return true;
        } else {
            return false;
        }
    }
    
    bool startsWith(std::string prefix) {
        Trie* node = this;
        for (auto ch : prefix) {
            if (node->children[ch - 'a'] != nullptr) {
                node = node->children[ch - 'a'];
            } else {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    Trie* obj = new Trie();
    obj->insert("beijing");
    obj->insert("shanghai");
    bool res1 = obj->search("beijing");
    std::cout << "beijing is found: " << res1 << std::endl;
    bool res2 = obj->startsWith("shang");
    std::cout << "shang is found in prefix: " << res2 << std::endl;
}