//mooc第四讲小白专场判别两个二叉树是否同构 //输入C会出错,找不到原因
#include<stdio.h>
#include<stdlib.h>
#define Null -1
#define MaxTree 10
typedef char ElementType;
typedef int Tree;
struct TreeNode{
ElementType Element;
Tree Left;
Tree Right;
}T1[MaxTree],T2[MaxTree];
Tree BuildTree(struct TreeNode T[]);
int Isomorphic(Tree R1,Tree R2);
int main()
{
Tree R1,R2;
R1=BuildTree(T1);
R2=BuildTree(T2);
if(Isomorphic(R1,R2))printf("yes\n");
else printf("no\n");
return 0;
}
//建立树
Tree BuildTree(struct TreeNode T[])
{
int i,N,Root=Null;
char cl,cr;
printf("请输入树中元素的个数\n");
scanf("%d",&N);
int check[N];
if(N){
for(i=0;i<N;i++)check[i]=0;
for(i=0;i<N;i++){
printf("请输入T[%d]的Element、Left、Right,中间用空格隔开\n",i);
scanf("%c %c %c\n",&T[i].Element,&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(i=0;i<N;i++){
if(!check[i]){
Root=i;
break;
}
}
return Root;
}
//判断树是否同构
int Isomorphic(Tree R1,Tree R2)
{
if((R1==Null)&&(R2==Null))
return 1;
if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))
return 0;
if(T1[R1].Element!=T2[R2].Element)
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].Element==T2[T2[R2].Left].Element))
return (Isomorphic(T1[R1].Left,T2[R2].Left)&&Isomorphic(T1[R1].Right,T2[R2].Right));
else
return (Isomorphic(T1[R1].Left,T2[R2].Right)&&Isomorphic(T1[R1].Right,T2[R2].Left));
}