Description
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
现给定两棵树，请你判断它们是否是同构的。
Input
输入数据包含多组，每组数据给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出”-”。给出的数据间用一个空格分隔。 注意：题目保证每个结点中存储的字母是不同的。
Output
如果两棵树是同构的，输出“Yes”，否则输出“No”。
Sample Input 1
8
A12
B34
C5-
D--
E6-
G7-
F--
H--
8
G-4
B76
F--
A51
H--
C0-
D--
E2-
Sample Output 1
Yes
Sample Input 2
8
B57
F--
A03
C6-
H--
D--
G4-
E1-
8
D6-
B5-
E--
H--
C02
G-3
F--
A14
Sample Output 2
No
Hint
样例输入/输出1对于上图1，样例输入/输出2对于上图2
参考程序（C语言实现）
非递归算法；特别注意数据输入时，这是一个难点，getchar()
用于消去一个换行。
#include <stdio.h>
#include <stdlib.h>
#define ROOM sizeof(struct TreeNode)
#define LEN 10
struct TreeNode
{
char data;
struct TreeNode *LeftChild;
struct TreeNode *RightChild;
};
struct LinkInformation
{
/*数据结构说明，构建的结点属于嵌套定义，由两部分组成：
1.一个字符数组，存储结点值即左子结点地址和右子结点地址（数字），例如“B 5 7”
2.二叉树中的结点*/
char info[10];
struct TreeNode *Node;
};
int main()
{
struct LinkInformation Tree_1[LEN],Tree_2[LEN];//两个表示树中结点链接信息的表格（结构体数组）
struct TreeNode *NULL_Node;
NULL_Node=(struct TreeNode*)malloc(ROOM);
NULL_Node->data='0';
/*构建“空结点”，相当于“NULL”.考虑到后面涉及对结点值进行比较，此时若结点为NULL（主存为空），是没有结点值的，会发生异常*/
int NodeNum_1,NodeNum_2,i;
while(scanf("%d",&NodeNum_1)!=EOF)
{
getchar();
for(i=0;i<NodeNum_1;i++)
{
scanf("%c %c %c",&Tree_1[i].info[0],&Tree_1[i].info[1],&Tree_1[i].info[2]);
getchar();
Tree_1[i].Node=(struct TreeNode*)malloc(ROOM);
Tree_1[i].Node->data=Tree_1[i].info[0];
}
scanf("%d",&NodeNum_2);
getchar();
for(i=0;i<NodeNum_2;i++)
{
scanf("%c %c %c",&Tree_2[i].info[0],&Tree_2[i].info[1],&Tree_2[i].info[2]);
getchar();
Tree_2[i].Node=(struct TreeNode*)malloc(ROOM);
Tree_2[i].Node->data=Tree_2[i].info[0];
}
for(i=0;i<NodeNum_1;i++)//根据二叉树的链接信息表，对第1棵树的结点链接情况进行完善
{
if(Tree_1[i].info[1]=='-')
{
Tree_1[i].Node->LeftChild=NULL_Node;
}
else
{
Tree_1[i].Node->LeftChild=Tree_1[ Tree_1[i].info[1]-'0' ].Node;
/*此处涉及数据类型的准换，需要将字符转换为数字*/
}
if(Tree_1[i].info[2]=='-')
{
Tree_1[i].Node->RightChild=NULL_Node;
}
else
{
Tree_1[i].Node->RightChild=Tree_1[ Tree_1[i].info[2]-'0' ].Node;
}
}
for(i=0;i<NodeNum_2;i++)
{
if(Tree_2[i].info[1]=='-')
{
Tree_2[i].Node->LeftChild=NULL_Node;
}
else
{
Tree_2[i].Node->LeftChild=Tree_2[ Tree_2[i].info[1]-'0' ].Node;
}
if(Tree_2[i].info[2]=='-')
{
Tree_2[i].Node->RightChild=NULL_Node;
}
else
{
Tree_2[i].Node->RightChild=Tree_2[ Tree_2[i].info[2]-'0' ].Node;
}
}
if(NodeNum_1!=NodeNum_2)
{
printf("No\n");
}
else
{
int flag=1;
for(i=0;i<NodeNum_1;i++)//对第1棵树的表进行遍历，即对每个结点进行检验
{
int j;
for(j=0;j<NodeNum_2;j++)//在第2棵树的表中，查找结点值相同的结点
{
if(Tree_1[i].Node->data==Tree_2[j].Node->data)
{
break;
}
}
if(j==NodeNum_1)
{
flag=0;
break;//没有找到，置flag为0，退出
}
else
{
//找到，进一步对两个结点的左右子结点值进行比较：
if( (Tree_1[i].Node->LeftChild->data==Tree_2[j].Node->LeftChild->data
&& Tree_1[i].Node->RightChild->data==Tree_2[j].Node->RightChild->data)
|| (Tree_1[i].Node->LeftChild->data==Tree_2[j].Node->RightChild->data
&& Tree_1[i].Node->RightChild->data==Tree_2[j].Node->LeftChild->data))
{
flag*=1;//结点满足上述情况，置当前flag为1， 再与前面的flag值相与
}
else
{
flag*=0;//只要存在一个结点不满足上述情况，置当前flag为0， 再与前面的flag值相与
}
}
if(!flag)
{
break; //只要运算后当前flag为0，后面的结点无需比较，直接退出
}
}
if(flag)
{
printf("Yes\n"); //所有结点的flag均为1，则同构
}
else
{
printf("No\n");
}
}
}
return 0;
}
//by jialChen
编程小白，水平有限。上面代码如有任何问题欢迎各界人士批评指正，不吝赐教，感谢！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: