首页 > 代码库 > PAT 天梯赛 是否同一棵二叉搜索树 (25分)(二叉搜索树)
PAT 天梯赛 是否同一棵二叉搜索树 (25分)(二叉搜索树)
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数NNN (≤10\le 10≤10)和LLL,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出NNN个以空格分隔的正整数,作为初始插入序列。最后LLL行,每行给出NNN个插入的元素,属于LLL个需要检查的序列。
简单起见,我们保证每个插入序列都是1到NNN的一个排列。当读到NNN为0时,标志输入结束,这组数据不要处理。
输出格式:
对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes No No
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<cmath> 7 #include<algorithm> 8 #include<stack> 9 #include<queue> 10 using namespace std; 11 12 //变量定义 13 int n,l,i,tmp; 14 15 //树结构定义 16 typedef struct node 17 { 18 int data; 19 struct node* left; 20 struct node* right; 21 node(int _data= http://www.mamicode.com/-1) 22 { 23 data =http://www.mamicode.com/ _data; 24 left = NULL; 25 right = NULL; 26 } 27 }Bnode; 28 29 //构造二叉搜索树 30 Bnode* CreateTree(Bnode* root,int data) 31 { 32 if(root == NULL) 33 root = new node(data); 34 else 35 { 36 if(data > root->data) 37 { 38 root->right=CreateTree(root->right,data); 39 } 40 if(data < root->data) 41 { 42 root->left=CreateTree(root->left,data); 43 } 44 } 45 return root; 46 } 47 48 //判断两颗二叉搜索树是否相同 49 bool issame(Bnode* root,Bnode* root2) 50 { 51 if(root== NULL&&root2 == NULL) 52 return true; 53 else if(root!=NULL&&root2==NULL) 54 return false; 55 else if(root==NULL&&root2!=NULL) 56 return false; 57 else if(root->data!=root2->data) 58 return false; 59 else 60 { 61 bool flag1; 62 flag1=issame(root->left,root2->left); 63 if(flag1) 64 { 65 bool flag2; 66 flag2=issame(root->right,root2->right); 67 if(flag2) 68 return true; 69 } 70 return false; 71 } 72 } 73 74 75 int main() 76 { 77 while(~scanf("%d",&n)&&n!=0) 78 { 79 scanf("%d",&l); 80 Bnode* root = NULL; 81 Bnode* root2 = NULL; 82 for(i=0;i<n;i++)//构造初始树 83 { 84 scanf("%d",&tmp); 85 root=CreateTree(root,tmp); 86 } 87 while(l--) 88 { 89 Bnode* root2 = NULL; 90 for(i=0;i<n;i++) 91 { 92 scanf("%d",&tmp); 93 root2=CreateTree(root2,tmp); 94 } 95 if(issame(root,root2)) 96 printf("Yes\n"); 97 else 98 printf("No\n"); 99 } 100 } 101 102 return 0; 103 }
PAT 天梯赛 是否同一棵二叉搜索树 (25分)(二叉搜索树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。