题意理解
给定一个插入序列就可以唯一确定一颗二叉搜索树。
但是，一颗给定的二叉搜索树却可以由多种不同的插入序列得到。
例如，按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树，都得到一样的结果。
问题
描述
对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入样例
4 2 第一部分是两个整数：4表示插入二叉搜索树的节点数、2表示要进行比较的序列
3 1 4 2 第二部分是输入的序列
3 4 1 2 第三部分是后面输入的序列，它们全部都要与第二部分进行对比，判断是否一样
3 2 4 1
2 1
2 1
1 2
0
输出样例
Yes
No
No
求解思路
建两棵二叉树
根据两个序列分别建树，再去递归判别两棵树是否一样。
不建树
例如：
3 1 2 4 对比 3 4 1 2，3都是根结点。
那找出所有比3大的结点和所有比3小的结点，发现：
很显然，我们能看出他们是同一棵二叉搜索树了。
再来对比一组：3 1 2 4、3 2 4 1。
这一组序列并不是同一棵二叉搜索树。
建一棵树
根据结点数来建立一棵二叉搜索树T，再来判别一个序列是否与二叉搜索树T一致。
分为三部分：
- 搜索树表示
- 建立搜索树T
- 判别一序列是否与搜索树T一致
搜索树表示
typedef struct TreeNode* Tree; struct TreeNode { int v; Tree Left, Right; int flag; };
程序框架搭建
int main()
{
对每组数据
1.读入N和L
2.根据第一行序列建树T
3.依据树T分别判别后面的L个序列是否能与T形成同一搜索树并输出结果。
return 0;
}
需要设计的主要函数：
- 读数据建立搜索树T
- 判别一序列是否与T构成一样的搜索树
int main() { int N, L, i; Tree T; scanf("%d", &N); while (N) { scanf("%d", &L); T = MakeTree(N); for (i = 0; i < L; i++) { if (Judge(T, N)) printf("Yes\n"); else printf("No\n"); ResetT(T); /*清除T中的所有标记flag*/ } FreeTree(T); scanf("%d", &N); } return 0; }
如何建搜索树
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; }
Tree Newnode(int V) { Tree T = (Tree*)malloc(sizeof(struct TreeNode)); T->v = 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->v) T->Right = Insert(T->Right, V); else T->Left = Insert(T->Left, V); } return T; }
如何判别
如何判别序列3 2 4 1是否与树T一致呢？
方法
在树T中按顺序搜索序列3 2 4 1中的每个数：
- 如果每次搜索所经过的结点在前面均出现过，则一致
- 否则（某次搜索中遇到前面未出现过的结点），则不一致
查找函数
check函数接受两个参数：一个二叉搜索树T和一个整数V。
函数的返回值为整型。
在二叉搜索树T中查找整数V， 如果找到了，则将该结点的标记flag设为1，并返回1；
如果没有找到，则返回0。
用递归的方式：首先判断当前结点是否被标记，如果被标记，则根据V与当前结点的大小关系，递归地查找左子树或右子树。
如果当前结点未被标记，则判断V是否等于当前结点的值， 如果等于，则将该结点的标记设为1，并返回1；
否则返回0。
int check(Tree T, int V) { if (T->flag) { if (V < T->v) { return check(T->Left, V); } else if (V > T->v) { return check(T->Right, V); } else return 0; } else { if (V == T->v) { T->flag = 1; return 1; } else { return 0; } } }
判断函数
int Judge(Tree T, int N) { int i, V; scanf("%d", &V); if (V != T->v) { return 0; } else { T->flag = 1; } for (i = 1; i < N; i++) { scanf("%d", &V); if (!check(T, V)) return 0; } return 1; }1. int J
函数有两个参数：一个是指向树的指针T，另一个是整数N。
首先从输入中读取一个整数V，如果V不等于树T的根结点值，则返回0， 表示输入的第一个数与树T不匹配。
如果V等于树T的根结点值，则将根结点的标记flag设置为1， 表示该节点已经被访问过。
接下来，用一个循环来读取剩余的N-1个整数。
对于每个整数V，函数调用check函数来检查树T中是否存在一个结点的值等于V。
如果不存在这样的节点，则返回0，表示输入的整数与树T不匹配。
如果存在这样的节点，则将该节点的标记flag设置为1， 表示该节点已经被访问过。
最后，如果所有的输入整数都能在树T中找到对应的节点，则返回1，表示输入的整数与树T匹配。
但是这段代码是存在bug的，当发现序列中的某个数与T不一致时，返回0程序结束，而不会把后面的数读完了。
那么就会误把后面的数当成下一组序列来看了，导致序列错乱了。
所以，当发现序列中的某个数与T不一致时，必须把序列后面的数都读完。
据此来改进代码：
int Judge(Tree T, int N) { int i, V, flag = 0; /*flag:0代表目前还一致，1代表已经不一致*/ scanf("%d", &V); if (V != T->v)flag = 1; else T->flag = 1; for (i = 1; i < N; i++) { scanf("%d", &V); if ((!flag) && (!check(T,V))) flag = 1; } if (flag) return 0; else return 1; }
输入参数为一个指向二叉树根结点的指针T和一个整数N，表示序列的长度。
函数的返回值为1或0，表示给定的二叉树是否与序列匹配。
首先从输入中读取第一个整数V，表示序列中的第一个元素。
如果V与二叉树根结点的值不相等，则将flag（这里是函数内部的flag标记）标记为1，表示当前已经不一致了；
否则将根节点的flag（这里是结点内的flag标记，表示是否访问过）标记为1，表示已经匹配上了。
再循环读取序列中的剩余元素，每次读取一个整数V。
如果当前已经不一致了（即flag为1），则直接跳过后面的元素。
如果当前还一致，并且当前节点的值等于V，则将当前节点的flag标记为1，表示已经匹配上了；
否则将flag标记为1，表示当前已经不一致了。
循环结束后，如果flag为1，则说明序列与二叉树不匹配，返回0；
否则返回1，表示匹配成功。
其他函数
清除T中各结点的flag标记
void ResetT(Tree T) /*清除T中各结点的flag标记*/ { if (T->Left) ResetT(T->Left); if (T->Right) ResetT(T->Right); T->flag = 0; }
先递归处理其左子树，再递归处理其右子树， 最后将该结点的flag标记设为0，表示清除标记。 这样，整个二叉树中所有节点的flag标记都被清除了。
释放T的空间
void FreeTree(Tree T) /*释放T的空间*/ { if (T->Left) FreeTree(T->Left); if (T->Right) FreeTree(T->Right); free(T); }
end
