Trie树算法

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树算法

推荐阅读更多精彩内容