前言

在准备考研复习专业课数据结构，所以我在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;
}