树的同构

给定两颗二叉树T1和T2，如果T1可以同过若干次左右孩子互换就变成T2，则我们称为两个树是同构的。现判断两棵树是否同构。

同构与不同构

【题目】

题意理解

第二棵树

【静态链表结构数组表示二叉树】

/* 静态链表二叉树 */
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree],T2[MaxTree];

/* 程序框架 */
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[])
{
    scanf("%d\n",&N);
    if(N){
        for(i=0;i<N;i++) check[i]=0; //check为标志位
            for(i=0;i<N;i++){
                scanf("%c %c %c\n",&T[i].Element,&cl,&cr);
                if(cl!='-'){
                    /*check不为空，则说明存在子孩子
                        则将子孩子处的check置1，即存在被指向
                        在树中check为0，即没有被指向的节点就是root
                    */
                    T[i].Left=cl-'0';
                    check[T[i].Left]=1;
                }
                else
                    T[i].Left=NULL;

                if(cr!='-'){
                    T[i].Right=cl-'0';
                    check[T[i].Right]=1;
                }
                else
                    T[i].Right=NULL;
            }
            for(i=0;i<N;i++) //判别check值为0
                if(!check[i])   break;
            Root=i;
    }
    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,T1[R1].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 ) );
}