树同构的判断

树同构的判断结构中的flag用来标记该元素是否被访问过,judge函数中的flag为了使一行的四个元素即使又被访问过的元素也要读完一整行。#include<stdio.h>#include<stdbool.h>#include<stdlib.h>typedefstructTreeNode*Tree;structTreeNode{ intv; Tre…

在这里插入图片描述
结构中的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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注