Trie.h

#pragma once

#include <algorithm>
#include <memory>
#include <stack>
#include <string>
#include <unordered_map>

namespace ds {
    template<typename T>
    class Trie;

    template<typename T>
    class TrieNode {
    public:
        friend class Trie<T>;//表明Trie 可以直接访问节点

    public:
        TrieNode() = default;
        TrieNode(const TrieNode&) = delete;//禁止使用常量引用
        TrieNode(TrieNode&&) = delete;
        ~TrieNode() = default;
        TrieNode& operator=(const TrieNode&) = delete;
        TrieNode& operator=(TrieNode&&) = delete;

    private:
        //一系列的{当前字符的值，指向下一个的智能指针}
        std::unordered_map<T, std::shared_ptr<TrieNode>> children_;
        bool end_ = false;//是不是结束（一个合法的字符串）
    };

    template<typename T>
    class Trie {
    public:
        Trie() = default;

        //四种不要做（套路式写法）
        Trie(const Trie&) = delete;
        Trie(Trie&&) = delete;
        Trie& operator=(const Trie&) = delete;
        Trie& operator=(Trie&&) = delete;



        int size();
        void clear();

        //std::string (C++11) 即 std::basic_string<char>
        //std::u16string(C++11) 即 std::basic_string<char16_t>
        void insert(const std::basic_string<T>& key);
        bool search(const std::basic_string<T>& key);
        bool remove(const std::basic_string<T>& key);

    private:
        //make_shared<T> 同make_pair(x,y) 一个道理，构造实例
        std::shared_ptr<TrieNode<T>> root_{ std::make_shared<TrieNode<T>>() };
        int size_{ 0 };
    };

    template<typename T>
    int Trie<T>::size() {
        return this->size_;
    }

    template<typename T>
    void Trie<T>::clear() {
        this->root_->children_.clear();//由unordered_map执行清空操作
        this->size_ = 0;
    }

    template<typename T>
    void Trie<T>::insert(const std::basic_string<T>& key) {

        //游动下标curr从root开始
        std::shared_ptr<TrieNode<T>> current{ root_ };

        //取出每一个字符
        for (const T& c : key) {
            //如果孩子中没有这个字符
            if (current->children_.find(c) == current->children_.end())
                current->children_[c] = std::make_shared<TrieNode<T>>();
            current = current->children_[c];//继续向下找
        }

        //末尾字符处还没有被标记为一个新词
        if (!current->end_ && current != root_) {
            current->end_ = true;//添加结束标志
            ++this->size_;//字符串数目加一
        }

    }

    template<typename T>
    bool Trie<T>::search(const std::basic_string<T>& key) {

        //curr从根开始搜
        std::shared_ptr<TrieNode<T>> current{ root_ };
        for (const T& c : key) {
            if (current->children_.empty()) return false;//半截就不对了
            current = current->children_[c];
            if (!current) return false;//不存在完整的字符串
        }
        return current->end_;//包含该串，但是需要检查结尾标记
    }

    template<typename T>
    bool Trie<T>::remove(const std::basic_string<T>& key) {

        //cur从根开始
        std::shared_ptr<TrieNode<T>> current{ root_ };
        //记录路径上的地址（指针）
        std::stack<std::shared_ptr<TrieNode<T>>> stack;
        stack.push(current);

        //同查找相似
        for (const T& c : key) {
            if (current->children_.empty()) return false;
            current = current->children_[c];
            if (!current) return false;
            stack.push(current);
        }


        // If no prefix is matched or the prefix is not a legit word.
        if (stack.size() <= 1 || !stack.top()->end_) return false;
        stack.top()->end_ = false;//清除标记
        auto r_it = key.rbegin();//将待删的字符串反着读（此时同出栈顺序一致）


        // Remove a Node Iteratively when it is not a word and it has no children.
        //从底下往上删除那些没有结束标识且没有儿子的字符（多余）
        while (!stack.top()->end_ && stack.top()->children_.empty() &&
            r_it != key.rend()) {
            stack.pop();
            stack.top()->children_.erase(*r_it);//从上一个字符的儿子map中删除
            ++r_it;//要明白此时，栈顶的指针所指的是字符就是*r_it
        }

        --this->size_;//词数减一
        return true;
    }
}

简单的例子

#include"Trie.h"
#include<iostream>

using namespace ds;

int main() {
    ds::Trie<char> trie;

    trie.insert("A");
    trie.insert("to");
    trie.insert("tea");
    trie.insert("ted");
    trie.insert("ten");
    trie.insert("i");
    trie.insert("in");
    trie.insert("inn");

    std::cout << trie.size() << std::endl;

    trie.remove("in");

    std::cout << trie.search("in") << std::endl;

    trie.clear();


    return 0;
}

更宽的字符

#include"Trie.h"
#include<iostream>

int main() {
    ds::Trie<wchar_t> trie;

    trie.insert(L"υπολογιστής");
    trie.insert(L"computer");
    trie.insert(L"компьютер");

    std::cout << trie.size() << std::endl;

    trie.remove(L"компьютер");

    std::cout << trie.search(L"компьютер") << std::endl;

    trie.clear();
}