二叉搜索树 - 九度教程第36题
题目:
时间限制:1 秒 内存限制:32 兆 特殊判题:否
题目描述:
判断两序列是否为同一二叉搜索树序列
输入:
开始一个数 n,(1<=n<=20) 表示有 n 个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于 10,包含(0~9)的数字,没有重复数字, 根据这个序列可以构造出一颗二叉搜索树。 接下去的 n 行有 n 个序列,每个序列格式跟第一个序列一样,请判断这两个 序列是否能组成同一颗二叉搜索树。
输出:
如果序列相同则输出 YES,否则输出 NO
样例输入:
2
567432
543267
576342
0
样例输出:
YES
NO
来源:
2010 年浙江大学计算机及软件工程研究生机试真题
对输入的数字序列构建二叉排序树,并对它们进行前序和中序的遍历, 依次比较两次遍历结果是否相同,若相同则说明两棵二叉排序树相同,否则不同。
#include <stdio.h>
#include <string.h>
struct Node{
Node *lchild;
Node *rchild;
int c;
}Tree[210];//21*10
int loc;
Node *creat(){
Tree[loc].lchild=NULL;
Tree[loc].rchild=NULL;
return &Tree[loc++];
}
Node *Insert(Node *T, int x){
if(T==NULL){
T=creat();
T->c=x;
return T;
}
if(x < T->c){
T->lchild=Insert(T->lchild,x);
}else{
T->rchild=Insert(T->rchild,x);
}//由题意不存在相同的情况
return T;
}
char str1[21],str2[21];
//保存二叉排序树的遍历结果
//将每一颗树的前序遍历得到的字符串与中序遍历得到的
//字符串连接,得到用于比较的遍历结果字符串
int size1,size2;//保存在字符数组中的遍历得到的字符个数
char *str;//当前正在保存的字符串
int *size;//当前正在保存字符串中字符个数
void preOrdet(Node *T){
str[(*size)++]=T->c + '0';
//将节点中的字符放入正在保存的字符串中
if(T->lchild!=NULL){
preOrdet(T->lchild);
}
if(T->rchild!=NULL){
preOrdet(T->rchild);
}
}
void inOrder(Node *T){
if(T->lchild!=NULL){
inOrder(T->lchild);
}
str[(*size)++]=T->c + '0';
if(T->rchild!=NULL){
inOrder(T->rchild);
}
}
int main()
{
int n;
char temp[11];
while(scanf("%d",&n)!=EOF && n!=0){
scanf("%s",temp);
loc=0;
Node *T=NULL;
for(int i=0;temp[i]!=0;i++){
T=Insert(T,temp[i]-'0');
//按顺序将数字插入二叉排序树
}
size1=0;//保存在第一个字符串中的字符个数初始化为0
str=str1;//将正在保存的字符串设定为第一个字符串
size=&size1;//将正在保存的字符串中的字符个数指针指向size1
preOrdet(T);//前序遍历
inOrder(T);//中序遍历
str1[size1]=0;
//在第一个字符串的最后一个字符后添加空字符,方便后面使用字符串函数
while(n-- != 0){//输入n个其他字符串
scanf("%s",temp);
Node *T2=NULL;
for(int i=0;temp[i]!=0;i++){
T2=Insert(T2,temp[i]-'0');
}
size2=0;
str=str2;
size=&size2;
preOrdet(T2);
inOrder(T2);
str2[size2]=0;
puts(strcmp(str1,str2)==0 ? "YES" : "NO");
//比较两个遍历字符串,若相同则输出YES,否则输出NO
}
}
return 0;
}