73树的同构（25分）

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

图1

图2

输入格式:

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

输出格式:

如果两棵树是同构的&＃xff0c;输出“Yes”&＃xff0c;否则输出“No”。

输入样例1&＃xff08;对应图1&＃xff09;&＃xff1a;

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&＃xff08;对应图2&＃xff09;&＃xff1a;

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


输出样例2:

No

注意&＃xff1a;次一个节点并不是根节点&＃xff0c;根节点需要自己判断&＃xff0c;可以一边建树一边判断&＃xff0c;具体的注释在代码中。建树不难&＃xff0c;判断那部分较难&＃xff0c;很多人可能用的是指针形式

&＃xff0c;后面通过指针交换左右子树进行判断&＃xff0c;哪种方法极容易错&＃xff0c;而且麻烦&＃xff0c;可以直接根据是否为空&＃xff0c;不为空数值是否相等进行判断下面是C&＃43;&＃43;代码和C语言代码

#include
#include
#include
using namespace std;
#define NULL -1
struct node{char ch;int left;int right;
}tree1[100],tree2[100];
bool book[100];
//建树
int build(struct node tree []){int n;int book[110];char data,l,r;memset(book,0,sizeof(book));//将所有点初始化 scanf("%d",&n);for(int i &＃61; 0;i // printf("%c %c %c\n",data,l,r);tree[i].ch &＃61; data;//判断左右子树是否存在并标记 if(l &＃61;&＃61; &＃39;-&＃39;){tree[i].left &＃61; NULL;}else{tree[i].left &＃61; l-&＃39;0&＃39;;book[l-&＃39;0&＃39;] &＃61; 1;}if(r &＃61;&＃61; &＃39;-&＃39;){tree[i].right &＃61; NULL;}else{tree[i].right &＃61; r-&＃39;0&＃39;;book[r-&＃39;0&＃39;] &＃61; 1;}}int root&＃61;NULL;//这里一定要赋值为NULL for(int i &＃61; 0;i }
bool judge(int root1,int root2){if(root1 &＃61;&＃61;NULL&& root2&＃61;&＃61;NULL){//判断根节点是否都为空 return true;//都为空则相同 }if(root1&＃61;&＃61;NULL&&root2!&＃61;NULL||root1!&＃61;NULL&&root2&＃61;&＃61;NULL){return false;//一个根节点为空另外一个不为空则为假 }if(tree1[root1].ch!&＃61;tree2[root2].ch){return false;//两棵树根节点都存在&＃xff0c;但数值不同则为假 }if(tree1[tree1[root1].left].ch &＃61;&＃61; tree2[tree2[root2].left].ch){//如果左子树的值相等则判断右子树 return judge(tree1[root1].right,tree2[root2].right);}else{//否则判断是否第二棵树是在第一课树左右子树调换之后得到的 return judge(tree1[root1].left,tree2[root2].right)&&judge(tree1[root1].right,tree2[root2].left);}
}
int main(){
// freopen("input.txt","r",stdin);int root1 &＃61; build(tree1);int root2 &＃61; build(tree2);if(judge(root1,root2)){printf("Yes\n");}else{printf("No\n");}return 0;
}纯C代码和C&＃43;&＃43;代码思路一样&＃xff0c;只是部分语法不同不再解释。

#include
#include
#define NULL -1
struct node{int left,right;char data;
}tree1[100],tree2[100];
int book[1000];
int build(struct node tree[])
{int n,i,root;memset(book,0,sizeof(book));char left,right;scanf("%d",&n);getchar();for(i &＃61; 0;i // printf("%c %c %c\n",tree1[i].data,left,right);if(left &＃61;&＃61; &＃39;-&＃39;){tree[i].left &＃61; NULL;}else{tree[i].left &＃61; left-&＃39;0&＃39;;book[left-&＃39;0&＃39;] &＃61; 1;}if(right &＃61;&＃61; &＃39;-&＃39;){tree[i].right &＃61; NULL;}else{tree[i].right &＃61; right-&＃39;0&＃39;;book[right-&＃39;0&＃39;] &＃61; 1;}}root &＃61; NULL;for(i &＃61; 0;i }
int judge(int root1,int root2)
{if(root1 &＃61;&＃61; NULL&&root2 &＃61;&＃61; NULL){return 1;}if((root1 &＃61;&＃61; NULL&&root2 !&＃61; NULL)||(root1 !&＃61; NULL&&root2 &＃61;&＃61; NULL)){return 0;}if(tree1[root1].data !&＃61; tree2[root2].data){return 0;}if(tree1[tree1[root1].left].data &＃61;&＃61; tree2[tree2[root2].left].data){return judge(tree1[root1].right,tree2[root2].right);}elsereturn judge(tree1[root1].left,tree2[root2].right) &&judge(tree1[root1].right,tree2[root2].left); }
int main()
{
// freopen("input.txt","r",stdin);int root1,root2,i;root1 &＃61; build(tree1);root2 &＃61; build(tree2);
// for(i &＃61; 0;i <8;i&＃43;&＃43;)
// {
// printf("%c %d %d\n",tree1[i].data,tree1[i].left,tree1[i].right);
// }
// printf("\n");
// for(i &＃61; 0;i <8;i&＃43;&＃43;)
// {
// printf("%c %d %d\n",tree2[i].data,tree2[i].left,tree2[i].right);
// }if(judge(root1,root2)&＃61;&＃61;1){printf("Yes\n");}else{printf("No\n");}return 0;
}