是否同一棵二叉搜索树

本题是C语言建立二叉搜索树的方法与判断两个树是否为同一个二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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<stdio.h>
#include<stdlib.h>

typedef struct TreeNode *Tree;
struct TreeNode
{
	int v;
	//存储节点的数字
	Tree left;
	Tree right;
	//储存左右儿子
	int flag;
	//标记节点有没有被遍历过
};

Tree maketree(int N);//构造二叉树
Tree insert(Tree T, int v);//向二叉树中插入元素
Tree NewNode(int v);//构建新的节点
int judge(Tree T, int N);//判断另一个树是否与该二叉树相同
void reset(Tree T);//重新设置二叉树的判断
void freetree(Tree T);//释放二叉树
int check(Tree T, int v);//判断一个树的元素是否满足相同二叉搜索树

int main()
{
	int N;
	scanf("%d", &N);
	while (N)//当N不是0的时候处理
	{
		int L;
		scanf("%d", &L);//读需要判断的序列的个数
		Tree T;
		T = maketree(N);//构造原始的二叉树
		int i;
		for (i = 0; i < L; i++)
		{
			if (judge(T, N))printf("Yes\n");
			else printf("No\n");
			reset(T);
		}
		freetree(T);
		scanf("%d", &N);
	}
	return 0;
}

Tree maketree(int N)
{
	Tree T;
	int i, tep;
	scanf("%d", &tep);
	T = NewNode(tep);
	for (i = 1; i < N; i++)
	{
		scanf("%d", &tep);
		insert(T, tep);//向二叉树中插入一个元素
	}
	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;
}

Tree NewNode(int v)
{
	Tree T = (Tree)malloc(sizeof(struct TreeNode));
	T->v = v;
	T->left = T->right = NULL;
	T->flag = 0;
	return T;
}

int check(Tree T, int v)//在树中查找一个元素v
{
	//flag设置为1表示该元素已经查过
	if (T->flag)//首先这个元素必须之前出现过才能查它的左右树
	{
		if (T->v > v)return check(T->left, v);
		else if (T->v < 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 tep, i,flag=1;
	for (i = 0; i < N; i++)
	{
		scanf("%d", &tep);
		if (!check(T, tep))
			flag = 0;
	}
	if (flag)return 1;
	else return 0;
}

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);
}