mooc 树的同构

03-树1 树的同构 (25分)
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

图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];

//创建树，返回根
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; 
}

//用递归判断是否同构
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");
}