7-3 树的同构 (25 分)

简介: 7-3 树的同构 (25 分)

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

6cb725403e21bb6418b6cc1f19fb3027.jpg


a0f8a223a5b3a379c909798b9adefa56.jpg

现给定两棵树,请你判断它们是否是同构的。


输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。


输出格式:

如果两棵树是同构的,输出“Yes”,否则输出“No”。


输入样例1(对应图1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -


输出样例1:

Yes


输入样例2(对应图2):

1. 8
2. B 5 7
3. F - -
4. A 0 3
5. C 6 -
6. H - -
7. D - -
8. G 4 -
9. E 1 -
10. 8
11. D 6 -
12. B 5 -
13. E - -
14. H - -
15. C 0 2
16. G - 3
17. F - -
18. A 1 4


输出样例2:

No


#include<bits/stdc++.h>
using namespace std;
int a[20],b[20];
int main()
{
    int n,m;
    cin>>n;
    if(n==1)//只有一个节点的情况
    {
        cout<<"No\n";
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        char x,y,op;
        cin>>op>>x>>y;
        if(x!='-') a[op-'A']++;//记录一下第一棵树每个节点有多少个孩子
        if(y!='-') a[op-'A']++;
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        char x,y,op;
        cin>>op>>x>>y;
        if(x!='-') b[op-'A']++;//记录一下第二棵树每个节点有多少个孩子
        if(y!='-') b[op-'A']++;
    }
    for(int i=0;i<n;i++)
    {
        if(a[i]!=b[i])//判断两棵树每个孩子数量是否都相同
        {
            cout<<"No\n";
            return 0;
        }
    }
    cout<<"Yes\n";
    return 0;
}
目录
打赏
0
0
0
0
4
分享
相关文章
|
9月前
|
树的存储结构以及树,二叉树,森林之间的转换
树的存储结构以及树,二叉树,森林之间的转换
52 0
一次区分 B树、B+树,B*树
一次区分 B树、B+树,B*树
107 0
|
9月前
【代数学习题3】从零理解数域扩张与嵌入 —— 同构、商环、分裂域与同态映射
【代数学习题3】从零理解数域扩张与嵌入 —— 同构、商环、分裂域与同态映射
495 0
【数据结构oj】树的度(树和二叉树的相互转化)
【数据结构oj】树的度(树和二叉树的相互转化)
100 0
树的概念及结构(一篇足以让你认识树)(1)
树的概念及结构(一篇足以让你认识树)
155 0
树的概念及结构(一篇足以让你认识树)(1)
树的概念及结构(一篇足以让你认识树)(2)
树的概念及结构(一篇足以让你认识树)
177 0
树的概念及结构(一篇足以让你认识树)(2)
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)
315 0
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)