树的同构

快来打我* 2023-05-31 12:14 36阅读 0赞

#include<stdio.h>
    
    typedef struct node
    { 
        char data;
        int l,r;
    }NODE;
    
    NODE t1[20],t2[20];
    int n,m;
    
    void build(NODE *t,int mm)
    { 
        int i;
        for(i=0; i<mm; i++)
        { 
            char s[10];
            scanf("%s",s);
            t[i].data=s[0];
            scanf("%s",s);
            if(s[0]=='-') t[i].l=-1;
            else t[i].l=s[0]-'0';
            scanf("%s",s);
            if(s[0]=='-') t[i].r=-1;
            else t[i].r=s[0]-'0';
        }
    }
    int judge(int i,int j)
    { 
        if(t1[t1[i].l].data==t2[t2[j].l].data&&t1[t1[i].r].data==t2[t2[j].r].data) 
            return 1;
        if(t1[t1[i].l].data==t2[t2[j].r].data&&t1[t1[i].r].data==t2[t2[j].l].data) 
            return 1;
        return 0;
    }
    void ok()
    { 
        int i,j;
        int flag=0;
        for(i=0; i<n; i++)
        { 
            for(j=0; j<m; j++)
            { 
                if(t1[i].data==t2[j].data)
                { 
                    if(judge(i,j)==0)
                    { 
                        flag=1;
                        break;
                    }
                    else 
                        break;
                }
            }
            if(flag==1)
                break;
            if(j==m)
            { 
                flag=1;
                break;
            }
        }
        if(flag) printf("No\n");
        else printf("Yes\n");
    }
    int main()
    { 
        while(~scanf("%d",&n))
        { 
            build(t1,n);
            scanf("%d",&m);
            build(t2,m);
            ok();
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，36人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的同构判断

一题意理解给定两颗树，T1，T2，若T1可以通过若干次的左右子互换变成T2，则称为这两棵树同构。二输入数据先输入一个N，代表接下来的个数，然后輸入N组元素，

小鱼儿/ 2023年07月02日 11:30/ 0 赞/ 137 阅读

相关树的同构

include<stdio.h> typedef struct node { char data; int

快来打我*/ 2023年05月31日 12:14/ 0 赞/ 37 阅读

相关 03-树1 树的同构

笔记： include<stdio.h> define MaxTree 10 define ElementType char def

亦凉/ 2022年07月28日 05:09/ 0 赞/ 165 阅读

相关 03-树1 树的同构

include<stdio.h> define MaxTree 10 define ElementType char define T

男娘i/ 2022年07月28日 05:08/ 0 赞/ 161 阅读

相关《数据结构》03-树1 树的同构

题目给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G

àì夳堔傛蜴生んèń/ 2022年05月15日 15:00/ 0 赞/ 207 阅读

相关 7-3 树的同构（25 分）

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互

小咪咪/ 2022年04月22日 07:14/ 0 赞/ 213 阅读

相关树的同构

这里给出一种O（N）判断两棵树是否同构的方法：首先找出两个树的重心，然后对这个重心进行树的哈希。然后比对哈希结果，没有找到例题，但是有一个判断多棵树是否同构的例题，因为

谁践踏了优雅/ 2021年11月04日 10:26/ 0 赞/ 355 阅读

相关 P5043 【模板】树同构（[BJOI2015]树的同构）

[传送门][Link 1] 哈希 $dfs$ 枚举所有节点，进入时哈希值加一个左括号，把所有儿子哈希值加入，退出时加一个右括号因为儿子的顺序可以任意，所以要把儿子哈希值

喜欢ヅ旅行/ 2021年10月29日 09:30/ 0 赞/ 314 阅读

相关 pta 编程题6 树的同构

其它pta数据结构编程题请参见：[pta][] 题目请参见：[树的同构][Link 1] 因题目中左右子树是按照下标给出，因此用数组存放树是更好的方法。判断两棵树是否同

逃离我推掉我的手/ 2021年10月24日 01:52/ 0 赞/ 282 阅读

相关有向树同构括号序列

include <cstdio> include <cstring> include <iostream> include <algorithm

本是古典何须时尚/ 2021年10月23日 14:14/ 0 赞/ 266 阅读