一個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()
 {
  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;
}