编辑代码

#include <stdio.h>
#include <malloc.h>
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

/*
    判断树是否同构，输入样例：
    8  结点数
    A 1 2  结点数据，指向的左孩子的下标，指向的右孩子的下标
    B 3 4
    C 5 - “-”表示没有指向孩子
    思路：
      1.二叉树的表示
           结构数组表示二叉树：静态链表
      2.建二叉树
      3.同构判别
*/

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

//判别是否同构
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) );
    }
}

//建树
Tree BuilderTree(struct TreeNode T[]){
    int N,i,Root;
    char cl,cr;
    printf("请输入结点数：\n");
    scanf("%d",&N);
    int check[10];
    if(N){
        for(i = 0;i < N;i++){
            /*
               check这个数组用于找出根结点
               用一个数组check，对应结构数组的N个结点，一开始的值全为0
               在读的过程中，如果一个结点有Left指向了某个位置，那么就把
               那个位置的check设为1（同理，Right也一样），整个循环完成后
               check为0的结点就是根结点
            */
            check[i] = 0;
        }
        //读入每一个结点
        for(i = 0;i < N;i++){
            printf("请输入第%d个结点：\n",i);
            scanf("%c %c %c\n",&T[i].Element,&cl,&cr);
            //左子树的处理
            if(cl != '-'){
                //减去字符0，转为整数
                T[i].Left = cl - '0';
                //把指向的结点的check值设为1
                check[T[i].Left] = 1;
            }else{
                T[i].Left = Null;
            }
            //右子树的处理
            if(cr != '-'){
                //减去字符0，转为整数
                T[i].Right = cr - '0';
                //把指向的结点的check值设为1
                check[T[i].Right] = 1;
            }else{
                T[i].Right = Null;
            }
        }
        //遍历check，找出根结点
        for(i = 0;i < N;i++)
            if(!check[i])
                break;
        Root = i;
    }
        return Root;
}

int main () {
    Tree R1,R2;
    
    //T1,T2为定义的全局变量，作为参数传进去
    R1 = BuilderTree(T1);
    R2 = BuilderTree(T2);
    if(isomorphic(R1,R2)){
        printf("Yes\n");
    }else{
        printf("NO\n");
    }
    return 0;
}