04-树4 是否同一棵二叉搜索树 （25 分）
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和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
#include<cstdio> #include<stdlib.h> typedef struct TreeNode *Tree; struct TreeNode{ int data; int flag; Tree left,right; }; Tree newNode(int v){ Tree T=(Tree)malloc(sizeof(struct TreeNode)); T->data=v; T->left=T->right=NULL; T->flag=0; return T; } Tree insert(Tree& T,int v){ if(!T)T=newNode(v); else{ if(v>T->data)T->right=insert(T->right,v); //我遗漏T->right！！！ else if(v<T->data)T->left=insert(T->left,v);//T->left } return T; } Tree MakeTree(int n){ Tree T; int i,v; scanf("%d",&v); T=newNode(v); //先创造根结点 for( i=1;i<n;i++){ scanf("%d",&v); T=insert(T,v); } return T; } int check(Tree T,int v){ if(T->flag){ //已经经过这个结点，那么可以继续检查 if(T->data>v)return check(T->left,v); else if(T->data<v)return check(T->right,v); else return 0; } else { //没有碰到过，如果值相等，那么标记一下，说明对应符合。 if(T->data==v){ T->flag=1; return 1; } else return 0; //某次搜索中遇到前面未出现的结点，不一致 } } int Judge(Tree T,int n){ int i,v,flag=0; scanf("%d",&v); if(v!=T->data)flag=1; //根结点就不一样，false else T->flag=1; for(int i=1;i<n;i++){ scanf("%d",&v); if((!flag)&&(!check(T,v)))flag=1; //之前是if(!check(T,v) return 0;这样会导致输入的后面的数字会转移到下一组 } if(flag)return 0; else return 1; } void Reset(Tree T){ //清除标记 if(T->left)Reset(T->left); if(T->right)Reset(T->right); T->flag=0; } void FreeTree(Tree T){ //释放树 if(T->left)FreeTree(T->left); if(T->right)FreeTree(T->right); free(T); } int main(){ int n,l; Tree T; scanf("%d",&n); while(n){ scanf("%d",&l); T=MakeTree(n); for(int i=0;i<l;i++){ if(Judge(T,n))printf("Yes "); else printf("No "); Reset(T); } FreeTree(T); scanf("%d",&n); //后面再加一个scanf使得程序循环。 如果输入0，那么程序可以终止。 } return 0; }