个人站长做哪些网站好,做游戏开发需要学哪些技术,品牌宣传如何做,学做快餐的视频网站题目描述 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2#xff0c;则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的#xff0c;因为我们把其中一棵树的结点A、B、G的左右孩子互换后#xff0c;就得到另外一棵树。而图2就不是同构的。 图1 … 题目描述 给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的因为我们把其中一棵树的结点A、B、G的左右孩子互换后就得到另外一棵树。而图2就不是同构的。 图1 图2 现给定两棵树请你判断它们是否是同构的。 输入
输入数据包含多组每组数据给出2棵二叉树的信息。对于每棵树首先在一行中给出一个非负整数N (≤10)即该树的结点数此时假设结点从0到N−1编号随后N行第i行对应编号第i个结点给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空则在相应位置上给出”-”。给出的数据间用一个空格分隔。 注意题目保证每个结点中存储的字母是不同的。输出
如果两棵树是同构的输出“Yes”否则输出“No”。示例输入 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 - 示例输出 Yes 提示 测试数据对应图1 #include stdio.h #includestring.h #includestdlib.h typedef char element; typedef int Bment; typedef struct BNode { element data; BNode *lchild,*rchild; }*BiTree; struct node//存储树的根和子树的元素 { element root; Bment l,r; }p[20]; Bment sign[11];//标记左右子树是否存在 BiTree CreateBiTree(BiTree T,int n) //建立二叉树 { Tnew BNode; T-datap[n].root; T-lchildNULL; T-rchildNULL; if(p[n].l!-1) T-lchildCreateBiTree(T-lchild,p[n].l); if(p[n].r!-1) T-rchildCreateBiTree(T-rchild,p[n].r); return T; } int CompareBiTree(BiTree T,BiTree T1)//比较是否同构 { if(!T!T1)//空树同构 return 1; else if(TT1) { if(T-data!T1-data) return 0; else if((CompareBiTree(T-lchild,T1-lchild)CompareBiTree(T-rchild,T1-rchild))||(CompareBiTree(T-rchild,T1-lchild)CompareBiTree(T-lchild,T1-rchild)))//同构的条件 return 1; else return 0; } else return 0; } int main() { int n,i; char s[6],w[6],t[6];//存储根左右子树的值 while(~scanf(%d,n)) { memset(sign,0,sizeof(sign));//清零函数 for(i0;in;i) { scanf(%s%s%s,s,w,t); p[i].roots[0]; if(w[0]!-) { p[i].lw[0]-0; sign[p[i].l]1;//判断子树是否存在的标记 } else p[i].l-1; if(t[0]!-) { p[i].rt[0]-0; sign[p[i].r]1; } else p[i].r-1; } for(i0;in;i) { if(!sign[i]) break; } BiTree T; TCreateBiTree(T,i);//树的生成 scanf(%d,n); memset(sign,0,sizeof(sign));//初始化 for(i0;in;i) { scanf(%s%s%s,s,w,t); p[i].roots[0]; if(w[0]!-) { p[i].lw[0]-0; sign[p[i].l]1; } else p[i].l-1; if(t[0]!-) { p[i].rt[0]-0; sign[p[i].r]1; } else p[i].r-1; } for(i0;in;i) if(!sign[i]) break; BiTree T1; T1CreateBiTree(T1,i);//生成树 if(CompareBiTree(T,T1))//树是否同构 printf(Yes\n); else printf(No\n); } return 0; } #include bits/stdc.h #define null -1 using namespace std; struct node { char data; int lchild; int rchild; } T1[20], T2[20]; int creat(node T[], int N) { int knull; char c[2], lc[2], rc[2]; int check[20]; memset(check, 0, sizeof(check)); if(N) { for(int i 0; i N; i) { scanf(%s %s %s, c, lc, rc); T[i].data c[0]; if(lc[0] ! -) { T[i].lchild lc[0]-0; check[T[i].lchild] 1; } else T[i].lchild null; if(rc[0] ! -) { T[i].rchild rc[0]-0; check[T[i].rchild] 1; } else T[i].rchild null; } for(int j 0; j N; j) { if(!check[j]) { k j; break; } } } return k; } int judge(int R1, int R2) { if(R1 nullR2 null) return 1; if((R1 nullR2 ! null)||(R1 ! nullR2 null)) return 0; if(T1[R1].data ! T2[R2].data) return 0; if(T1[R1].lchild nullT2[R2].lchild null) return judge(T1[R1].rchild, T2[R2].rchild); if(T1[R1].lchild ! null T2[R2].lchild ! null T1[T1[R1].lchild].data T2[T2[R2].lchild].data) return (judge(T1[R1].lchild, T2[R2].lchild)judge(T1[R1].rchild, T2[R2].rchild)); return (judge(T1[R1].lchild, T2[R2].rchild)judge(T1[R1].rchild, T2[R2].lchild)); } int main() { int n, m; int R1, R2; while(~scanf(%d, n)) { R1 creat(T1, n); scanf(%d, m); R2 creat(T2, m); if(judge(R1, R2) 1) printf(Yes\n); else printf(No\n); } return 0; }
