字典树(Tire树)

字典树(Tire树)

字典树是一种多叉树，又称为前缀树。核心思想是利用字符串的公共前缀。

字典树的根节点为空，从根节点到某一节点路径上的字符连接起来构成字符串，完整的字符串在链上而非结点上，一个节点的所有子节点都具有相同公共前缀。

普通Tire树

struct node{
    bool end;//标记一个单词的结束
    int child[26];//下标存储英文数据，数组本身存储该数据的孩子结点的位置
}tree[MAX];
int cnt=1;//下一个新字符的存储位置(类似于链式前向星),注意root结点不用,故cnt从1开始

• 插入函数：

void insert(string s){
    int now=0;//当前工作指针
    for(int i=0;i<s.size();i++){
        int c=s[i]-'a';//将字符转换成0-26
        if(!tree[now].child[c]){//若字典树中未出现此前缀字符，执行插入结点操作
            tree[now].child[c]=cnt++;//执行插入结点操作
        }
        now=tree[now].child[c];//更新当前工作指针到其孩子结点
        if(i==s.size()-1) tree[now].end=1;//一个单词完整插入，在其最后一个字符处标记结束
    }
}

• 查找函数：

bool check(string s){
    int now=0;//当前工作指针
    for(int i=0;i<s.size();i++){
        int c=s[i]-'a';
        if(!tree[now].child[c]) return 0;//未找到该字符，此字符串查找失败
        now=tree[now].child[c];
    }
    if(!tree[now].end) return 0;//未找到结尾标记，此字符串为某个字符串的前缀，但未出现该字符串，查找失败
    return 1;//查找成功
}

01Tire树

将数字的二进制表示插入到Tire树中。