#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef char ElemType;
typedef ElemType SqBinTree[MaxSize];
typedef struct node
{ ElemType date;
struct node *lchild;//左孩子结点
struct node *rchild;//右孩子结点
} BTNode;
void CreateBTree(BTNode *&b,char *str)//创建二叉树
{ BTNode *St[MaxSize],*p;//St数组作为顺序栈
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')//循环扫描st中的字符
{ switch(ch)
{ case'('://左孩子
top++;
St[top]=p;
k=1;break;
case')':
top--;
break;
case','://右孩子
k=2;
break;
default:
p=(BTNode *)malloc(sizeof(BTNode));
p->date=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)//尚未建立根节点
b=p;//p所指向的为根节点
else
{ switch(k)
{ case 1:
St[top]->lchild=p;
break;
case 2:
St[top]->rchild=p;
break;
}
}
}
j++;
ch=str[j];
}
}
void DestroyBTree(BTNode *&b)//销毁二叉树
{ if(b!=NULL)
{ DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
void DispBTree(BTNode *b)//输出二叉树
{ if(b!=NULL)
{ printf("%2c",b->date);
if(b->lchild!=NULL || b->rchild!=NULL)
{ printf("(");
DispBTree(b->lchild);
if(b->rchild!=NULL)
printf(",");
DispBTree(b->rchild);
printf(")");
}
}
}
bool Like(BTNode *b1,BTNode *b2)//【7.15】判断两棵二叉树是否相似
{ bool like1=false,like2=false;
if(b1==NULL && b2==NULL)
return true;
else if(b1==NULL || b2==NULL)
return false;
else
{ like1=Like(b1->lchild,b2->lchild);
like2=Like(b1->rchild,b2->rchild);
return (like1&&like2);
}
}
int main()
{ BTNode *t,*t1;
int jds,sd,n;
char x;
bool like;
char str[MaxSize]="A(B(D,E),C(F,G))";
char str1[MaxSize]="A(B(D,E),C(H,I))";//用于比较的树str1
CreateBTree(t,str);
CreateBTree(t1,str1);
printf("用于比较的两棵树:\n");
printf("t:");
DispBTree(t);
printf("\n");
printf("t1:");
DispBTree(t1);
printf("\n");
like=Like(t,t1);
printf("比较结果是否相似:");
if(like==1)
printf("true");
else
printf("false");
printf("\n");
return 0;
}
