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");

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/1600.html