h5网站作用,大型企业网络设计方案,wordpress游客评论游客,杭州做企业网站的公司题目描述 对应给定的一个序列可以唯一确定一棵二叉排序树。然而#xff0c;一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树#xff0c;都得到一样的结果。你的任务书对于输入的各种序列#xff0c;判断它们是否… 题目描述 对应给定的一个序列可以唯一确定一棵二叉排序树。然而一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树都得到一样的结果。你的任务书对于输入的各种序列判断它们是否能生成一样的二叉排序树。 输入 输入包含若干组测试数据。每组数据的第1行给出两个正整数N (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
#includestdlib.h
#includestring.h
using namespace std;
typedef int status;
typedef struct BNode
{
int data;
BNode *lchild,*rchild;
}*BiTree;
status Search(BiTree T,int key,BiTree f,BiTree p)//二叉排序树的查找
//p指向数据元素的结点f指向双亲的结点
{
if(!T)
{
pf;//树为空则数据元素指向双亲结点
return 0;
}
else if(keyT-data)
{
pT;
return 1;
}
else if(keyT-data)
return Search(T-lchild,key,T,p);//查找树的左子树
else
return Search(T-rchild,key,T,p);//查找树的右字树
}
status Insert(BiTree T,int key)//二叉排序树元素的插入
{
BiTree p,s;
if(!Search(T,key,NULL,p))
{
snew BNode;
s-datakey;//插入的结点一定是树的叶子结点;
s-lchilds-rchildNULL;
if(!p)
Ts;//第一个结点根结点
else if(keyp-data)
T/p-lchilds;
else
T/p-rchilds;
return 1;
}
return 0;
}
int judge(BiTree T,BiTree T1)//判断是否为同一颗二叉排序树
{
if(!T!T1)
return 1;
if(TT1)
if(T-dataT1-data)
if(judge(T-lchild,T1-lchild)judge(T-rchild,T1-rchild))
return 1;
return 0;
}
int main()
{
int n,num;
BiTree T,T1;
while(~scanf(%d,n)n)
{
int m;
scanf(%d,m);
TNULL;//对树初始化处理
for(int i0;in;i)
{
scanf(%d,num);
Insert(T,num);//二叉排序树的元素插入
}
while(m--)
{
int flag0;
T1NULL;//对树初始化处理
for(int i0;in;i)
{
scanf(%d,num);
Insert(T1,num);
}
flagjudge(T,T1);
if(flag)
printf(Yes\n);
else
printf(No\n);
}
}
return 0;
}
