题目1009：二叉搜索树
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：7634
解决：3374
- 题目描述：
- 判断两序列是否为同一二叉搜索树序列
- 输入：
- 开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
- 输出：
-
如果序列相同则输出YES，否则输出NO
- 样例输入：
-
25674325432675763420
- 样例输出：
-
YESNO
#include
#include #include using namespace std;struct Node{ Node *lchild; Node *rchild; int c;} Tree[110];int loc;Node *create(){ Tree[loc].lchild=Tree[loc].rchild=NULL; return &Tree[loc++];}char str1[25],str2[25];//保存前序和中序遍历结果int size1,size2;//保存在字符数组中的遍历得到的字符个数char *str;//当前正在保存字符串int *size;//正在保存字符串中字符个数void postOrder(Node *T)//前序遍历{ str[(*size)++]=T->c+'0';//将结点中的字符放入正在保存中的字符串 if(T->lchild!=NULL) postOrder(T->lchild); if(T->rchild!=NULL) postOrder(T->rchild); str[(*size)++]=T->c+'0';//将结点中的字符放入正在保存中的字符串}void inOrder(Node *T)//中序遍历{ if(T->lchild!=NULL) inOrder(T->lchild); str[(*size)++]=T->c+'0'; if(T->rchild!=NULL) inOrder(T->rchild);}Node *Insert(Node *T,int x){ if(T==NULL) { T=create(); T->c=x; return T; } else if(x c) { T->lchild=Insert(T->lchild,x); } else if(x>T->c) { T->rchild=Insert(T->rchild,x); } return T;}int main(){ int n; char tmp[12]; while(scanf("%d",&n)!=EOF&&n!=0) { loc=0;//初始化静态空间未使用 Node *T=NULL; scanf("%s",tmp);//输入字符串 for (int i=0; tmp[i]!=0; i++) { T=Insert(T,tmp[i]-'0'); } size1=0;//保存在第一个字符串中的字符初始化为0； str =str1;//正在保存的字符串设定为第一个字符串 size=&size1; postOrder(T); inOrder(T); str1[size1]=0;//向第一个字符串的最后一个字符后加空字符，方便使用字符串函数 while(n--!=0) { scanf("%s",tmp); Node *T2=NULL; for(int i=0; tmp[i]!=0; i++) { T2=Insert(T2,tmp[i]-'0'); } size2=0; str=str2; size=&size2; postOrder(T2); inOrder(T2); str2[size2]=0; puts(strcmp(str1,str2)==0 ?"YES":"NO"); } } return 0;}