CPP dictionary tree notation

preface

Search on the Internet for a long time, did not find C++ dictionary tree standard library, do the problem often used, so in this special study and write a dictionary tree, for future use

describe

1. Use the hash table as the node of the tree

2. Use an int to check whether the word reached this node is a complete word

3. Use stack to delete words

Trie.h

#ifndef CPPTRIE_TRIE_H
#define CPPTRIE_TRIE_H
#include <unordered_map>
#include <stack>

class Trie {
private:
    std::unordered_map<char,Trie *> root;// Storage node
    int wordd;// Whether the storage is a word
public:
    Trie(a); ~Trie(a);int insert(const std::string& word);/ / insert
    bool find_word(const std::string& word);// Look for words
    bool find_prefix(const std::string& word_prefix);// Find the prefix
    bool delete_word(const std::string& word);// Delete the word
};


#endif //CPPTRIE_TRIE_H
Copy the code

Trie.cpp

include "Trie.h"

Trie::Trie() :wordd(0) {}; Trie::~Trie() =default;

bool Trie::find_word(const std::string& word) {
    Trie *node=this;
    for(auto &C:word){
        if(! node->root.count(C)){
            return false;
        }
        node=node->root[C];
    }
    if(node->wordd! =1) return false;
    return true;
}

int Trie::insert(const std::string& word) {
    Trie *node=this;
    for(auto &C:word){
        if(! node->root.count(C)){
            Trie *new_node=new Trie;
            node->root[C]=new_node;
        }
        node=node->root[C];
    }
    node->wordd=1;
    return 0;
}

bool Trie::find_prefix(const std::string& word_prefix ) {
    Trie *node=this;
    for(auto &C:word_prefix){
        if(! node->root.count(C)){
            return false;
        }
        node=node->root[C];
    }
    return true;
}

bool Trie::delete_word(const std::string &word) {
    std::stack<std::pair<char,Trie*>> ST;// Use the stack to find the string and then remove the characters from the end
    Trie *node=this;
    for(auto &C:word){
        if(! node->root.count(C)){
            return false;
        }

        node=node->root[C];
        ST.push(std::pair<char,Trie*>(C,node));

    }
    if(node->wordd! =1) return false;// The word was not found

    if(! node->root.empty()) {// If there are any characters at the end of the string, just clear the flag bit
        node->wordd=0;
        return true;
    }
    while(! ST.empty()) {if(ST.top().second->root.empty()){
            std::pair<char,Trie*>top=ST.top(a); ST.pop(a);if(ST.empty()) {this->root.erase(top.first);
                delete top.second;// Free heap memory
                return  true;
            }
            ST.top().second->root.erase(top.first);
            delete top.second;
        }else{
            return true; }}return false;
}
Copy the code

test

Buckle test topic without delete, self-test delete is ok, the following code

#include <iostream>
#include "Trie.h"
int main(a) {
    Trie root;
    root.insert("ancd");
    root.insert("ance");
    root.insert("ancf");

    std::cout << "find_word:ancde " <<root.find_word("ancde")<< std::endl;
    std::cout << "find_word:ancd " <<root.find_word("ancd")<< std::endl;
    std::cout << "find_word:ancf " <<root.find_word("ancf")<< std::endl;
    std::cout << "find_word:anc " <<root.find_word("anc")<< std::endl;
    std::cout << "find_prefix:anc " <<root.find_prefix("anc")<< std::endl;
    std::cout << "delete_word:ancf " <<root.delete_word("ancf")<< std::endl;
    std::cout << "find_word:ancf " <<root.find_word("ancf")<< std::endl;
    std::cout << "find_prefix:anc " <<root.find_prefix("anc")<< std::endl;

    std::cout << "delete_word:ancd " <<root.delete_word("ancd")<< std::endl;
    std::cout << "delete_word:ance " <<root.delete_word("ance")<< std::endl;
    std::cout << "find_word:ancd " <<root.find_word("ancd")<< std::endl;
    std::cout << "find_word:ance " <<root.find_word("ance")<< std::endl;
    std::cout << "find_prefix:anc " <<root.find_prefix("anc")<< std::endl;
    std::cout << "find_prefix:a " <<root.find_prefix("a")<< std::endl;
    return 0;
}
Copy the code

💻 Repository address: CppTrie