trie和前缀检查---zoj_2876

???????? trie树是一种多叉树，广泛用于字典检索。如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。额，有点晚了，具体不写了。看代码吧。。

zoj_2876

#include<iostream>#include<cstdio>#include<string>using namespace std;bool res=false;bool f=false;class treeNode{public:bool flag;//标志这个节点形成一个词const static int maxi=10; treeNode* next[maxi];treeNode(){this->flag=false;for(int i=0;i<maxi;i++)next[i]=NULL;}};class trieTree{public:treeNode* root;const static int maxi=10; trieTree(){this->root=new treeNode;}void insert(char* word){treeNode* node=root;int i=0;while(word[i]){int num=word[i]-'0';if(node->next[num]!=NULL){node=node->next[num];if(node->flag){res=true;}}else{node->next[num]=new treeNode;node=node->next[num];f=true;}i++;}node->flag=true;if(!f)res=true;}bool search(char* word){treeNode* node=root;int i=0;while(word[i]){int num=word[i]-'0';if(node->next[num]!=NULL){node=node->next[num];}elsereturn false;i++;}if(node->flag==true)return true;elsereturn false;}bool clear(treeNode* node){for(int i=0;i<maxi;i++){if(node->next[i]!=NULL)clear(node->next[i]);}if(node!=NULL)delete node;}~trieTree(){clear(this->root);}};int cases,m;char str[1000];int main(){freopen("e:\\zoj\\zoj_2876.txt","r",stdin);cin>>cases;while(cases--){trieTree trie;cin>>m;res=false;while(m--){scanf("%s",str);f=false;trie.insert(str);}if(res)cout<<"NO"<<endl;elsecout<<"YES"<<endl;//if(trie.search(str))//cout<<str<<endl;}}

?