给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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);
}
}
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- sarr.cn 版权所有 赣ICP备2024042794号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务