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]即可。经典题目里有几道例题可以看看。
网友评论