03-树1 树的同构 (25 分)
#include<cstdio>
#define null -1
const int maxn=15;
typedef int Tree;
typedef char ElementType;
struct TNode{
Tree left, right;
ElementType data;
int flag;
}T1[maxn], T2[maxn];
int check[maxn];
Tree BuildTree( struct TNode T[]){
Tree R=-1, cl, cr;
int n;
scanf("%d\n", &n);
for(int i=0; i<n; i++)check[i]=0;
for(int i=0; i<n; i++){
scanf("%c %c %c\n", &T[i].data, &cl, &cr);
if(cl!='-'){
T[i].left=cl - '0';
check[T[i].left]=1;
}else{
T[i].left=null;
}
if(cr!='-'){
T[i].right= cr-'0';
check[T[i].right]=1;
}else{
T[i].right=null;
}
}
for(int i=0; i<n; i++)
if(check[i]==0){
R=i;
break;
}
return R;
}
int Isomorphic(Tree R1, Tree R2){
if(R1==null && R2==null)return 1;
if((R1==null && R2!=null) || (R2==null && R1!=null))return 0;
if(T1[R1].data!=T2[R2].data)return 0;
if(T1[R1].left==null && T2[R2].left==null)
return Isomorphic(T1[R1].right, T2[R2].right);
if((T1[R1].left!=null&&T2[R2].left!=null)&&(T1[T1[R1].left].data==T2[T2[R2].left].data)){
return(Isomorphic(T1[R1].left, T2[R2].left)&&Isomorphic(T1[R1].right, T2[R2].right));
}else{
return(Isomorphic(T1[R1].right, T2[R2].left)&&Isomorphic(T1[R1].left, T2[R2].right));
}
}
int main(){
Tree R1, R2;
R1=BuildTree(T1);
R2=BuildTree(T2);
if(Isomorphic(R1, R2)){
printf("Yes");
}else{
printf("No");
}
return 0;
}
【测试点】