前言

在准备考研复习专业课数据结构,所以我在mooc平台上找了浙江大学的数据结构课程重新学习,感觉老师留的课后题都很有趣,所以想记录下自己的学习过程。

题目:

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第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
Yes
No
No

题解

题目分析

​ 要注意以下,这个题目的输入数据是一次全部输入的,当读取到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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<iostream>
#include<string.h>
#include<vector>
#include<cstdlib>
using namespace std;

struct Tree_node{
int data;
Tree_node* left;
Tree_node* right;
}*BST=NULL;

typedef Tree_node* BSTree;
void insert_BSTree(BSTree &BST,int num){
BSTree pre,temp = BST;
int flag = 0;
if(BST==NULL){
BST = (BSTree)malloc(sizeof(Tree_node));
BST->data = num;
BST->left = NULL;
BST->right = NULL;
//return BST;
}
else{
while(temp){
pre = temp;
if(num<(temp->data)){
temp = temp->left;
flag = -1;
}
else {
temp = temp->right;
flag = 1;
}
}
temp = (BSTree)malloc(sizeof(Tree_node));
temp->data = num;
if(flag==-1){
pre->left = temp;
}
else{
pre->right = temp;
}
temp->left = temp->right = NULL;
}
//return BST;
}
int IsSameTree(BSTree a,BSTree b){
if(a==NULL&&b==NULL)
return 1;
if((a==NULL&&b!=NULL)||(a!=NULL&&b==NULL))
return 0;
if(a->data==b->data){
return IsSameTree(a->left,b->left)&&IsSameTree(a->right,b->right);
}
else
return 0;
}

int main(){
int n,l,k,result[1000],count=0;
memset(result,-1,sizeof(result));
BSTree first,temp;
first = temp = NULL;
scanf("%d",&n);
while(n!=0){
scanf("%d",&l);
first = NULL;
for(int i=0;i<l+1;i++){
temp = NULL;
for(int j=0;j<n;j++){
scanf("%d",&k);
if(i==0)
insert_BSTree(first,k);
else
insert_BSTree(temp,k);
}
if(i!=0){
result[count++] = IsSameTree(first,temp);
}
}
scanf("%d",&n);
}
count = 0;
if(result[count]!=-1){
if(result[count++]==1)
printf("Yes");
else
printf("No");
}

while(result[count]!=-1){
if(result[count++]==1)
printf("\nYes");
else
printf("\nNo");
}
return 0;
}