【PTA】树的同构 (25 分)

本文主要是介绍【PTA】树的同构 (25 分)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <iostream>
#include <algorithm>
#define MAXN 10
using namespace std;

struct node
{
    char c;
    int lchild;
    int rchild;
}T1[MAXN],T2[MAXN];

int root1=-1,root2=-1;
int check[MAXN];

int Istonggou(int r1,int r2){
    //判断此结点(全空，一边空，不等)
    if( (r1==-1) && (r2==-1) ) return 1;
    if( ( (r1==-1) && (r2!=-1) ) || ( (r1!=-1) && (r2==-1) ) )  return 0;
    if(T1[r1].c != T2[r2].c) return 0;

    //判断子结点（全空，全不空且相等，[一边空、全不空但不等]）
    if( (T1[r1].lchild==-1) && (T2[r2].lchild==-1) ){
        //没必要再写右孩子，return时会在“判断此节点”时判断
        return Istonggou(T1[r1].rchild,T2[r2].rchild);
    }

    if( (T1[r1].lchild!=-1) && (T2[r2].lchild!=-1) && 
    ( (T1[T1[r1].lchild].c) == T2[T2[r2].lchild].c)){
        return Istonggou(T1[r1].lchild,T2[r2].lchild) && 
        Istonggou(T1[r1].rchild,T2[r2].rchild);
    }else{
        return Istonggou(T1[r1].lchild,T2[r2].rchild) && 
        Istonggou(T1[r1].lchild,T2[r2].rchild);
    }

}

int ReadT(node T[]){
    int n1;
    cin>>n1;
    char tmp_lchild='-',tmp_rchild='-';
    int root=-1;

    fill(check,check+n1,0);

    for(int i=0;i<n1;i++){
        //此处只能用废容器在前面接住，
        //不能使用scanf("%c %c %c\n")，不然在我自己的IDE上无法运行
        //可能是某种输入规则?但是在PTA上是正确的，很奇怪..
        getchar();
        scanf("%c %c %c",&T[i].c,&tmp_lchild,&tmp_rchild);

        if(tmp_lchild != '-'){
            T[i].lchild=(int)(tmp_lchild-'0');
            check[T[i].lchild]=1;
        }
        else T[i].lchild=-1;

        if(tmp_rchild != '-'){
            T[i].rchild=(int)(tmp_rchild-'0');
            check[T[i].rchild]=1;
        }
        else T[i].rchild=-1;
    }

    for(int i=0;i<n1;i++){
        if(check[i]==0){
            root=i;
            break;
        }
    }

    return root;
}

int main(){
    
    root1=ReadT(T1);
    root2=ReadT(T2);

    if(Istonggou(root1,root2)==1) cout<<"Yes";
    else cout<<"No";



    return 0;
}

这篇关于【PTA】树的同构 (25 分)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！