现给定两棵树，请你判断它们是否是同构的。 输入格式: 输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式: 如果两棵树是同构的，输出“Yes”，否则输出“No”。
思路：首先根据输入建树寻找根结点，然后分情况讨论，
都为空则同构一个为空一个不为空，不同构非空但根结点值不同，不同构左子树为空，就递归判断右子树左子树非空且data相同，就判断右子树左子树非空，但data不同就交换判断左右子树 #include <stdio.h> typedef struct TreeNode { char data; int Left; int Right; }TNode; //定义结构体 TNode T1[10], T2[10]; int CreatTree(TNode T[]); //创建树 int Isomorphic(int r1, int r2); //判断树是否同构 int main() { int r1, r2; r1 = CreatTree(T1); r2 = CreatTree(T2); if (Isomorphic(r1, r2)) printf("Yes"); else printf("No"); } int CreatTree(TNode T[]) { int n; scanf("%d", &n);//输入结点数 int i; int check[n]; int root = -1; for (i = 0; i < n; i++) check[i] = 0; for (i = 0; i < n; i++) { //getchar(); char cl, cr; scanf("\n%c %c %c", &T[i].data, &cl, &cr);//输入数据，左结点编号，右结点编号 if (cl == '-') T[i].Left = -1; else { T[i].Left = cl - '0'; check[T[i].Left] = 1; } if (cr == '-') T[i].Right = -1; else { T[i].Right = cr - '0';//字符串转数字 check[T[i].Right] = 1; } } for (i = 0; i < n; i++) if (check[i] == 0) { root = i; break; }//找寻根结点 return root; } int Isomorphic(int r1, int r2) { if (r1 == -1 && r2 == -1) //如果两颗树均为空，认为他们同构 return 1; if ((r1 == -1 && r2 != -1) || (r1 != -1 && r2 == -1)) //如果两棵树只有一颗为空，认为他们不同构 return 0; if (T1[r1].data != T2[r2].data) //如果两棵树根结点的值都不同，则不同构 return 0; if (T1[r1].Left == -1 && T2[r2].Left == -1) //l两棵树左边子树都为空就去递归的找他们的右子树 return Isomorphic(T1[r1].Right, T2[r2].Right); if ((T1[r1].Left != -1 && T2[r2].Left != -1) && (T1[T1[r1].Left].data == T2[T2[r2].Left].data)) { //如果左子树相同且左子树数据也相同 return Isomorphic(T1[r1].Left, T2[r2].Left) && Isomorphic(T1[r1].Right, T2[r2].Right);//然后递归的进入左右子树去判断是否同构 } else { //如果两个左子树有为空的或者两个左子树数据不相同，就交换左右子树递归的去判断 return Isomorphic(T1[r1].Left, T2[r2].Right) && Isomorphic(T1[r1].Right, T2[r2].Left); } }