给定两棵树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];
10 
11 /* 构造树并返回根结点  */
12 int create(struct TreeNode T[])
13 {
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<n;i++)
23     {
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; //减
34         }
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         }        
42     }
43     return root;
44 }
45 /* 判断是否同构 */
46 int judge(int R1,int R2)
47 {
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()
71 {
72     int R1,R2;
73     R1 = create(T1);
74     R2 = create(T2);
75     if(judge(R1,R2))
76         printf("Yes");
77     else
78         printf("No");
79     return 0;
80 } 

c 代码

 1 #include<stdio.h>
 2 
 3 #define MaxTree 10
 4 #define ElementType char
 5 #define Tree int
 6 #define Null -1
 7 
 8 struct TreeNode
 9 {
10     ElementType Element;
11     Tree Left;
12     Tree Right;
13 } T1[MaxTree], T2[MaxTree];
14 
15 int Isomorphic ( Tree R1, Tree R2 );
16 Tree BuildTree( struct TreeNode T[] );
17 
18 int main()
19 {
20     Tree R1, R2;
21 
22     R1 = BuildTree(T1);
23     R2 = BuildTree(T2);
24     if (Isomorphic(R1, R2)) printf("Yes
");
25     else printf("No
");
26 
27     return 0;
28 }
29 
30 Tree BuildTree( struct TreeNode T[] )
31 {
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<N; i++) 
38         {
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;
43             }
44             else T[i].Left = Null;
45             
46             if (cr != '-') {
47                 T[i].Right = cr-'0';
48                 check[T[i].Right] = 1;
49             }
50             else T[i].Right = Null;
51         }
52         for (i=0; i<N; i++)
53             if (!check[i]) break;
54         Root = i;
55     }
56     return Root;
57 }
58 
59 int Isomorphic ( Tree R1, Tree R2 )
60 {
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 */
67     
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)) )
71     
72         return ( Isomorphic( T1[R1].Left, T2[R2].Left ) &&
73         Isomorphic( T1[R1].Right, T2[R2].Right ) );
74 
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代码