二叉树深度宽度相似度的c实现
求二叉树深度，宽度，判断是否相似。
#include
#include
#include
#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T)//建立二叉树
{
TElemType e;
scanf("%d",&e);
if(e==0) T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data =e;
CreateBiTree(T->lchild );
CreateBiTree(T->rchild );
}
return OK;
}
int max(int a[])
{
int max,i;
max=a[0];
for(i=1;i
{
if(max
max=a[i];
}
return max;
}
int BiTreeWidth (BiTree T)//递归求二叉树的宽度
{
if(T==NULL)
return 0;
else
{
static int a[20]={0};
static int i=0;
a[i]++;
i++;
BiTreeWidth (T->lchild );
if(T->lchild ==NULL)
i--;
BiTreeWidth (T->rchild );
if(T->rchild ==NULL)
i--;
return max(a);
}
}
bool Similar(BiTree &t1,BiTree &t2)//递归求二叉树是否相似 {
if(t1==NULL&&t2==NULL)
return(true);
else if(t1!=NULL&&t2!=NULL)
{
if ( ! Similar(t1->lchild,t2->lchild))
return(false);
if (! Similar(t1->rchild,t2->rchild))
return(false);
return(true);
}
else
return(false);
}
int GetBiTreeDepth(BiTree &T)//递归求二叉树的深度 {
if(T==NULL) return 0;
else
{
int d1=GetBiTreeDepth(T->lchild);
int d2=GetBiTreeDepth(T->rchild);
if(d1>=d2)
return 1+d1;
else
return 1+d2;
}
}
void main()
{
BiTree T,T1;
printf("请输入二叉树中节点的值（int型），0表示空树:\n"); CreateBiTree(T);
CreateBiTree(T1);
printf("该二叉树的宽度是:%d\n",BiTreeWidth(T)); printf("该二叉树的深度是%d\n",GetBiTreeDepth(T)); if(Similar(T,T1))
printf("T和T1相似！！\n");
else
printf("T和T1不相似！！\n");
}