一个Trie字典树的简单实现
[cpp]
// 字典树.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int Max=26;
typedef struct Node
{
bool isStr;
Node *next[Max];
}TrieNode;
class Trie
{
public:
//构造函数中初始化根节点
Trie()
{
root=new TrieNode;
for(int i=0;i<Max;i++)
root->next[i]=NULL;
root->isStr=false;
}
//利用递归的方法将整个字典树删除
~Trie()
{
del(root);
root=NULL;
}
//字典树的插入操作
void insert(const char *str)
{
if(str==NULL||*str=='\0')
return;
TrieNode *p=root;
while(*str!='\0')
{
if(p->next[*str-'a']==NULL)
{
TrieNode *tmp=new TrieNode;
for(int i=0;i<Max;i++)
tmp->next[i]=NULL;
tmp->isStr=false;
p->next[*str-'a']=tmp;
p=tmp;
}
else
{
p=p->next[*str-'a'];
}
str++;
}
p->isStr=true;
}
//查找某一个字符是否在字典树中存在
bool search(const char *str)
{
if(str==NULL||*str=='\0')
return false;
TrieNode *p=root;
while(p!=NULL && *str!='\0')
{
p=p->next[*str-'a'];
str++;
}
if(p!=NULL && p->isStr==true)
return true;
else
return false;
}
protected:
void del(TrieNode *root)
{
for(int i=0;i<Max;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}
private:
TrieNode *root;
};
int _tmain(int argc, _TCHAR* argv[])
{
Trie trie;
trie.insert("happy");
trie.insert("girl");
trie.insert("lady");
if(trie.search("happy"))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
if(trie.search("boy"))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
if(trie.search("lady"))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
if(trie.search("girl"))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
system("pause");
return 0;
}
// 字典树.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int Max=26;
typedef struct Node
{
bool isStr;
Node *next[Max];
}TrieNode;
class Trie
{
public:
//构造函数中初始化根节点
Trie()
{
root=new TrieNode;
for(int i=0;i<Max;i++)
root->next[i]=NULL;
root->isStr=false;
}
//利用递归的方法将整个字典树删除
~Trie()
{
