Trie树

Trie树是一种用来保存字符串集合的树。

Trie树可在$$O(n)$$的时间内将一个字符串插入该集合中,也可以在$$O(n)$$的时间内确定一个字符串是否在集合中。

这是一颗Trie树(图自https://baike.baidu.com/pic/%E5%AD%97%E5%85%B8%E6%A0%91/9825209/0/9252ae7e96e893610dd7da67?fr=lemma&ct=single#aid=0&pic=9252ae7e96e893610dd7da67)

每i层的节点存储字符串中的第i个字符。

代码实现:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = unsigned long long int;

struct TrieNode {
    TrieNode* chd[26];
    int_t value = 0;

    TrieNode() {
        memset(chd, 0, sizeof (chd));
    }
};
TrieNode* root = new TrieNode;

void insert(string str, int_t v) {
    TrieNode * ptr = root;
    for (int_t i = 0; i < str.length(); i++) {
        if (ptr->chd[str[i] - 'a'] == nullptr) {
            ptr->chd[str[i] - 'a'] = new TrieNode;
        }
        ptr = ptr->chd[str[i] - 'a'];
    }
    ptr->value = v;

}
vector vec;

void map(TrieNode * v) {
    if (v->value) {
        for (char chr : vec) cout << chr;
        cout << endl;
    }
    for (int_t i = 0; i <= 'z' - 'a'; i++) {
        if (v->chd[i]) {
            vec.push_back(i + 'a');
            map(v->chd[i]);
            vec.pop_back();
        }
    }
}

bool query(string str) {
    TrieNode * ptr = root;
    for (int_t i = 0; i < str.length(); i++) {
        if (ptr->chd[str[i] - 'a'] == nullptr) {
            return false;
        }
        ptr = ptr->chd[str[i] - 'a'];
    }
    if (ptr->value == 0) return false;
    return true;

}

int main() {
    while (true) {
        string opt;
        cin>>opt;
        if (opt == "exit") break;
        else if (opt == "insert") {
            string str;
            cin>>str;
            insert(str, 1);
        } else if (opt == "query") {
            string str;
            cin>>str;
            cout << query(str) << endl;
        } else if (opt == "map") {
            map(root);
        }
    }

    return 0;

}