当对二叉搜索树进行插入操作时，较小的元素会放在左子树，较大的元素会放在右子树。这是一种有序的存储结构，因此不同的插入序列可能会生成相同的二叉搜索树。题目要求判断给定的插入序列是否能生成相同的二叉搜索树。
题目
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
1
2
3
4
5
6
7
8
| 4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
|
输出样例:
答案
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
| #include <stdio.h>
#include <stdbool.h>
typedef struct TreeNode *Tree;
struct TreeNode {
int data;
Tree left, right;
};
Tree Insert(Tree T, int X);
bool IsSameTree(Tree T1, Tree T2);
int main() {
int N, L;
while (scanf("%d", &N) == 1 && N != 0) {
scanf("%d", &L);
Tree originalTree = NULL;
for (int i = 0; i < N; i++) {
int num;
scanf("%d", &num);
originalTree = Insert(originalTree, num);
}
for (int i = 0; i < L; i++) {
Tree checkTree = NULL;
for (int j = 0; j < N; j++) {
int num;
scanf("%d", &num);
checkTree = Insert(checkTree, num);
}
if (IsSameTree(originalTree, checkTree))
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}
Tree Insert(Tree T, int X) {
if (!T) {
T = (Tree)malloc(sizeof(struct TreeNode));
T->data = X;
T->left = T->right = NULL;
} else {
if (X < T->data)
T->left = Insert(T->left, X);
else
T->right = Insert(T->right, X);
}
return T;
}
bool IsSameTree(Tree T1, Tree T2) {
if (!T1 && !T2)
return true;
if ((T1 && !T2) || (!T1 && T2))
return false;
return (T1->data == T2->data) &&
IsSameTree(T1->left, T2->left) &&
IsSameTree(T1->right, T2->right);
}
|
- 首先，定义了二叉树的结构
TreeNode，包含一个整数 data 和两个指向左右子树的指针 left 和 right。
- 定义了两个函数
Insert 和 IsSameTree。
Insert 函数用于向二叉搜索树插入元素。它首先检查当前节点是否为空，如果为空则创建一个新节点，并根据大小关系将元素插入左子树或右子树。然后递归调用 Insert 函数，继续插入元素。IsSameTree 函数用于判断两棵二叉树是否相同。它首先检查两棵树是否都为空，如果都为空，则认为相同。如果其中一个为空而另一个不为空，则认为不相同。然后，比较当前节点的数据，并递归判断左右子树是否相同。
- 主函数
main 中，先读取一个整数 N，表示每个序列插入元素的个数。然后读取一个整数 L，表示需要检查的序列个数。
- 对于每组测试数据，首先构建原始的二叉搜索树
originalTree，通过反复调用 Insert 函数插入元素。
- 然后，对于每个需要检查的序列，同样构建一个二叉搜索树
checkTree，并通过 Insert 函数插入元素。
- 最后，通过调用
IsSameTree 函数来判断原始树和检查树是否相同，根据判断结果输出 “Yes” 或 “No”。
