字典树

介绍

字典树（Trie），就是像字典一样的树，可用于插入和检索字符串。

假设某字典树只需要存储单词，所有单词均由 26 个小写字母组合而成，那么对于该字典树而言，每个节点都有 27 个域，分别为 26 个子节点（可以为 nullptr ）以及一个布尔标识符，表示是否存在某个单词以该字母结尾。

以下图为例：

该字典树一共存储了 dog、dot、dig、tea、tease、tease 六个单词，其中黄色的节点表示结束节点。

代码实现

在这里还是以 26 个字母组成的单词为例，给出字典树的代码实现。

使用链式节点的字典树模版

class Trie {
private:
    std::vector<Trie*> child;
    bool isEnd;

    Trie* searchPrefix(const std::string& prefix) {
        Trie* p = this;
        for (char ch : prefix) {
            p = p->child[ch - 'a'];
            if (p == nullptr) return nullptr;
        }

        return p;
    }

public:
    Trie(): child(26, nullptr), isEnd(false) {}
    ~Trie() {
        for (Trie* ct : child) {
            if (ct != nullptr) {
                delete ct;
                ct = nullptr;
            }
        }
    }

    void insert(const std::string& word) {
        Trie* p = this;
        for (char ch : word) {
            if (p->child[ch - 'a'] == nullptr) {
                p->child[ch - 'a'] = new Trie();
            }
            p = p->child[ch - 'a'];
        }
        p->isEnd = true;
    }

    bool search(const std::string& word) {
        Trie* p = searchPrefix(word);
        return p && p->isEnd;
    }
};