这一题是课上例题，用到的递归思想较为关键。
1 #include2 #include 3 #define MaxTreeNodes 10 4 5 struct TreeNode{ 6 char Element; 7 int Left; 8 int Right; 9 };10 typedef struct TreeNode FullTree;11 FullTree T1[MaxTreeNodes], T2[MaxTreeNodes];12 13 int BuildTree(FullTree T[])14 {15 int Root;16 int i = -1, N;17 int check[10];18 char cl, cr;19 scanf("%d\n", &N); //'\n'一定要加！！20 if(N){21 for(i = 0; i < N; i++){22 check[i] = 0; //check[N]中没有被指向都为0，指向了就赋值为1，最后没被指向的就是根节点23 }24 for(i = 0; i < N; i++){25 scanf("%c %c %c\n", &T[i].Element, &cl, &cr);26 if(cl == '-')27 T[i].Left = -1;28 else{29 T[i].Left = cl - '0';30 check[T[i].Left] = 1;31 }32 if(cr == '-')33 T[i].Right = -1;34 else{35 T[i].Right = cr - '0';36 check[T[i].Right] = 1;37 }38 }39 for(i = 0; i < N; i++){40 if(!check[i])41 break;42 }43 }44 Root = i;45 return Root;46 }47 48 int isOmorphic(int R1, int R2)49 {50 if((R1 == -1) && (R2 == -1))51 return 1;52 if(((R1 != -1) && (R2 == -1)) || ((R1 == -1) && (R2 != -1)))53 return 0;54 if(T1[R1].Element != T2[R2].Element)55 return 0;56 if((T1[R1].Left == -1) && (T2[R2].Left == -1))57 return isOmorphic(T1[R1].Right, T2[R2].Right);58 if((T1[R1].Left != -1) && (T2[R2].Left != -1)59 && (T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element))60 return (isOmorphic(T1[R1].Left, T2[R2].Left) && isOmorphic(T1[R1].Right, T2[R2].Right));61 else62 return (isOmorphic(T1[R1].Left, T2[R2].Right) && isOmorphic(T1[R1].Left, T2[R2].Right));63 }64 65 int main(int argc, char const *argv[])66 {67 int R1, R2;68 R1 = BuildTree(T1);69 R2 = BuildTree(T2);70 if(isOmorphic(R1, R2))71 printf("Yes\n");72 else73 printf("No\n");74 return 0;75 }
一开始没有加第20行的if(N)导致空树情况下总是错误，后来意识到虽然空树时没有进入循环，但是循环判断条件if语句还是执行了的，期间会使得i重置为0，使得Root结果错误。