04-树4 是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为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<iostream> 2 3 using namespace std; 4 struct treenode{ 5 int data; 6 treenode* left=NULL; 7 treenode* right=NULL; 8 int flag=0; 9 }; 10 using tree=treenode*; 11 tree insert(int i,tree t){ 12 if(t==NULL) { 13 tree T=new treenode(); 14 T->data=i; 15 t=T; 16 } 17 else if(i>t->data) t->right=insert(i,t->right); 18 else if(i<t->data) t->left=insert(i,t->left); 19 return t; 20 } 21 tree maketree(int N){ 22 int i; 23 tree t=new treenode(); 24 cin>>i; t->data=i; 25 for(int p=1;p<N;p++){ 26 cin>>i; insert(i,t); 27 } 28 return t; 29 } 30 int check(tree t,int i){ 31 if(t->flag){ 32 if(i>t->data) return check(t->right,i); 33 else if(i<t->data) return check(t->left,i); 34 else return 0; 35 }else{ 36 if(t->data==i) { 37 t->flag=1;return 1; 38 } 39 else return 0; 40 } 41 } 42 int judge(tree t,int N){ 43 int flag=1;int i; 44 cin>>i; 45 if(t->data==i) t->flag=1; 46 else flag=0; 47 for(int p=1;p<N;p++){ 48 cin>>i; 49 if(flag&&(!check(t,i))) flag=0; 50 } 51 return flag; 52 } 53 void reset(tree t){ 54 if(t->left) reset(t->left); 55 if(t->right) reset(t->right); 56 t->flag=0; 57 } 58 void freetree(tree t){ 59 if(t->left) free(t->left); 60 if(t->right) free(t->right); 61 free(t); 62 } 63 int main(){ 64 int N,L; 65 cin>>N; 66 while(N){ 67 cin>>L; 68 tree t=maketree(N); 69 for(int i=0;i<L;i++){ 70 if(judge(t,N)) cout<<"Yes"<<endl; 71 else cout<<"No"<<endl; 72 reset(t); 73 } 74 freetree(t); 75 cin>>N; 76 } 77 return 0; 78 }