一个通用的Trie树，标准C++实现

#include "Trie.h"    namespace MyUtility   {       /*        *************************************************      功能   : 中文文本预处理，序列化输入      参数   :       返回值 :       -------------------------------------------------      备注   :       -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       void Trie::Tokenize(const std::string &str, std::vector<std::string> &vec_tokens)       {           vec_tokens.clear();           std::string tmp ="";           if(str.empty())           {               return ;           }           for(int i=0;i<str.size();i++)           {               unsigned char c = str[i];               if(c < 128)               {                   tmp = str.substr(i,1);                   vec_tokens.push_back(tmp);               }               else               {                   tmp = str.substr(i,2);                   vec_tokens.push_back(tmp);                   i++;               }           }       }       /*        *************************************************      功能   : 销毁Trie树      参数   :       返回值 :       -------------------------------------------------      备注   :       -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       void Trie::Destroy()       {           Destroy(Root);       }       void Trie::Destroy(TrieNode * node)       {           if(NULL != node)           {               Destroy(node->sons);               Destroy(node->next);               delete node;               node = NULL;           }           else           {               return ;           }       }       /*        *************************************************      功能   : 清空Trie树      参数   :       返回值 :       -------------------------------------------------      备注   :       -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       bool Trie::Clear()       {           Destroy();           CreateRoot();           travel_path.clear();           result.clear();           return true;       }       /*        *************************************************      功能   : 取得一个Trie数节点的子节点数，即一个Token序列的重复次数。      参数   :       返回值 :       -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       void Trie::TrieNodeSons(const TrieNode * node,const TrieNode* root)       {           if(NULL != node)           {               TrieNodeSons(node->sons,root);               if(node->terminal)               {                   sub_sons++;/*以Token序列是否是序列结尾为标志*/               }               if(node != root)               {/*根节点不能遍历其兄弟节点*/                   TrieNodeSons(node->next,root);               }           }           else           {               return  ;           }       }       /*void Trie::TrieNodeSons(const TrieNode * node)      {          if(NULL != node)          {              TrieNodeSons(node->sons);              if(node->terminal)              {                  sub_sons++;              }              if(node != Root)              {                  TrieNodeSons(node->next);              }          }          else          {              return  ;          }      }*/       /*        *************************************************      功能   : 遍历Trie数所有的节点，根据设定的threashold输出Token序列      参数   :       返回值 :       -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       void Trie::Travel(TrieNode* node)       {           if(NULL != node)           {               if(node != Root)               travel_path.push_back(node->token);               Travel(node->sons);               /********************************************************/               sub_sons =0;               //TrieNodeSons(node);                TrieNodeSons(node,node);               int sum = sub_sons;               //sub_sons = 0;                //TrieNodeSons(node->sons,node->sons);                   if((sub_sons >= threshhold))               //if((sum != sub_sons) && (sum >= threshhold))                {                   std::string buf="";                   for(int i=0;i<travel_path.size();i++)                   {                       buf += travel_path[i];                   }                   if(!buf.empty())                   {                       //fout<<buf<<"\t"<<sum<<std::endl;                        fout<<buf<<"\t"<<sub_sons<<std::endl;                   }               }               if(travel_path.size() > 0)               {                   travel_path.pop_back();               }               /********************************************************/               Travel(node->next);               /********************************************************/                              /********************************************************/           }           else           {               return ;           }       }       void Trie::Print()       {           travel_path.clear();           result.clear();           Travel(Root);           std::cout<<"String\tFrequency"<<std::endl;           for(int i=0;i<result.size();i++)           {               std::cout<<result[i].Str <<"\t"<<result[i].Freq <<std::endl;           }           result.clear();       }       void Trie::Print(std::vector<StrFreq>& re_result)       {           travel_path.clear();           result.clear();           Travel(Root);           //re_result = result;            //result.clear();        }       /*        *************************************************      功能   : 输入Trie树字符串      参数   :       返回值 :       -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       bool Trie::AddString(const std::string &str)       {           std::vector<std::string>val;           std::vector<std::string>val_tmp;           Tokenize(str,val);           int step = maxLength;           for(int i=0;i<val.size();i++)           {               val_tmp.clear();               while((i+step) > val.size())               {                   step --;               }               for(int j=i;j< (i+step);j++)               {                   val_tmp.push_back(val[j]);               }               TrieNode* cur = Root;               for(int j=0;j<val_tmp.size();j++)               {                   if(j == val_tmp.size() - 1)                   {                       InsertNode(cur,val_tmp[j].c_str(),true);                   }                   else                   {                       cur = InsertNode(cur,val_tmp[j].c_str());                   }               }           }           return true;       }              /*        *************************************************      功能   : 插入Trie树节点      参数   :       返回值 : 插入节点的指针      -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       TrieNode * Trie::InsertNode(TrieNode* node,const char *token,bool end)       {           if(NULL == node)           {               return NULL;           }           if(NULL == node->sons)           {               node->sons = NewNode();               node->sons->token = new char[sizeof(char)*strlen(token)];               strcpy(node->sons->token,token);               if(end)               {                   node->sons->terminal = true;               }               return node->sons;           }           else           {               TrieNode* cur = node->sons;               while(NULL != cur->next)               {                   if(strcmp(cur->token,token) == 0)                   {                       if(end)                       {                           cur->terminal = true;                       }                       return cur ;                   }                   if( NULL != cur->next)                   {                       cur = cur->next ;                   }                   else                   {                       break;                   }               }               if(strcmp(cur->token ,token) == 0)               {                   if(end)                   {                       cur->terminal = true;                   }                   return cur;               }               TrieNode* n = NewNode();               n->token = new char[sizeof(char)*strlen(token)];               strcpy(n->token ,token);               if(end)               {                   n->terminal = true;               }               cur->next = n;               return n;           }              }       /*        *************************************************      功能   : 查找一个字符串的重复次数      参数   :       返回值 :       -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       int Trie::StrFrequency(const char* str)       {           std::vector<std::string>tokens;           Tokenize(str,tokens);           TrieNode * cur = Root;           for(int i=0;i<tokens.size();i++)           {               cur = FindNode(cur,tokens[i].c_str());           }           if(NULL == cur)           {               return 0;           }           else           {               sub_sons =0;               TrieNodeSons(cur, cur);               return sub_sons;           }       }       /*        *************************************************      功能   : 查找一个节点的指针      参数   :       返回值 :       -------------------------------------------------      备注   :      -------------------------------------------------      作者   ：Li Yachao      时间   ：2012-4-3      *************************************************      */       TrieNode * Trie::FindNode(TrieNode *p_node, const char *token)       {           if((NULL != p_node) && (NULL != p_node->sons))           {               TrieNode *cur = p_node->sons;               while(NULL != cur)               {                   if(strcmp(cur->token,token) == 0)                   {                       return cur;                   }                   cur = cur->next;               }               return NULL;           }           else           {               return NULL;           }       }   }