PTA 5-3 树的同构 ——理解递归

 

 难点：

>>递归函数的实现

int Isomorphic(Tree R1,Tree R2)
{
    if(R1==Null&&R2==Null)
    return 1;
    if(R1==Null&&R2!=Null)
    return 0;
    if(R1!=Null&&R2==Null)
    return 0;
    if(T1[R1].Element!=T2[R2].Element)
    return 0;
    if(T1[R1].Left==Null&&T2[R2].Left==Null)
    return Isomorphic(T1[R1].Right,T2[R2].Right);
    if(T1[R1].Left!=Null&&T2[R2].Left!=Null&&T1[T1[R1].Left].Element==T2[T2[R2].Left].Element)
    return Isomorphic(T1[R1].Left,T2[R2].Left)&&Isomorphic(T1[R1].Right,T2[R2].Right);
    else
    return Isomorphic(T1[R1].Right,T2[R2].Left)&&Isomorphic(T1[R1].Left,T2[R2].Right);
}
1.由于首先在一行中给出一个非负整数N，考虑到N=0时Root=-1;
  即表示根节点找不到，注意Root！=0的原因是题目默认从0开始作为下标
2.该函数传入的参数可能为Null的原因：其一，当N=0时，根节点为Null；其二，递归过程可能会出现T1[R1].Right为Null或T2[R2].Right为Null的情况；
3.当Tree R1=-1时，则该结点无意义，不能访问T1[R1].Element；
4.注意参数顺序：Tree R1延伸的结点必须在左边，Tree R2的必须在右边，应为递归中始终是T1[R1]，T2[R2]；
5.注意分支语句的写法
左分支相等有两种情况：一，都为Null；二，都不为Null，且值相等
请他情况则考虑交叉相等

第五点的前提是，前面有对两个都为Null，其一为Null，两者都不为Null的讨论

#include<stdio.h> 

#define MaxTree 11
#define ElementType char
#define Tree int
#define Null -1
struct TreeNode
{
    ElementType Element;//树结点的值，字符 
    Tree Left; 
    Tree Right;
}T1[MaxTree],T2[MaxTree];
Tree BuildTree(struct TreeNode T[])
{
int N,i,Root=-1;
int check[11];
char cl,cr;
    scanf("%d",&N);
    getchar();
for(i=0;i<N;i++)
        check[i]=0;
if(!N)
return Null;
if(N)
    {    
for(i=0;i<N;i++)
        {
            scanf("%c %c %c",&T[i].Element,&cl,&cr);
            getchar();
if(cl!='-')
            {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
else
            T[i].Left=Null;
if(cr!='-')
            {
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            }
else
            T[i].Right=Null;
        }

    }
for(i=0;i<N;i++)
if(!check[i])
return i;
}
int Isomorphic(Tree R1,Tree R2)
{
if(R1==Null&&R2==Null)
return 1;
if(R1==Null&&R2!=Null)
return 0;
if(R1!=Null&&R2==Null)
return 0;
if(T1[R1].Element!=T2[R2].Element)
return 0;
if(T1[R1].Left==Null&&T2[R2].Left==Null)
return Isomorphic(T1[R1].Right,T2[R2].Right);
if(T1[R1].Left!=Null&&T2[R2].Left!=Null&&T1[T1[R1].Left].Element==T2[T2[R2].Left].Element)
return Isomorphic(T1[R1].Left,T2[R2].Left)&&Isomorphic(T1[R1].Right,T2[R2].Right);
else
return Isomorphic(T1[R1].Right,T2[R2].Left)&&Isomorphic(T1[R1].Left,T2[R2].Right);
}
int main()
{
    Tree R1,R2;
    R1=BuildTree(T1);
    R2=BuildTree(T2);
if(Isomorphic(R1,R2))
    printf("Yes\n");
else
    printf("No\n");
return 0;
}