字典樹(Trie Tree)的基本操作
Trie
字典樹的介紹來自维基百科，自由的百科全书
（重定向自字典树）
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
性质
它有3个基本性质：
图示
这是一个Trie结构的例子： 
在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。
以下是我自己寫的Trie的代碼：
#include <fstream>
/*
NOIP必备资料： Retrieval Tree 字典树
本程序为字典树的基本操作，包含字典树的建立、插入、删除的操作
本程序在GCC下编译通过并能正确工作
欢迎交流：zyfworks@gmail.com
*/
using namespace std;
const int sonnum=26; //子节点个数
const char base='a';
struct Trie
{
bool isStr; //该处是否插入过一个字符串
struct Trie *son[sonnum];//子节点
};
Trie *NewTrie() //Create a new node 建立一个新的字典树
{
Trie *temp=new Trie;
temp->isStr=false;
for (int i=0;i<sonnum;i++)
temp->son[i]=NULL; //初始化子节点
return temp;
}
void Insert(Trie *pnt,char *s,int len) //Insert a new word to Trie Tree
{ //向字典树插入一个新的字符串
Trie *temp=pnt;
for (int i=0;i<len;i++)
{
if (temp->son[s[i]-base]==NULL)
temp->son[s[i]-base]=NewTrie();
temp=temp->son[s[i]-base];
}
temp->isStr=true;
}
bool check(Trie *pnt,char *s,int len) //测试字典树中是否存在某个字符串
{
Trie *temp=pnt;
for (int i=0;i<len;i++)
if (temp->son[s[i]-base]!=NULL)
temp=temp->son[s[i]-base];
else return false;
return temp->isStr;
}
void DeleteWord(Trie *pnt,char *s,int len)//从字典树中删除某个字符串
{
Trie *temp=pnt;
for (int i=0;i<len;i++)
if (temp->son[s[i]-base]!=NULL)
temp=temp->son[s[i]-base];
else return;
temp->isStr=false;
}
int main()
{
Trie *Tree;
Tree=NewTrie();
ifstream fin("trie.in");
ofstream fout("trie.out");
char s[100];
int m;
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
Insert(Tree,s,strlen(s)); //插入字符串
}
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
DeleteWord(Tree,s,strlen(s)); //删除字符串
}
fin>>m;
for (int i=0;i<m;i++)
{
fin>>s;
fout<<check(Tree,s,strlen(s))<<endl;//测试字符串是否存在
}
return 0;
}
评论 (0)
