字典树(Trie)
学习字典树一段时间 了，个人觉得字典树比较容易掌握，但是ACM中题目变化多端，我们只有多练习，才能对字典树的应用有更深的把握。
下面讲解一下字典树。
其实掌握字典树，只需要写过一个关于字典树的程序，记住它的结构就可以了。先看看字典树的定义
[cpp]
struct Trie
{
Trie *next[MAX];
bool isword;
};
struct Trie
{
Trie *next[MAX];
bool isword;
};
其实上面那个字典树结点的定义只是来自我做的一个题目，里面的元素视你做的题目而定，不过 Trie *next[] 这个数组就是一定的了，只不过他的大小也视你的题目而定。(可能是26个小写字母，也可能是52个大小写字母或者其他)
相信一个例子大家就都掌握了，建议一定先看看题目（自己敲完这一个题目之后，一定可以A掉其他许多关于字典树的题目了）
题目的大概意思就是说给定一些单词，要你从中找到某些单词，而这个单词是由另外两个单词组成的。
其实我们就是利用字符的ascii码来给他对应的索引
这个题目就是把每个单词拆成两部分，看看是不是每一部分在字典树中都是一个单词
先来看看建树的过程。（耐心一点，一步一步看懂程序，just one time）
必要的时候动手画一画图
[cpp]
<SPAN style="FONT-SIZE: 18px">void createTrie(char str[])//传进来输入的字符串
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
q = new Trie;
for(int j=0;j<MAX;j++)
q->next[j] = NULL;
q->isword = false;
p->next[id] = q;
}
if(i==len-1)
p->next[id]->isword = true;
p = p->next[id];
}
}</SPAN>
void createTrie(char str[])//传进来输入的字符串
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
q = new Trie;
for(int j=0;j<MAX;j++)
q->next[j] = NULL;
q->isword = false;
p->next[id] = q;
}
if(i==len-1)
p->next[id]->isword = true;
p = p->next[id];
}
}再看看查找的过程
[cpp]
<SPAN style="FONT-SIZE: 18px">bool findTrie(char str[])
{
int len = strlen(str);
Trie *p = root;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
return false;
}
p = p->next[id];
}
if(p->isword)
return true;
else
return false;
}</SPAN>
bool findTrie(char str[])
{
int len = strlen(str);
Trie *p = root;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
if(p->next[id]==NULL)
{
return false;
}
p = p->next[id];
}
if(p->isword)
return true;
else
return false;
}
最后记得释放掉这颗字典树
[cpp]
<SPAN style="FONT-SIZE: 18px">void del(Trie *root)
{
for(int i=0;i<26;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}</SPAN>
void del(Trie *root)
{
for(int i=0;i<26;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}注意在建立树的时候，先产生一个根节点 Trie *root = new Trie; //我几乎每次都忘了先new出来一个
下面贴一下完整代码
[cpp]
<SPAN style="FONT-SIZE: 18px">#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 26;
struct Trie
{
Trie *next[MAX];
bool isword;
};
Trie *root = new Trie;
char word[50000][30];
void createTrie(char str[])
{
int len = strlen(str);
Trie *p = root,*q = NULL;
for(int i=0;i<len;i++)
{
int id = str[i]-'a';
