5-4 是否同一棵二叉搜索树 (25分)

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

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数

简单起见，我们保证每个插入序列都是1到

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

输出样例:

Yes
No
No
===============================================华丽丽的分割线===========================================
妈的，读了半天才把题意看懂。。。。。相信你们不会像我这样傻的。。。。。。。。。

还有一点问题没有解决，我再试试。。。。。

代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 typedef struct TreeNode *Tree;
  6 struct TreeNode{
  7     int v;//v表示元素的值
  8     Tree Left,Right;
  9     int flag;//一个序列是否和数是一致的，没被访问过flag为0，访问过了flag为1
 10 };
 11 Tree MakeTree(int N);
 12 Tree NewTreeNode(int temp);
 13 Tree Insert(Tree T, int temp);
 14 int Judge(Tree T, int N);
 15 int check(Tree T, int temp);
 16 void FreeTree(Tree T);
 17 void ResetT(Tree T);
 18 int main()
 19 {
 20     int N,L,i; Tree T;
 21     cin>>N;//每个序列插入元素的个数 并且保证N<=10
 22     while(N)
 23     {
 24         cin>>L;
 25         T=MakeTree(N);
 26         for(i=0;i<N;i++)
 27         {
 28             if(Judge(T,N)) printf("Yes
");
 29             else printf("No
");
 30             ResetT(T);//清除T中的标记flag
 31         }
 32         FreeTree(T);
 33         cin>>N;
 34     }
 35     return 0;
 36 }
 37 
 38 Tree MakeTree(int N)//每个序列插入元素的个数
 39 {
 40     Tree T;
 41     int i,v;
 42     cin>>v;
 43     T=NewTreeNode(v);//用v来构造一个新的根
 44     for(i=1;i<N;i++)
 45     {
 46         cin>>v;
 47         T=Insert(T,v);
 48     }
 49     return T;
 50 }
 51 
 52 Tree NewTreeNode(int temp)//构造一个新的叶节点
 53 {
 54     Tree T=(Tree)malloc(sizeof(struct TreeNode));
 55     T->v=temp;
 56     T->Left=NULL;
 57     T->Right=NULL;
 58     T->flag=0;//没被访问过的统一设置为0
 59     return T;
 60 }
 61 Tree Insert(Tree T, int temp)
 62 {
 63     if(!T) T=NewTreeNode(temp);//如果T是空的，则新构造一个节点
 64     else{
 65         if(temp<T->v)
 66             T->Left=Insert(T->Left,temp);
 67         else
 68             T->Right=Insert(T->Right,temp);
 69     }
 70     return T;
 71 }
 72 int Judge(Tree T,int N)
 73 {
 74     int temp;
 75     int i,flag=0;//flag=0表示目前还是一致的，flag=1表示目前不是一致的
 76     cin>>temp;
 77     if(temp!=T->v)
 78         flag=1;
 79     else {
 80         T->flag=1;
 81     }
 82     for (i=1; i<N; i++) {
 83     cin>>temp;
 84     if ( (!flag) && (!check(T,temp)) )
 85         flag = 1;
 86 }
 87    if (flag)
 88        return 0;
 89    else
 90        return 1;
 91 
 92 }
 93 
 94 int check(Tree T, int temp)//用新的树来和以前的树相比较
 95 {
 96     if(T->flag)
 97     {
 98         if(temp<T->v)
 99             return check(T->Left,temp);
100         else if(temp>T->v)
101             return check(T->Right,temp);
102         else
103             return 0;
104     }
105     else if (T->flag==0)
106     {
107         if(temp==T->v)
108         {
109             T->flag=1;
110             return 1;
111         }
112         else return 0;
113     }
114     return 0;
115 }
116 void ResetT(Tree T)//清除T中各节点的flag标志
117 {
118     if(T->Left)
119         ResetT(T->Left);
120     if(T->Right)
121         ResetT(T->Right);
122     T->flag=0;
123 }
124 
125 void FreeTree(Tree T)//释放T的空间
126 {
127     if(T->Left)
128         FreeTree(T->Left);
129     if(T->Right)
130         FreeTree(T->Right);
131     free(T);
132 }