Trie树

发布时间：2020-12-14 01:31:28 所属栏目：Linux 来源：网络整理

导读：问题模型：给定一个字典中的所有单词，然后每次给出一个单词进行询问是否为字典中的单词对字典中的每一个单词，将这个单词转化为字典树的”一根树枝“，及从根节点往下延伸，按照顺序每个节点对应一个该单词中的字母。例如age，an ? ? ? ? ? ? ? ? ? ? ? ?

问题模型：给定一个字典中的所有单词，然后每次给出一个单词进行询问是否为字典中的单词

对字典中的每一个单词，将这个单词转化为字典树的”一根树枝“，及从根节点往下延伸，按照顺序每个节点对应一个该单词中的字母。

例如age，an

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?root

　　　　　　　　a? ? ? ??

　　　　　　　g　　n

建树：

struct trie
{
    trie *next[maxn];//子节点数组
    bool last;//记录此节点储存字母是否为一个单词的末尾字母
    
    trie()//构造函数初始化赋值
    {
        memset(next,0,sizeof(next));
        last = false;
    }
};
trie *root;
void init()//为root分配空间
{
　　root = new trie;
}

插入单词：

void insert(char s[])
{
    trie *p = root;
    for( int i = 0; i < (int)strlen(s); ++i )
    {
        if( !p->next[s[i]-‘a‘] )//该字母对应节点不存在
            p->next[s[i]-‘a‘] = new trie;
        p = p->next[s[i]-‘a‘];//转移，向下继续搜索
    }
    p->last = true;//节点末尾标记为真
}

查询：

bool query(char s[])
{
    trie *p = root;
    for( int i = 0; i < (int)strlen(s); ++i )
    {
        if( !p->next[s[i]-‘a‘] )//无节点对应该字母
            return false;
        p = p->next[s[i]-‘a‘];//继续查找
    }
    if(p->last ) return true;//该单词最后一个字母为树中储存单词的结尾，并非前缀
    else return false;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!