Trie树_字典树(字符串排序)简介及实现(2)
};
class Trie
{
public:
Trie();
voidinsert(const char* word);
boolsearch(char* word);
voiddeleteTrie(Trie_node *root);
// voidprintTrie(Trie_node *root); //new add
private:
Trie_node* root;
};
Trie::Trie()
{
root =new Trie_node();
}
void Trie::insert(const char* word)
{
Trie_node*location = root;
while(*word)
{
if(location->next[*word-'a'] == NULL)//不存在则建立
{
Trie_node *tmp = new Trie_node();
location->next[*word-'a'] = tmp;
}
location = location->next[*word-'a']; //每插入一步,相当于有一个新串经过,指针要向下移动
word++;
}
location->isStr = true; //到达尾部,标记一个串
}
bool Trie::search(char *word)
{
Trie_node*location = root;
while(*word&& location)
{
location= location->next[*word-'a'];
word++;
}
return(location!=NULL && location->isStr);
}
void Trie::deleteTrie(Trie_node *root)
{
for(i =0; i < branchNum; i++)
{
if(root->next[i]!= NULL)
{
deleteTrie(root->next[i]);
}
}
deleteroot;
}
void main() //简单测试
{
Trie t;
t.insert("a");
t.insert("abandon");
char * c= "abandoned";
t.insert(c);
t.insert("abashed");
内容版权声明:除非注明,否则皆为本站原创文章。