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

图1

图2

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

输入格式:

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

输出格式:

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

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

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

输出样例1:

Yes

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

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

输出样例2:

No
算法实现及思路

#include <stdio.h>#define MaxTree 10#define ElementType char#define Tree int#define Null -1//定义二叉树的结点//采用结构数组存储二叉树struct TreeNode{ElementType Element;Tree left;Tree right;}T1[MaxTree],T2[MaxTree];int check[MaxTree];//check数组用来检查谁是根节点//建树函数Tree BuildTree(struct TreeNode T[]){int N,i;Tree Root=Null;char cl,cr;scanf("%d\n",&N);if(N){for(i=0;i<N;i++) check[i]=0;//初始check数组全部置0for(i=0;i<N;i++){scanf("%c %c %c\n", &T[i].Element,&cl,&cr);if(cl!='-'){T[i].left=cl-'0';check[T[i].left]=1;//指向的结点check值设置为1}else{T[i].left=Null;//若结点指向为空,则将left设置为-1}// 右结点同理if(cr!='-'){T[i].right=cr-'0';check[T[i].right]=1;}else{T[i].right=Null;}}for(i=0;i<N;i++){//若没有任何结点指向的那一个结点 就是该树的根节点if(!check[i]) break;}Root =i;//值赋给根并返回}return Root;}//递归比较左右结点是否相等,若两结点相等int lsomorphic(Tree R1,Tree R2){//比较是否两棵树是否同构if((R1==Null)&&(R2==Null))//若同为空结点,返回1return 1;if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))//若 一个空,一个不空,肯定不同构,返回0return 0;if(T1[R1].Element!=T2[R2].Element)//若两结点不空,但是值不相等,肯定不同构,返回0return 0;if((T1[R1].left==Null)&&(T2[R2].left==Null))//若两棵树的结点都没有左子树,则比较右子树return lsomorphic(T1[R1].right,T2[R2].right);//若两棵树的当前左结点相等,递归比较左右子结点if(((T1[R1].left!=Null)&&(T2[R2].left!=Null))&&((T1[T1[R1].left].Element)==(T2[T2[R2].left].Element)))return (lsomorphic(T1[R1].left,T2[R2].left)&&lsomorphic(T1[R1].right,T2[R2].right) );else//若左右子结点互换同构,则互换比较return (lsomorphic(T1[R1].left,T2[R2].right)&&lsomorphic(T1[R1].right,T2[R2].left));
}int main(){ Tree R1,R2; R1=BuildTree(T1); R2=BuildTree(T2); if(lsomorphic(R1,R2)) printf("Yes\n"); else printf("No\n"); return 0;
}