数据结构——04-树4 是否同一棵二叉搜索树

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

代码一：（最大N，多组合过不去。和代码二逐行对照，就差把注释也照抄了，还是通不过，快崩溃了）

#include <stdio.h>
#include <stdlib.h>

typedef int Element;
typedef struct node Tree;
struct node{
	Element data;
	Tree *left;
	Tree *right;
	int flag;//用来标记结点有没有被搜索过 
};
Tree *create_tree(int n);						//建树
Tree *NewNode(Element data);					//构建结点
Tree *insert_tree(Tree *pTr,Element data);		//结点的插入操作
int check_tree(Tree *pTr,Element data);			//判断序列中的特定元素是否应该出现在树的对应位置 
int judge(Tree *pTr,int n);						//判断序列是否与树一致 
Tree *init_tree(Tree *pTr);						//清空树的标记 
void cle_tree(Tree *pTr);						//释放所占用的空间 


int main(int argc,char const *argv[]){
	int N=0,L;
	Tree *pTr=NULL;
	scanf("%d",&N);
	while(N){
		scanf("%d",&L);
		pTr=create_tree(N);
		for(int i=0;i<L;i++){
			if(judge(pTr,N))
				printf("Yes\n");
			else
				printf("No\n");
			pTr=init_tree(pTr);
		}
		cle_tree(pTr);
		scanf("%d",&N);	
	}
	return 0;
}
Tree *create_tree(int n){
	Tree *t=NULL;
	Element data;

	for(int i=0;i<n;i++){
		scanf("%d",&data);
		t=insert_tree(t,data);
	}
	return t;
}
Tree *NewNode(Element data){
	Tree *pNode=(Tree*)malloc(sizeof(Tree));
	pNode->data=data;pNode->flag=0;
	pNode->left=pNode->right=NULL;
	return pNode;
}
Tree *insert_tree(Tree *pTr,Element data){
	if(!pTr){
		pTr=NewNode(data);
	}else{
		if(data<pTr->data){
			pTr->left=insert_tree(pTr->left,data);
		}else{
			pTr->right=insert_tree(pTr->right,data);
		}
	}		
	return pTr;
}
int check_tree(Tree *pTr,Element data){
	int res=0;
	if(pTr&&pTr->flag){
		if(data<pTr->data){
			res=check_tree(pTr->left,data);
		}else if(data>pTr->data){
			res=check_tree(pTr->right,data);
		}
	}else if(pTr){
		if(data==pTr->data){
			pTr->flag=1;
			res=1;
		}
	}
	return res;
}
int judge(Tree *pTr,int n){
	Element data;
	int res=1;

	for(int i=0;i<n;i++){
		scanf("%d",&data);
		if(res&&!check_tree(pTr,data)){
			res=0;
		}
	}
	return res;
}

Tree *init_tree(Tree *pTr){
	if(pTr){
		pTr->flag=0;
		init_tree(pTr->left);
		init_tree(pTr->right);
	}
}
void cle_tree(Tree *pTr){
	if(pTr){
		cle_tree(pTr->left);
		cle_tree(pTr->right);
		free(pTr);
	}
}

代码二：（顺利通过）

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *Tree;
struct TNode {
	int Data;
	Tree Left;
	Tree Right;
	int flag; // 用来标记结点有没有被搜索过 
}; 

Tree BuildTree(int N); // 建树 
Tree BuildNode(int data); // 构建结点 
Tree Insert(Tree T,int data); // 结点的插入操作
int Check(Tree T,int data); // 判断序列中的特定元素是否应该出现在树的对应位置
int Judge(Tree T,int N); // 判断序列是否与树一致 
void ResetT(Tree T); // 清空树的标记
void FreeT(Tree T); // 释放树所占用的空间 
 

int main()
{
	int N=0,L; // N：每个序列的元素个数；L：序列个数
	Tree T=NULL;
	scanf("%d",&N);
	while(N) { // 以输入N为0作为数据输入截止条件
		scanf("%d",&L);
		T = BuildTree(N);
		for(int i = 0;i < L;i ++) {
			if(Judge(T,N))
				printf("Yes\n");
			else
				printf("No\n");
			ResetT(T); // 清除T中的标记flag 
		} 
		FreeT(T); // 不释放树所占内存不影响程序对错，要内存达到最优需要释放 
		scanf("%d",&N);
	} 
	return 0;
}

Tree BuildTree(int N)
{
	Tree T=NULL;
	int data;
	
	for(int i = 0;i < N;i ++) {
		scanf("%d",&data);
		T = Insert(T,data); // 做插入操作 
	}
	return T;
} 

Tree BuildNode(int data)
{
	Tree T = (Tree)malloc(sizeof(struct TNode));
	T -> Data = data;
	T -> Left = T -> Right = NULL;
	T -> flag = 0; // 没有被搜索过 
	return T;
}

Tree Insert(Tree T,int data)
{
	if(!T)
		T = BuildNode(data);
	else {
		if(data< T -> Data)
            T -> Left = Insert(T -> Left,data);
		else 
			T -> Right = Insert(T -> Right,data);
	}
	return T;
}

int Check(Tree T,int data)
{
	int res=0;
	if(T&&T -> flag) {
		if(data < T -> Data)
			res= Check(T -> Left,data);
		else if(data > T -> Data)
			res= Check(T -> Right,data);
	}else if(T){
        if(data==T -> Data){
            T -> flag = 1; // 该结点已经被搜索了，标记出来 
            res= 1; // 符合 
        }   
	}
	return res;
} 

int Judge(Tree T,int N)
{
    int data;
	int res = 1;

	for(int i = 0;i < N;i ++) {
		scanf("%d",&data);
		if(res && !Check(T,data))
			res = 0;
	} 
	return res;
} 

void ResetT(Tree T)
{
    if(T){
        T->flag=0;
        ResetT(T->Left);
        ResetT(T->Right);
    }
}
void FreeT(Tree T){
	if(T){
		FreeT(T->Left);
		FreeT(T->Right);
		free(T);
	}
}