PTA 7-3 树的同构 C语言判断两棵树是否同构

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

图二

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

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

输出格式: 如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：

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（对应图2）：

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

程序框架

int main() { 建立二叉树1 建立二叉树2 判断同构并输出 return 0； }

思考：注意判断树的同构时，要注意利用递归函数，使程序简洁。 给出两个结点，判断同构时有几种情况： 从自身结点考虑：

两个结点都是空的，此时同构两个结点有一个是空的，另一个不是空的，此时一定不同构两结点都不空，但储存的值不一样，此时一定不同构

考虑完自身，再考虑孩子（注意考虑孩子时只考虑左孩子）： 4. 两个结点都没有左孩子，递归判断右孩子（此时不需要把两个结点都没有右孩子，递归判断左孩子单列，因为后面的判断包括了这种情况） 5. 结点R1有左孩子，结点R2没有左孩子

①. 左孩子对应的值相同，递归判断两者的右孩子 ②.左孩子对应的值不同，将R1左孩子和R2右孩子递归判断，R1右孩子和R2左孩子递归判断，判断时两者必须都同构，树才同构（因此用&&连接） 建议，为避免条件重复，每种情况之间最好用else if连接 函数实现：

Tree Is_the_same(Tree R1,Tree R2) { if((R1==Null)&&(R2==Null))//两颗空树！ return 1; else if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))//两颗树有一颗是空的 return 0; else if(T1[R1].Element!=T2[R2].Element)//两棵树的根结点的值不一样 return 0; else if((T1[R1].left==Null)&&(T2[R2].left==Null))//左子树都是空的，进而判断右子树是否为空 return Is_the_same(T1[R1].right,T2[R2].right); // else if((T1[R1].right==Null)&&(T2[R2].right==Null)) // return Is_the_same(T1[R1].left,T2[R2].left); else if((T1[R1].left!=Null)&& (T2[R2].left!=Null)); { if(T1[T1[R1].left].Element==T2[T2[R2].left].Element) return (Is_the_same(T1[R1].right,T2[R2].right)&&Is_the_same(T1[R1].right,T2[R2].right)); else return (Is_the_same(T1[R1].right,T2[R2].left)&&Is_the_same(T1[R1].left,T2[R2].right)); } }

完整代码：

#include<stdio.h> #include <stdlib.h> #include <string.h> #include<malloc.h> #define MaxTree 10//储存数据元素的最大个数 #define ElementType char #define Tree int #define Null -1//不能定义为NULL，因为NULL为0，但0也是一个数组下标 //结构数组表示二叉树：静态链表 struct TreeNode { ElementType Element; Tree left; Tree right;//左右孩子的数组下标 }T1[MaxTree],T2[MaxTree]; Tree gen(struct TreeNode T[]) { int i,sum; char cl,cr; int Root=Null; int flag[100]={0}; scanf("%d\n",&sum);//从这里开始控制格式 if(sum) { for(i=0;i<sum;i++) { scanf("%c %c %c\n",&T[i].Element,&cl,&cr);//控制字符输入格式 if(cl!='-') { cl=cl-'0'; T[i].left=cl; flag[T[i].left]=1; //flag[cl]=1; } else T[i].left=Null; if(cr!='-') { cr=cr-'0'; T[i].right=cr; flag[T[i].right]=1; //flag[cl]=1; } else T[i].right=Null; } for(i=0;i<sum;i++) { if(flag[i]==0) break; } Root=i; } return Root; } Tree Is_the_same(Tree R1,Tree R2) { if((R1==Null)&&(R2==Null))//两颗空树！ return 1; else if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))//两颗树有一颗是空的 return 0; else if(T1[R1].Element!=T2[R2].Element)//两棵树的根结点的值不一样 return 0; else if((T1[R1].left==Null)&&(T2[R2].left==Null))//左子树都是空的，进而判断右子树是否为空 return Is_the_same(T1[R1].right,T2[R2].right); // else if((T1[R1].right==Null)&&(T2[R2].right==Null)) // return Is_the_same(T1[R1].left,T2[R2].left); else if((T1[R1].left!=Null)&& (T2[R2].left!=Null)); { if(T1[T1[R1].left].Element==T2[T2[R2].left].Element) return (Is_the_same(T1[R1].right,T2[R2].right)&&Is_the_same(T1[R1].right,T2[R2].right)); else return (Is_the_same(T1[R1].right,T2[R2].left)&&Is_the_same(T1[R1].left,T2[R2].right)); } } int main() { Tree R1,R2; int tag=0; R1=gen(T1); R2=gen(T2); tag=Is_the_same(R1,R2); if(tag) printf("Yes"); else printf("No"); return 0; }