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];	
			}
			else
			return false;
			i++;
		}
		if(node->flag==true)
		return true;
		else
		return 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;
		else
			cout<<"YES"<<endl;
		//if(trie.search(str))
		//	cout<<str<<endl;
	}	
}