判断两颗二叉树是否同构

//实验2，判断两颗二叉树是否同构
//假设二叉树采用二叉链存储结构存放，设计一个递归算法判断两颗
//二叉树是否同构。

//此程序包含多个二叉树基本算法

粘贴代码请粘贴前面的，后面只是方便观看，但是标点不对，网页自动转成中文标点了，内容都一样

#include<stdio.h>
#include<stdlib.h>
typedef struct isomorphism_btree//二叉树结点类型
{
    char data;//数据
   struct isomorphism_btree *lchild;
   struct isomorphism_btree *rchild;
  
}BTnode;
 BTnode* CreateBT(char *pre,char *in,int n)//根据先序序列和中序序列构造二叉树
 {
     BTnode *s;//根节点
     char *p;//用于在中序序列in中寻找先序序列pre的位置
     int k;//pre的位置
     if(n<=0)
     {
         return NULL;
     }
     s=(BTnode*)malloc(sizeof(BTnode));//创建根节点
    s->data=*pre;
    for(p=in;p<in+n;p++)//在in中寻找数据为*pre的位置k
    {
        if(*p==*pre)
         break;
    }
        k=p-in;
    s->lchild=CreateBT(pre+1,in,k);//先序序列为per+1开始的k个字符，中序序列为in开始的k个字符
    s->rchild=CreateBT(pre+k+1,p+1,n-k-1);//先序序列为pre+k+1的n-k-1个字符，中序序列为p+1开始n-k-1个字符
    return s;
    
 }

void disp(BTnode* b)//输出二叉树
{
    if(b!=NULL)//若树不为空则执行以下操作
    {
        printf("%d",b->data);//先输出根节点
        if(b->lchild!=NULL || b->rchild!=NULL)//左右子树至少有一个，分别输出左子树和右子树
        //因为递归调用，所以左子树右子树内部先不用管，逻辑上认为直接处理左子树和右子树
        {
            printf("(");
            disp(b->lchild);//输出左子树
                 if(b->rchild!=NULL)//若右子树不为空，表示有右子树，需要“，”分隔
               {
                printf(",");
               }
            disp(b->rchild);//输出右子树
            printf(")");

        }
    }
}

void Destroy(BTnode *b)//销毁二叉树算法
{
    if(b==NULL)//如果二叉树为空则直接返回，结束函数，作为递归出口
    {
        return;
    }
    else
    {
        Destroy(b->lchild);//分别销毁左右子树
        Destroy(b->rchild);
        free(b);//，销毁左右子树后只剩下一个根节点，直接释放
    }
}
bool isomorphism(BTnode *bt1,BTnode *bt2)//判断bt1和bt2是否同构
{
    if(bt1==NULL && bt2==NULL)//根据二叉树同构的定义，如果两个二叉树左右子树都同构或两个二叉树都为空则两个二叉树同构
    //此处判断是否两个二叉树都为空，且作为递归出口
    {    
        return true;
    }
    if((bt1==NULL && bt2!=NULL) || (bt1!=NULL && bt2==NULL))//同上判断。作为递归出口
    {
        return false;
    }
    bool l_ism=isomorphism(bt1->lchild,bt2->lchild);//判断左右子树是否同构
    bool r_ism=isomorphism(bt1->rchild,bt2->rchild);
    return l_ism & r_ism;
}
 main()
 {
     BTnode *bt1,*bt2,*bt3;
     char a[]={5,2,3,4,1,6};//先序序列
     char b[]={2,3,5,1,4,6};//中序序列
int n=sizeof(a)/sizeof(a[0]);
     bt1=CreateBT(a,b,n);

     char c[]={2,5,1,4,3,6};
     char d[]={5,1,2,3,4,6};
int m=sizeof(c)/sizeof(c[0]);
     bt2=CreateBT(c,d,n);

     char e[]={4,1,2,6,3,5};
     char f[]={2,1,4,3,6,5};
int k=sizeof(e)/sizeof(e[0]);
     bt3=CreateBT(e,f,n);
    
    printf("二叉树1：");
    disp(bt1);printf("\n");
    printf("二叉树2：");
    disp(bt2);printf("\n");
    printf("二叉树3：");
    disp(bt3);printf("\n");
if(isomorphism(bt1,bt2))
{
    printf("二叉树1和二叉树2同构\n");
}
else
{
    printf("二叉树1和二叉树2不同构\n");
}

  if(isomorphism(bt1,bt3))
{
    printf("二叉树1和二叉树3同构\n");
}  
else
{
    printf("二叉树1和二叉树3不同构\n");
}
Destroy(bt1);//销毁
Destroy(bt2);
Destroy(bt3);


 system("pause");
     return 0;
    
 }