$\Huge\color{orchid}{点击此处获取更多干货}$

字典树

字典树(Trie)又称前缀树，其操作方式就跟查字典一样，从首字母开始，一个一个的按照字母顺序去字典里查找到对应的单词，故得名“字典树”。先来看下面这个例子：

字典树中可以用指向一个节点的指针来代表某字符串的字符，存储字符串时应当遵循以下规则：
1. 字符之间的前驱后继关系在字典树中保持不变，比如上图中的$\text{he}$，字符$\text{h}$在字符$\text{e}$前面，那么在字典树中，$\text{h}$对应的节点延伸出的指针应该指向$\text{e}$对应节点，以保持前驱后继关系
2. 如果一个节点对应了一个字符串的末尾元素，那么它应该被打上标记或记录其词频$freq$（图中红色的就是如此）
3. 没有任何指针指向根节点，因此它不代表任何字符，但是需要它来引导插入和查询

在插入时，需要一个初始位于根节点处的引导指针，它对应节点的nxt表用于记录当前即将插入的字符。由于需求限制为了26个英文小写字母，因此可以把这些字母映射到$0 \sim 25$之间，找到对应的位置，如果是空节点就构造一个，然后下移到对应位置，直至字符串插入完毕。这时引导指针所指节点的词频需要+1。查询时引导指针的动向与插入一致，遇上空节点返回0，能遍历完所有字符，就返回引导指针所指节点的词频。

C++ 代码

下面给出模板类

struct TrieNode {
    size_t freq = 0ull;
    TrieNode** nxt;

    TrieNode() {
        //限制为小写英文字母26个
        nxt = new TrieNode*[26];
        fill(nxt, nxt + 26, nullptr);
    }

    //用指针给出的数组一旦new了就必须手动delete
    ~TrieNode() {
        delete[] nxt;
    }
};

class Trie {
private:
    TrieNode* root;

    //按后根顺序析构字典树
    void deleteNode(TrieNode*& node) {
        if (node == nullptr) {
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (node->nxt[i] != nullptr) {
                deleteNode(node->nxt[i]);
            }
        }
        delete node;
    }
public:
    Trie() {
        //先要有个根节点
        root = new TrieNode;
    }

    ~Trie() {
        deleteNode(root);
    }

    //插入单词
    void insert(string word) {
        TrieNode* cur = root;//从根节点开始
        for (auto& ch : word) {
            int p = ch - 'a';//映射到0~25
            if (cur->nxt[p] == nullptr) {
                cur->nxt[p] = new TrieNode;//不存在就构造
            }
            cur = cur->nxt[p];//向下移动
        }
        cur->freq++;//打上标记
    }

    //统计词频
    size_t countFrequency(string word) {
        TrieNode* cur = root;
        for (auto& ch : word) {
            int p = ch - 'a';
            if (cur->nxt[p] == nullptr) {
                return 0ull;//不存在直接返回0
            }
            //存在则向下移动
            cur = cur->nxt[p];
        }
        //返回当前节点的词频（如果中间节点未被标记，一样是0）
        return cur->freq;
    }
};