题目1009:二叉搜索树

时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:4894 解决:2183

题目描述:

判断两序列是否为同一二叉搜索树序列

输入:

开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。

输出:

如果序列相同则输出YES,否则输出NO
样例输入:

2
567432
543267
576342
0

样例输出:

YES
NO

来源:
2010年浙江大学计算机及软件工程研究生机试真题
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-7733-1-1.html
来源: http://ac.jobdu.com/problem.php?pid=1009

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
对输入数字序列构建二叉排序树,并对它们进行前序和中序遍历,
依次比较两次遍历结果是否相同,若相同则说明两棵二叉排序树
相同,否则不同
*/
#include<stdio.h>
#include<string.h>
typedef struct Node
{
struct Node *lchild;
struct Node *rchild;
int c;
}Node;
Node bTree[110];
int loc;
char str1[25],str2[25];
int size1,size2;
char *str;
int *size;
void preOrder(Node *T)
{
if(T!=NULL)
{
str[(*size)++]=T->c+'0';
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void inOrder(Node *T)
{
if(T!=NULL)
{
inOrder(T->lchild);
str[(*size)++]=T->c+'0';
inOrder(T->rchild);
}
}
struct Node* insert(Node* T,int x)
{
if(!T)
{
T=&bTree[loc++];
T->c=x;
T->lchild=T->rchild=NULL;
return T;
}
else if(x<T->c) T->lchild=insert(T->lchild,x);
else if(x>T->c) T->rchild=insert(T->rchild,x);
return T;
};
int main()
{
#ifndef ONLINE_JUDGE
freopen("E:\jsj\cprojects\docs\in.txt","r",stdin);
//freopen("E:\jsj\cprojects\docs\mout.txt","w",stdout);
#endif
int n,i;
char tmp[12];
while(~scanf("%d",&n)&&n!=0)
{
Node *T=NULL;
scanf("%s",tmp);
for(loc=i=0;tmp[i]!=0;++i)
{
T=insert(T,tmp[i]-'0');
}
size1=0;
str=str1;
size=&size1;
preOrder(T);
inOrder(T);
str1[size1]=0;
while(n--!=0)
{
scanf("%s",tmp);
Node *T2=NULL;
for(i=0;tmp[i]!=0;++i)
{
T2=insert(T2,tmp[i]-'0');
}
size2=0;
str=str2;
size=&size2;
preOrder(T2);
inOrder(T2);
str2[size2]=0;
puts(strcmp(str1,str2)==0?"YES":"NO");
}
}
return 0;
}