字典树Trie

• 音同try，又称前缀树，是一颗有根树，根节点到树节点的一个路径就代表一个单词，多用于关键词检索，自动补完和拼写检查

• 用空间换时间：借公共前缀来降低查询时间的开销

• 根节点无内容

（参考：
字典树TrieTree图文详解——CSDN

实现Trie题解——力扣）

208.实现Trie

复习一下this指针：

• cpp给每个非静态的成员函数都增加了一个隐藏（不能显式地写出来）的指针参数this，指向当前对象

• 在函数体中所有成员变量的操作都是通过该指针访问

• 是个形参，存储在栈区（寄存器register）

成员变量（Private）：

• 节点两个字段：
  • 指向子节点的指针数组children
  • 布尔字段isEnd

功能函数（public）：

• 插入insert：

  • 存在children--沿指针移动

  • 不存在--创建，记录在children数组对应位置上

• 查询search：

  • 存在children--后移

  • 存在prefix--后移

  • 存在字符串--前缀末尾对应节点的isEnd为true

  • 不存在--prefix不匹配

• 查找前缀prefix：

  • 存在children--后移

  • 不存在--说明字典树中不包含该前缀，返回空指针nullptr

• 析构函数deconstruction：

  • trie对象没有析构函数，用的默认析构函数。new出来的对象不delete释放内存，多了会泄露

AC：vector数组构建Trie

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//vector动态数组方法
class Trie {
private:
    //两个字段
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix){
        Trie* node=this;
        //this pointer, Trie* type
        for(char ch:prefix){
            //借ASCII码求字符下标，将字母转为数字
            ch-='a';            
            //某字符不存在于前缀中
            if(node->children[ch]==nullptr)
                return nullptr;
            //存在则后移 
            node=node->children[ch];
        }
        return node;
    }

public:
    //construction
    Trie():children(26),isEnd(false) {}

    void insert(string word) {
        Trie* node=this;
        for(char ch:word){
            ch-='a';
            if(node->children[ch]==nullptr)
                node->children[ch]=new Trie();
            //存在或生成子节点后后移
            node=node->children[ch];
        }
        node->isEnd=true;//prefix前缀的末尾
    }

    bool search(string word) {
        Trie* node=this->searchPrefix(word);
        return node!=nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix)!=nullptr;
    }
};

int main(){
    Trie* object;
    object=new Trie();
    object->insert("hello");
    bool flag;
    flag=object->search("hello");
    if(flag)
        cout<<"word exists";
    else    cout<<"word does not exist";
    return 0;
}

vocal，真