什么是二叉搜索树
二叉搜索树（BST,Binary Search Tree）,也称二叉排序树或二叉查找树。
二叉搜索树：一颗二叉树，可以为空;如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值
- 非空右子树的所有键值大于其根节点的键值
- 左右子树都是二叉搜索树
题意理解
给定一个插入序列就可以确定一颗二叉搜索树。然而，一颗给定的二叉搜索树却可以由多种不同的插入序列得到。
- 例如，按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树，都得到一样的结果
问题：对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
第一行的4代表的是输入序列的长度为4
第一行的2代表的是需要比较的输入序列
因此，第二行是被比较的序列，第三、四行代表的要比较的输入序列
后面的也是此理
复制代码
求解思路
第一种解题思路如下：
根据两个序列分别建树，在判别树是否一样
第二种解题思路如下：
大家都知道序列的第一个数是整颗二叉搜索树的根节点。
于是，我们先比较两个序列的第一个树。若不相等，则两颗二叉搜索树必然不一样。
若相等，我们按顺序将小于根节点的数放在一起，大于根节点的数放在一起。
此时，小于根节点的数集合为左子树，大于根节点的数集合为右子树。
左右两颗子树也是二叉搜索树，于是递归下去就可以判别两个序列是否为同一颗二叉搜索树
第三种解题思路如下：（要实现的解法）
第三种解题思路的实现代码
搜索树的表示
typedef struct TreeNode *Tree;
struct TreeNode {
int v;
Tree Left, Right;
int flag; //是否被访问的标记
};
复制代码如何比较
程序框架
数据输入格式为
4 //序列长度
1 //要比较的序列个数
3142 //被比较的序列
3412 //要比较的序列
/**
* 主程序
*/
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; //置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;
}
/**
* 读取下一个要比较的序列，并进行比较
* 注：就算falg置1表示不一致了，我们还是要将序列读取完毕
* 如果一致返回1，否则返回0
*/
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;
}
/**
* 查找结点V
* 先查看当前结点是否访问过，若访问过，则继续查找，如果找不到返回0
* 若没有访问过，则进行比较，查看当前结点是否与该结点一致。
* 如果一致返回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;
}
}
/**
* 清除T中各结点的flag标记
*/
void ResetT ( Tree T ) {
if (T->Left) ResetT(T->Left);
if (T->Right) ResetT(T->Right);
T->flag = 0;
}
/**
* 释放T的空间
*/
void FreeTree ( Tree T ) {
if (T->Left) FreeTree(T->Left);
if (T->Right) FreeTree(T->Right);
free(T);
}
复制代码
