same.cpp

来自「有时需要测试2 个数据结构的同构性」· C++ 代码 · 共 58 行

#include<iostream>
using namespace std;
struct Node
{
	Node *leftchild;
	Node *rightchild;
};
int fatherx,fathery;
typedef struct Node N;
N** create(int n){
	int father,lc,rc;
	N **bt=new N *[n+1];//建立一个数组指针
	for(int i=0;i<=n;i++)//初始化左右子树为空
	{        bt[i] = new N;
			bt[i]->leftchild=NULL;
			bt[i]->rightchild=NULL;
	}
        cin>>fatherx>>lc>>rc;
		if(lc) bt[fatherx]->leftchild=bt[lc];
		if(rc) bt[fatherx]->rightchild=bt[rc];
	
	for(i=1;i<n;i++){
		cin>>father>>lc>>rc;
		if(lc) bt[father]->leftchild=bt[lc];
		if(rc) bt[father]->rightchild=bt[rc];
	}
	return bt;
}
void Judge(N*bt1,N*bt2){

	if((bt1->leftchild==NULL&&bt2->leftchild!=NULL)||(bt1->leftchild!=NULL&& bt2->leftchild==NULL)
		||(bt1->rightchild==NULL&&bt2->rightchild!=NULL)||(bt1->rightchild!=NULL&& bt2->rightchild==NULL)){ 
		cout<<"No";
		exit(1);
	}
	else if(bt1->leftchild!=NULL)
		Judge(bt1->leftchild,bt2->leftchild);
	 if(bt1->rightchild!=NULL)	Judge(bt1->rightchild,bt2->rightchild); 
	
}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	N** bt1,**bt2;
	int n1,n2;
	cin>>n1;
	bt1=create(n1);
    fathery=fatherx;
	cin>>n2;
	bt2=create(n2);
	if(n1!=n2){ 
		cout<<"No";
		exit(1);
	}
	Judge(bt1[fathery],bt2[fatherx]); cout<<"Yes";
	return 0;
}