结构中的flag用来标记该元素是否被访问过,judge函数中的flag为了使一行的四个元素即使又被访问过的元素也要读完一整行。
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct TreeNode *Tree;
struct TreeNode{
int v;
Tree left,right;
int flag; //访问过设置为1
};
Tree NewNode(int V){
Tree T = (Tree)malloc(sizeof(struct TreeNode));
T->v = V;
T->left = T->right = NULL;
T->flag = 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); //递归调用 T仍为根节点
else
T->left = Insert(T->left,V);
}
return T;
}
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;
}
bool check(Tree T,int V){
//函数对输入的每个元素判断是否被访问过
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; //证明本次寻找的V找到了 比较下个V
}
else return 0; //T 为标准建的一个树 ,V为一组树结点 将V每个数字都和标准树对照
}
}
bool Judge(Tree T,int N){
//按顺序查找元素 在查找过程中经过的元素若均被访问过(flag=1)则同构
int i,V,flag = 0;
scanf("%d",&V); //先判断根节点
if(V!=T->v) flag = 1;
else T->flag = 1;
for(i=1;i<N;i++){
scanf("%d",&V);
if((!check(T,V))&&(!flag)) flag = 1;
}
if(!flag) return true;
else return false;
}
void ResetT(Tree T){
if(T->left) ResetT(T->left);
if(T->right) ResetT(T->right);
T->flag = 0;
}
void FreeTree(Tree T){
if(T->left) FreeTree(T->left);
if(T->right) FreeTree(T->right);
free(T);
}
int main(){
//读入n(树结点个数)和l(序列个数) 要实现多组n l比较
//根据n和l建树
//根据树T判断与后面的分别读入的l个序列能否生成同一二叉搜索树
int N,L,i;
Tree T;
scanf("%d",&N);
while(N){
//读到0则结束
scanf("%d",&L);
T = MakeTree(N); //读入N个数
for(i=0;i<L;i++){
//对l组数据进行同构判断
if(Judge(T,N)) printf("Yes\n");
else printf("No\n");
ResetT(T); //清楚树中标记的flag
}
FreeTree(T);
scanf("%d",&N);
}
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35220.html