字典树，又称单词查找树，Trie树，是一种树形结构，哈希表的一个变种。用于统计，排序和保存大量的字符串（也可以保存其的）。

 

优点就是利用公共的前缀来节约存储空间。在这举个简单的例子：比如说我们想储存3个单词，nyist、nyistacm、nyisttc。如果只是

单纯的按照以前的字符数组存储的思路来存储的话，那么我们需要定义三个字符串数组。但是如果我们用字典树的话，只需要定义

一个树就可以了。在这里我们就可以看到字典树的优势了。

 

基本操作：

1>建树

2>查找

3>删除即释放内存

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;bool flag;typedef struct node {     int cnt;     struct node *next[10];     node()     {          memset(next,NULL,sizeof(next));          cnt=0;     }}node ;char s[20];void buildtrid(node *root)//建树。{     node *p=root;     int l=strlen(s);     node *tmp;     for(int i=0;i
        
         next[s[i]-'0']==NULL)          {               tmp=new node;               p->next[s[i]-'0']=tmp;          }          p=p->next[s[i]-'0'];     //插入的单词是否有前缀          if(p->cnt!=0)               flag=false;     }     for(int i=0;i<10;i++)//判断插入的单词是否为其他的前缀。。          if(p->next[i]!=NULL)          {               flag=false;               break;          }     p->cnt++;}void del(node *root)//删除多余的节点，并赋值为NULL{     for(int i=0;i<10;i++)     {          if(root->next[i])          {               del(root->next[i]);               root->next[i]=NULL;          }     }     delete root;}int Search(node *root,char *s)//查找{      node *p=root;      for(int i=0;s[i];i++){          int x=s[i]-'a';          if(p->next[x]==NULL)         return 0;          p=p->next[x];      }      return p->num;  }  int main(){     int n,m;     scanf("%d",&n);     while(n--)     {          flag=true;          node *root=new node;          scanf("%d",&m);          while(m--)          {               scanf("%s",s);               if(!flag)continue;               buildtrid(root);          }          if(flag)               printf("YES\n");          else               printf("NO\n");          del(root);     }     return 0;}