#include<iostream>
#include<string>
using namespace std;
#define NUM 10
int top;
//字典书数据结构
struct Trie
{
	Trie * Next[10];
	bool isword;
};
Trie trie[1000010],*t,*s;
Trie thead;
char str[20];
//建立空字典书
void InitTrie(Trie &head)
{
	head.isword=false;
	for(int i=0;i<NUM;i++)
	{
		head.Next[i]=NULL;
	}
}
void Insert(Trie &head,char x[])
{
	int i,j,len=strlen(x);
	s=&head;
	for(i=0;i<len;i++)
	{
		if(s->Next[x[i]-'0']==NULL)break;
		else s=s->Next[x[i]-'0'];
	}
	if(i==len)
	{
		s->isword=true;
		return ;
	}
	for(;i<len;i++)
	{
		t=&trie[top];
		top++;
		for(j=0;j<NUM;j++)
		{
			t->Next[j]=NULL;
		}
		t->isword=false;
		s->Next[x[i]-'0']=t;
		s=t;
	}
	s->isword=true;
}
bool visit(Trie *head)
{
	if(head->isword)
		return true;
	for(int i=0;i<NUM;++i)
		if(head->Next[i]!=NULL&&visit(head->Next[i]))
			return true;
			return false;

}
//检查是否存在前缀 
bool check(Trie *head)
{
	int i;
	if(head->isword)
	{
		for( i=0;i<NUM;++i)
		{
			if(head->Next[i]!=NULL&&(visit(head->Next[i]))) 
				return true;
		}
		return false;
	}
	for( i=0;i<NUM;++i)
	{
		if(head->Next[i]!=NULL&&(check(head->Next[i]))) 
			return true;
	}
	return false;
}
int main()
{
	int Case;
	cin>>Case;
	while(Case--)
	{
		int n;
		scanf("%d",&n);
	
		InitTrie(thead);
		top=0;
		for(int i=0;i<n;i++)
		{
			scanf("%s",str);
			Insert(thead,str);
		}
		if(check(&thead))
			printf("NO\n");
		else
			printf("YES\n");
	}
	return 0;
}

• Re:第一次用字段树，总是WA不知道哪的问题...请哪位帮忙解答下，谢谢啦！！ (925) jxnuxiaoyong 2010-01-15 17:24:53