pat 树的同构 判断两棵树是否同构

Question

如题 判断两棵树是同构的

自己的方法怎么也想不通哪里的错误

o(╥﹏╥)o

#include <iostream>
using namespace std;
#define elementtype char
#define  tree int
#define null -1
#define maxsize 10
struct treenode{
    elementtype element;
    tree left;
    tree right;
}T1[maxsize],T2[maxsize];
tree maketree(struct treenode T[]);
tree judge(tree R1,tree R2);
int check[maxsize],N;

int main(){
    tree R1,R2;
    R1=maketree(T1);
    R2=maketree(T2); 
    if(judge(R1,R2)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
tree maketree(struct treenode T[]){ //建树并且返回根节点 
    int i;
    tree root=null;
    char cl,cr;
    cin>>N;
    if(N){
         for(i=0;i<N;i++) check[i]=0;//check 数组用来记录各个节点是否已经被指向过，没有则为0 
         for(i=0;i<N;i++){
            cin>>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]) break;            //如果给出的数据是两棵树 bug  以前者的那个根为树的根 后者被忽略 
            root=i;
    //  }   不能加括号 加了括号break直接跳出 不在进行root=i 
    }
    return root;
}


//这是正确的做法
/*tree judge(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 judge(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))//都有左节点1.左节点数据相同 
        return (judge(T1[R1].left,T2[R2].left)&&judge(T1[R1].right,T2[R2].right));          //向左递归 
        else            //其他 左节点不一定都有 左节点数据不一定相同 
            return (judge(T1[R1].left,T2[R2].right)&&judge(T1[R1].right,T2[R2].left));
}*/



//我写的
tree judge(tree R1,tree R2){//判断两棵树是否为同一颗树
    if ((R1==null&&R2==null)||(R1!=null&&R2!=null&&T1[R1].element ==T2[R2].element )) return 1; 
        else return 0;          //都空 都存在且数据相同 
    if (T1[R1].left!=null&&T2[R2].left!=null&&T1[R1].left ==T2[R2].left ) //左树的左子比较右树的左右子
    return (judge(T1[R1].left ,T2[R2].left ))&&(judge(T1[R1].right ,T2[R2].right ));//&&(judge(T1[R1].right ,T2[R2].right ))
        else if(T1[R1].left!=null&&T2[R2].right !=null&&T1[R1].left ==T2[R2].right )
                return (judge(T1[R1].left,T2[R2].right  ))&&(judge(T1[R1].right ,T2[R2].left ));//&&(judge(T1[R1].right ,T2[R2].left ))
        else return 0;
    if (T1[R1].right!=null&&T2[R2].left!=null&&T1[R1].right ==T2[R2].left )//左树的右子比较右树的左右子 
        return (judge(T1[R1].right ,T2[R2].left ))&&(judge(T1[R1].left ,T2[R2].right ));//&&(judge(T1[R1].left ,T2[R2].right ))
        else if(T1[R1].right!=null&&T2[R2].right!=null&&T1[R1].right ==T2[R2].right )
                return (judge(T1[R1].right,T2[R2].right  ))&&(judge(T1[R1].left ,T2[R2].left ));//&&(judge(T1[R1].left ,T2[R2].left ))
                else return 0;
}

Answer 1

https://blog.csdn.net/qq_42673507/article/details/85264010