C++ 实现字典树、插入、查找单词

C++ 实现字典树、插入、查找单词

#include 
#include 
#include 
#include 

using namespace std;

//字典树结构体
struct TrieNode{
    bool isEnd;//判断此节点是否为单词结尾
    vectorchildNode;
    TrieNode():isEnd(0), childNode(26, NULL) {} //初始化列表构造函数  函数名与类名相同是构造函数
};


//向字典树中插入一个单词
void insert(TrieNode *root, const string word){
    TrieNode *temp=root;
    for(char i:word){
        //节点匹配，如果没有对应的字符，则需创建新的节点
        if(temp->childNode[i-'a'] == NULL) {
            temp->childNode[i-'a'] = new TrieNode();
        }
        temp = temp->childNode[i-'a'];//继续往下匹配
    }
    temp->isEnd = 1;//最后一个节点置1，表示它是一个单词的末尾
}


//查找一个单词
bool search(TrieNode *root, const string word) {
    TrieNode *temp=root;
    for(char i:word){
        temp=temp->childNode[i-'a'];//取单词中的每个字符进行判断
        if(!temp) break;
    }
    return temp?temp->isEnd:0;
}

//查找是否有以prefix为前缀的单词
bool startsWith(TrieNode *root, const string prefix) {
    TrieNode* temp = root;
    for(char i:prefix){
        temp=temp->childNode[i-'a'];//取单词中的每个字符进行判断
        if(!temp) return false;
    }
    return true;
}

int main() {

    TrieNode *root = new TrieNode();//新建节点
    insert(root, "word");
    cout< 
参考：
 Trie Tree 的实现 (适合初学者) - 实现 Trie (前缀树) - 力扣（LeetCode）