same.cpp

有时需要测试2 个数据结构的同构性

#include <iostream>
#include<fstream>
using namespace std;

struct Node{
	struct Node * leftchild;
	struct Node * rightchild;
};

Judge (Node * bt1,Node * bt2){
	if (bt1 == NULL && bt2 == NULL){
        return 1;
	}
	else if ((bt1 == NULL && bt2 != NULL) || (bt1 != NULL && bt2 == NULL)){ 
        return 0;
	}
	else{
        return (Judge(bt1->leftchild,bt2->leftchild) && Judge(bt1->rightchild,bt2->rightchild)); 
	}
}
void main(){
	int n(0),m(0),i(0),father(0),lc(0),rc(0);
	ifstream infile("input.txt");
	ofstream outfile("output.txt");
	infile>>n;
	Node ** bt1 = new Node *[n + 1];
	for (i = 1; i <= n; i ++)
	{
        bt1[i] = new Node;
        bt1[i]->leftchild = NULL;
        bt1[i]->rightchild = NULL;
	}
	for (i = 1; i <= n; i ++){
		infile>>father>>lc>>rc;
	}
	
	if (lc == 0 && rc == 0){
		bt1[father]->leftchild = NULL;
		bt1[father]->rightchild = NULL;
	}
	if (lc == 0 && rc != 0){
        bt1[father]->leftchild = NULL;
        bt1[father]->rightchild = bt1[rc];
	}
	if (lc != 0 && rc == 0){
        bt1[father]->leftchild = bt1[lc];
        bt1[father]->rightchild = NULL;
	}
	if (lc != 0 && rc != 0){
        bt1[father]->leftchild = bt1[lc];
        bt1[father]->rightchild = bt1[rc];
	}
	infile>>m;
	if(m!=n)
		cout<<"NO!";
	Node ** bt2 = new Node *[m + 1];
	for (i = 1; i <= m; i ++)
	{
        bt2[i] = new Node;
        bt2[i]->leftchild = NULL;
        bt2[i]->rightchild = NULL;
	}
	for (i = 1; i <= m; i ++){
		infile>>father>>lc>>rc;
	}
	
	if (lc == 0 && rc == 0){
		bt2[father]->leftchild = NULL;
		bt2[father]->rightchild = NULL;
	}
	if (lc == 0 && rc != 0){
        bt2[father]->leftchild = NULL;
        bt2[father]->rightchild = bt2[rc];
	}
	if (lc != 0 && rc == 0){
        bt2[father]->leftchild = bt2[lc];
        bt2[father]->rightchild = NULL;
	}
	if (lc != 0 && rc != 0){
        bt2[father]->leftchild = bt2[lc];
        bt2[father]->rightchild = bt2[rc];
	}
     if(Judge (bt1[1],bt2[1]))
		 outfile<<"Yes";
	 else
		 outfile<<"NO";
}