首页 > 代码库 > PAT-树的同构
PAT-树的同构
链接
树的同构
题意
同构的定义: 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。
给两棵树,判断是否同构
做法
先建树,然后判断,知道怎么判断就知道怎么写了,具体实现看代码
代码
/* Name: hello world.cpp Author: AA Description: 唯代码与你不可辜负*/#include<bits/stdc++.h>using namespace std;#define LL long long#define maxn 20100typedef struct Node { char data; int left; int right;} Tree;Tree t1[maxn], t2[maxn];int build(Tree T[]) { int n, cherk[maxn], root = -1; char cl, cr; scanf("%d", &n); getchar(); if(n) { for(int i = 0; i < n; i++) cherk[i] = 0; for(int i = 0; i < n; i++) { scanf("%c %c %c", &T[i].data, &cl, &cr); getchar(); if(cl != ‘-‘) { T[i].left = cl - ‘0‘; cherk[T[i].left] = 1; } else T[i].left = -1; if(cr != ‘-‘) { T[i].right = cr - ‘0‘; cherk[T[i].right] = 1; } else T[i].right = -1; } for(int i = 0; i < n; i++) { if(cherk[i] == 0) { root = i; break; } } } return root;}bool Isomorphic(int root1, int root2) { if(root1 == -1 && root2 == -1) return true;//都是空的,符合 else if((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) return false; //一个空一个不空当然不符合 else if(t1[root1].data != t2[root2].data) return false; //元素不相等不符合 else if(t1[root1].left == -1 && t2[root2].left == -1) //左子树都是空的话,就判断右子树 return Isomorphic(t1[root1].right, t2[root2].right); else if(t1[t1[root1].left].data =http://www.mamicode.com/= t2[t2[root2].left].data)//左子树的元素都相同的话就把他们的左右子树都判断 return (Isomorphic(t1[root1].left, t2[root2].left) && Isomorphic(t1[root1].right, t2[root2].right)); else //最后是把左右子树交换来判断 return (Isomorphic(t1[root1].left, t2[root2].right) && Isomorphic(t1[root1].right, t2[root2].left));}int main() { int root1, root2; root1 = build(t1); root2 = build(t2); if(Isomorphic(root1, root2)) puts("Yes"); else puts("No");}
?
PAT-树的同构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。