03-樹(shù)1 樹(shù)的同構(gòu) (25分)
給定兩棵樹(shù)T1和T2阁危。如果T1可以通過(guò)若干次左右孩子互換就變成T2涉茧，則我們稱(chēng)兩棵樹(shù)是“同構(gòu)”的。例如圖1給出的兩棵樹(shù)就是同構(gòu)的琴锭，因?yàn)槲覀儼哑渲幸豢脴?shù)的結(jié)點(diǎn)A晰甚、B、G的左右孩子互換后决帖，就得到另外一棵樹(shù)厕九。而圖2就不是同構(gòu)的。
圖1
圖2
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
#define Tree int
#define ElementType char
#define Null -1
struct TreeNode{
ElementType Element;
Tree Left,Right;
}T1[MaxSize],T2[MaxSize];
//創(chuàng)建樹(shù)地回，返回根
Tree BuildTree(struct TreeNode T[]){
int n;
int check[MaxSize];
for(int i=0;i<MaxSize;i++) check[i]=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
char b,c;
scanf("%c %c %c",&T[i].Element,&b,&c);
if(b!='-'){
T[i].Left=b-'0';
check[T[i].Left]=1;
}
else{
T[i].Left=Null;
}
if(c!='-'){
T[i].Right=c-'0';
check[T[i].Right]=1;
}
else{
T[i].Right=Null;
}
}
for(int i=0;i<n;i++){
if(!check[i]) break;
}
return i;
}
//用遞歸判斷是否同構(gòu)
int IsSame(Tree r1,Tree r2)
{
if(r1 == Null && r2 == Null) return 1;
if(r1 == Null && r2 != Null||r1 != Null && r2 == Null) return 0;
if(r1 != Null && r2 != Null && T1[r1].Element != T2[r2].Element) return 0;
if(T1[r1].Left == Null && T2[r2].Left == Null) return IsSame(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 IsSame(T1[r1].Right,T2[r2].Right)&&IsSame(T1[r1].Left,T2[r2].Left);
else return IsSame(T1[r1].Left,T2[r2].Right) && IsSame(T1[r1].Right,T2[r2].Left);
}
int main()
{
//freopen("in.txt","r",stdin);
Tree R1,R2;
R1=BuildTree(T1);
R2=BuildTree(T2);
if(IsSame(R1,R2)) printf("Yes");
else printf("No");
}
