题目1105: 二叉搜索树
判断两序列是否为同一二叉搜索树序列
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
如果序列相同则输出YES，否则输出NO
6
45021
12045
54120
45021
45012
21054
50412
0
NO
NO
YES
NO
NO
NO
*** 提示已隐藏，点击上方 [+] 可显示 ***
2010年浙江大学计算机及软件工程研究生机试真题
/********************************* * 日期：2013-3-17 * 作者：SJF0115 * 题号: 天勤 题目1105: 二叉搜索树 * 来源：http://acmclub.com/problem.php?id=1105 * 结果：AC * 来源：2010年浙江大学计算机及软件工程研究生机试真题 * 总结： **********************************/#include<stdio.h>#include<string.h>#include<malloc.h>//二叉树结点typedef struct BiTNode{//数据char data;//左右孩子指针struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;char PreArray[11],PreArray2[11];char InArray[11],InArray2[11];/*x 插入的数据*/void CreateBalanceTree(BiTree &T,int x){//若当前树为空if(T == NULL){T = (BiTree)malloc(sizeof(BiTNode));T->data = x;T->lchild = NULL;T->rchild = NULL;}//如果比当前结点小，插入左子树else if(x < T->data){CreateBalanceTree(T->lchild,x);}//如果比当前结点大，插入右子树else if(x > T->data){CreateBalanceTree(T->rchild,x);}//相等不插入}//先序遍历 void PreOrder(BiTree T,int &index){ //访问根节点 PreArray[index++] = T->data;if(T->lchild != NULL){ //访问左子结点 PreOrder(T->lchild,index);}if(T->rchild != NULL){ //访问右子结点 PreOrder(T->rchild,index);} } //中序遍历 void InOrder(BiTree T,int &index){ if(T->lchild != NULL){ //访问左子结点 InOrder(T->lchild,index);}//访问根节点 InArray[index++] = T->data; if(T->rchild != NULL){ //访问右子结点 InOrder(T->rchild,index);}} int main(){int N,x,index,i,j;char str1[11],str2[11];//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); while(scanf("%d",&N) != EOF && N != 0){BiTree T = NULL;index = 0;scanf("%s",str1);//建树for(i =0;i < strlen(str1);i++){CreateBalanceTree(T,str1[i]);}//先序遍历PreOrder(T,index);PreArray[index] = '\0';strcpy(PreArray2,PreArray);//中序遍历index = 0;InOrder(T,index);InArray[index] = '\0';strcpy(InArray2,InArray);//判断序列for(i = 0;i < N;i++){T = NULL;scanf("%s",str2);//建树for(j =0;j < strlen(str2);j++){CreateBalanceTree(T,str2[j]);}//先序遍历index = 0;PreOrder(T,index);PreArray[index] = '\0';//先序序列不一样则二叉树就不一样if(strcmp(PreArray,PreArray2) != 0){printf("NO\n");continue;}//中序遍历index = 0;InOrder(T,index);InArray[index] = '\0';//中序序列不一样则二叉树就不一样if(strcmp(InArray,InArray2) != 0){printf("NO\n");continue;}//先序中序都一样就能确定唯一二叉树printf("YES\n");free(T);}} return 0;}