2828字典树

 

字典树

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

遇到单词不认识怎么办? 查字典啊，已知字典中有n个单词，假设单词都是由小写字母组成。现有m个不认识的单词，询问这m个单词是否出现在字典中。

输入

含有多组测试用例。

第一行输入n，m (n>=0&&n<=100000&&m>=0&&m<=100000)分别是字典中存在的n个单词和要查询的m个单词.

紧跟着n行，代表字典中存在的单词。

然后m行，要查询的m个单词

n=0&&m=0 程序结束

数据保证所有的单词都是有小写字母组成，并且长度不超过10

输出

若存在则输出Yes，不存在输出No .

示例输入

3 2 aab aa ad ac ad 0 0

示例输出

No Yes

提示：可以称作排序树的二分查找，也是排序树的灵活应用

 

来源

gyx

示例程序

 

#include <stdio.h> #include <stdlib.h> #include <string.h> int f; typedef char element; typedef struct BiTnNode { element data[22]; BiTnNode *lchild,*rchild; } BiTnNode, *BiTree; void CreateTree(BiTree &T,char *key)//插入建排序树； { if(T==NULL) { T=new BiTnNode; strcpy(T->data,key); T->lchild=T->rchild=NULL; } else { if(strcmp(key,T->data)<0) { CreateTree(T->lchild,key); } else { CreateTree(T->rchild,key); } } } void searchTree(BiTree T,char s[])///排序树的二分搜索 { if(T) { if(strcmp(T->data,s)>0)///搜索字符串的字典序小于结点时，搜索左子树 searchTree(T->lchild,s); else if(strcmp(T->data,s)<0)///否则大于搜索右子树； searchTree(T->rchild,s); else f=1; } } int main() { int i,m,n; char a[12],s[12]; BiTree T; while(~scanf("%d %d",&n,&m)&&n!=0&&m!=0) { T=NULL; getchar(); while(n--) { gets(a); CreateTree(T,a);///插入一个数字（字符串）； } while(m--) { gets(s); f=0; searchTree(T,s); if(f==1) printf("Yes\n"); else printf("No\n"); } } return 0; }