题目描述
二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树
输入
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)
输出
示例输入
2
123456789
987654321
432156789
0
示例输出
NO
NO
1 #include<stdio.h>
2 #include<
string.h>
3 #include<stdlib.h>
4 struct node
5 {
6 char data;
7 struct node *left,*
right;
8 };
9 int ans;
10 //递归建立二叉排序树
11 void build(
struct node **p,
char ch)
12 {
13 if(*p ==
NULL)
14 {
15 *p = (
struct node *)malloc(
sizeof(
struct node));
16 (*p)->data =
ch;
17 (*p)->left =
NULL;
18 (*p)->right =
NULL;
19 }
20 else if((*p)->data >
ch)
21 build(&(*p)->
left,ch);
22 else build(&(*p)->
right,ch);
23 }
24 //先序遍历二叉排序树
25 void preorder(
struct node *p,
char s[])
26 {
27 if(p ==
NULL)
28 return;
29 s[ans++] = p->
data;
30 preorder(p->
left,s);
31 preorder(p->
right,s);
32 }
33 //释放内存
34 void del(
struct node *
p)
35 {
36 if(p == NULL)
return;
37 del(p->
left);
38 del(p->
right);
39 free(p);
40 }
41 //把二叉排序树的先序遍历转化为字符串
42 void trans(
char s[])
43 {
44 ans =
0;
45 struct node *root =
NULL;
46 char number[
11];
47 gets(number);
48 for(
int i =
0; number[i] !=
'\0'; i++
)
49 {
50 build(&
root,number[i]);
51 }
52 preorder(root,s);
53 s[ans] =
'\0';
54 del(root);
55 }
56
57 int main()
58 {
59 int n;
60 char s[
11],s1[
11];
61 while(~scanf(
"%d%*c",&n) &&
n)
62 {
63 trans(s);
64 while(n--
)
65 {
66 trans(s1);
67 if(strcmp(s,s1) ==
0)
68 printf(
"YES\n");
69 else printf(
"NO\n");
70 }
71 }
72 return 0;
73 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3222244.html
