首页 > 代码库 > SDUT 3340 数据结构实验之二叉树一:树的同构
SDUT 3340 数据结构实验之二叉树一:树的同构
数据结构实验之二叉树一:树的同构
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic
Problem Description
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。
图1
图2
现给定两棵树,请你判断它们是否是同构的。
Input
输入数据包含多组,每组数据给出2棵二叉树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N?1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出”-”。给出的数据间用一个空格分隔。
注意:题目保证每个结点中存储的字母是不同的。
注意:题目保证每个结点中存储的字母是不同的。
Output
如果两棵树是同构的,输出“Yes”,否则输出“No”。
Example Input
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 -
Example Output
Yes
DQE:
二叉树的同构,类似化学上的同分异构体,本题要求简单,利用结构体和指针数组接受数据,用O(N)时间的循环组织数据建立二叉树,再用O(N)时间的循环找出唯一没有双亲的节点作为树的根,再仿照化学上的同分异构体判定两颗二叉树是否同构即可。
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 struct Tree 7 { 8 char c,l,r; 9 Tree *pr,*lt,*rt; 10 }; 11 Tree *f[12]; 12 13 Tree *creat(int n) 14 { 15 int i; 16 for(i=0;i<n;i++) 17 { 18 if(f[i]->l!=‘-‘) 19 { 20 f[ f[i]->l-48 ]->pr=f[i]; 21 f[i]->lt=f[ f[i]->l-48 ]; 22 } 23 if(f[i]->r!=‘-‘) 24 { 25 f[ f[i]->r-48 ]->pr=f[i]; 26 f[i]->rt=f[ f[i]->r-48 ]; 27 } 28 } 29 for(i=0;i<n;i++) 30 { 31 if(f[i]->pr==NULL) 32 return f[i]; 33 } 34 return NULL; 35 } 36 37 bool cmp(Tree *r1,Tree *r2) 38 { 39 if(r1==NULL&&r2==NULL) 40 return true; 41 else if(r1==NULL||r2==NULL) 42 return false; 43 if(r1->c!=r2->c) 44 return false; 45 if( ( cmp(r1->lt,r2->lt)&&cmp(r1->rt,r2->rt) ) || ( cmp(r1->lt,r2->rt)&&cmp(r1->rt,r2->lt) ) ) 46 return true; 47 return false; 48 } 49 50 int main() 51 { 52 Tree *r1,*r2; 53 int n,m; 54 while(scanf("%d",&n)!=EOF) 55 { 56 char a[3],b[3],c[3]; 57 int i; 58 for(i=0;i<n;i++) 59 { 60 f[i]=new Tree; 61 scanf("%s%s%s",a,b,c); 62 f[i]->c=*a; 63 f[i]->l=*b; 64 f[i]->r=*c; 65 f[i]->pr=f[i]->lt=f[i]->rt=NULL; 66 } 67 r1=creat(n); 68 69 scanf("%d",&m); 70 for(i=0;i<m;i++) 71 { 72 f[i]=new Tree; 73 scanf("%s%s%s",a,b,c); 74 f[i]->c=*a; 75 f[i]->l=*b; 76 f[i]->r=*c; 77 f[i]->pr=f[i]->lt=f[i]->rt=NULL; 78 } 79 r2=creat(m); 80 81 if(cmp(r1,r2)) 82 printf("Yes\n"); 83 else 84 printf("No\n"); 85 } 86 return 0; 87 } 88 89 /*************************************************** 90 User name: *** 91 Result: Accepted 92 Take time: 0ms 93 Take Memory: 156KB 94 Submit time: 2016-11-04 20:08:40 95 ****************************************************/
SDUT 3340 数据结构实验之二叉树一:树的同构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。