给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换 就变成T2，则我们称两棵树是 同构 的。
题意理解：何为同构，给你两棵树T1和T2，根、左子树、右子树是一样的，那么两个树是同构的；若根一样，左子树与右子树、右子树与左子树一样也认为是同构的。
解题思路：二叉树如何表示 ， 如何创建二叉树 ， 如何判别同构
一、二叉树如何表示，用结构体数组来表示二叉树，即静态链表的形式，物理上的存储是数组，思想是链表的思想，因此，结点序列存储不一致，也可以表示同一颗树，数组的每一个分量是一个结构，这个结构包含三个信息，一个是结点的信息，表示结点的，另外两个信息，是存储结点左右儿子位置的下标，空的结点用-1表示。
/*结点结构体*/struct TreeNode{ char data; // 存值 int left; // 左子树的下标 int right; // 右子树的下标 }T1[10],T2[10];//结构体数组表示树在结构体数组里，在左右儿子下标中没有出现的下标就是根结点的下标，可以通过遍历的方式找到，比如建立一个check数组存储下标是否出现过，整个check数组先初始化为0，出现过就赋值为1，最后可以遍历check数组可以判断根的下标；还可以累加下标，再减去出现的下标，结果就是根的下标。
二、如何创建二叉树，建一个二叉树的函数，最后返回的是树的根，循环输入每个结点的信息及左右儿子的信息，在输入过程中，处理左右儿子的信息，是空指针的用-1表示，否则保存左右儿子的下标，并对出现的下标进行处理，最后返回根结点的下标。
三、如何判别同构
1、两个树都是空的，是同构，函数返回1；
2、两个树一个空，另外一个不空，函数返回0；
3、两个树的信息不一样，函数返回0；
4、如果两个树的左子树是空的，递归判断右子树是否同构；
5、如果两个树的左子树不空且左子树的数据一样，递归判断左边（左为根）是否同构、右边（右为根）是否同构；
否则，两个树左子树与右子树，右子树与左子树，递归判断是否同构。
1 #include stdio.h 2 #include malloc.h 3 #define null -1 4 /* 定义树结点 */ 5 struct TreeNode{ 6 char data; // 存值 7 int left; // 左子树的下标 8 int right; // 右子树的下标 9 }T1[10],T2[10];11 /* 构造树并返回根结点 */12 int create(struct TreeNode T[])14 int n;15 int root = 0;16 char left, right;17 /* 输入结点数 */18 scanf("%d", n);19 /* 空树 */20 if(!n)21 return null;22 for(int i=0;i i++)24 /* 累加i*/25 root +=i; 26 /* 输入数据 */27 scanf(" %c %c %c", T[i].data, left, right);28 /* 1.left */29 if(left=='-')30 T[i].left = null;31 else{32 T[i].left = left-'0';33 root -= T[i].left; //减35 /* 2.right */36 if(right=='-')37 T[i].right = null;38 else{39 T[i].right = right-'0';40 root -= T[i].right;//减 41 } 43 return root;45 /* 判断是否同构 */46 int judge(int R1,int R2)48 /* 1.两棵树都为空 */49 if(R1 == null R2 == null)50 return 1;51 /* 2.一个为空，一个不为空 */52 if(R1 == null R2 != null || R1 != null R2 == null)53 return 0;54 /* 3.两颗树的值不同 */55 if(T1[R1].data != T2[R2].data) 56 return 0;57 /* 4.左儿子为空*/58 if(T1[R1].left == null T2[R2].left == null)59 return judge(T1[R1].right,T2[R2].right);60 /* 5.左儿子不为空且值相等*/61 if((T1[R1].left != null T2[R2].left != null )62 (T1[T1[R1].left].data == T2[T2[R2].left].data)) 63 return judge(T1[R1].left,T2[R2].left) 64 judge(T1[R1].right,T2[R2].right); 65 /* 6.左儿子不为空且值不等 或者 某一个树的左儿子为空*/66 else 67 return judge(T1[R1].right,T2[R2].left)68 judge(T1[R1].left,T2[R2].right); 69 } 70 int main()72 int R1,R2;73 R1 = create(T1);74 R2 = create(T2);75 if(judge(R1,R2))76 printf("Yes");77 else78 printf("No");79 return 0;80 } 1 #include stdio.h 3 #define MaxTree 10 4 #define ElementType char 5 #define Tree int 6 #define Null -1 8 struct TreeNode10 ElementType Element;11 Tree Left;12 Tree Right;13 } T1[MaxTree], T2[MaxTree];15 int Isomorphic ( Tree R1, Tree R2 );16 Tree BuildTree( struct TreeNode T[] );18 int main()20 Tree R1, R2;22 R1 = BuildTree(T1);23 R2 = BuildTree(T2);24 if (Isomorphic(R1, R2)) printf("Yes25 else printf("No27 return 0;30 Tree BuildTree( struct TreeNode T[] )32 int i, N, Root = Null, check[MaxTree]={0};33 char cl, cr;34 scanf("%d", N);35 if (N) 36 { 37 for (i=0; i i++) 39 scanf("%c %c %c", T[i].Element, cl, cr);40 if (cl != '-') {41 T[i].Left = cl-'0';42 check[T[i].Left] = 1;44 else T[i].Left = Null;46 if (cr != '-') {47 T[i].Right = cr-'0';48 check[T[i].Right] = 1;50 else T[i].Right = Null;52 for (i=0; i i++)53 if (!check[i]) break;54 Root = i;56 return Root;59 int Isomorphic ( Tree R1, Tree R2 )61 if ( (R1==Null ) (R2==Null) ) /* both empty */62 return 1;63 if ( ((R1==Null) (R2!=Null)) || ((R1!=Null) (R2==Null)) )64 return 0; /* one of them is empty */65 if ( T1[R1].Element != T2[R2].Element )66 return 0; /* roots are different */68 /* no need to swap the left and the right */69 if ( ((T1[R1].Left!=Null) (T2[R2].Left!=Null)) 70 ((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)) )72 return ( Isomorphic( T1[R1].Left, T2[R2].Left ) 73 Isomorphic( T1[R1].Right, T2[R2].Right ) );75 else /* need to swap the left and the right */76 return ( Isomorphic( T1[R1].Left, T2[R2].Right) 77 Isomorphic( T1[R1].Right, T2[R2].Left ) );78 }浙大c代码