Trie树算法

作者: Chuck_Hu | 来源:发表于2017-05-12 09:14 被阅读58次

    Trie树也叫字典树,查新效率高且适用于字符串查找。相关例题HDU 1671,1251,1075,1247
    字典树由链表构成,以查询英文字母组成的例题为例。建立字典树时,每个节点都有26个子节点,代表其后可能出现的26个英文字母。且每个节点还需要一个bool型的参数end,当end=true时,说明该节点是一个单词的结尾字母。
    建立字典树需要一个根节点root,root不存储任何信息,初始化时也要将root对应的end设为false。
    建立步骤如下:

    typedef struct TrieNode  //定义Trie树节点
    {
        bool end;            //变量end
        TrieNode *next[26];  //26个子节点
    }Trie;
    Trie *root;   //定义字典树root
    void init()
    {
        root=(Trie*)malloc(sizeof(Trie)); //给root申请空间
        for(int i=0;i<26;i++)
            root->next[i]=NULL;         //初始化其子节点
        root->end=false;                //初始化根节点end值
    }
    

    看不懂就学学数据结构。
    字典树建立完成,还需要向里面插入单词。需要定义Insert方法,遍历索要插入字符串的每个字母并插入到字典树中。
    代码实现:

    void Insert(char *s)     //将单词s插入到字典树中
    {
        if(root==NULL||*s=='\0')
            return;
        int i;
        Trie *p=root;         //以节点p代表root
        while(*s!='\0')       //当读入字符不为'\0'便继续读入
        {
            if(p->next[*s-'a']==NULL)        //如果当前节点对应子节点没有录入过当前字符
            {
                Trie *t=(Trie *)malloc(sizeof(Trie));//定义节点t
                for(i=0;i<26;i++)           //节点t子节点初始化
                {
                    t->next[i]=NULL;
                }
                t->end=false;          //输入节点t子节点end值
                p->next[*s-'a']=t;     //将t录入p所指的结点即插入完成
                p=p->next[*s-'a'];        //记得p要后移
            }
            else
            {
                p=p->next[*s-'a'];
            }
            s++;                         //s也要后移
        }
        //跳出循环即所有字母全部录入完毕,将最后所指节点end设为true,表示此处是一单词结尾
        p->end=true;
    }
    

    录入完成,形成的树状结构如图所示:

    字典树图例

    没到单词的结尾通过设置end值为true表示当前字母是一个单词的结尾,图中以红色表示。
    录入完毕,接下来是接输入查找。带入某一字符串依次遍历,当多只字母所对应的节点为空时或者为字母所对节点的end值不为true,说明所查询的单词不在字典树中。反之,则在字典树中。
    代码实现:

    int Search(char *s)
    {
        Trie *p=root;
        while(*s!='\0'&&p!=NULL)   
        {
            p=p->next[*s-'a'];
            s++;
        }
        return (p!=NULL&&p->end); //若字典树的节点不为空,且end为true,则说明找到
    }
    

    最后还要清空字典树以备下次使用

    void DEL(Trie *root)
    {
        for(int i=0;i<26;i++)
            if(root->next[i]!=NULL)
                DEL(root->next[i]);
        free(root);
    }
    

    如果遇到数字类的问题,则在定义时将next[26]定义为next[10]即可。经典题目里有几道例题可以看看。

    相关文章

      网友评论

        本文标题:Trie树算法

        本文链接:https://www.haomeiwen.com/subject/ulpatxtx.html