#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct Node
{
int data;
int depth;
struct Node *llink,*rlink;
}Node,*Tree;
Status SearchBST(Tree T,int key,Tree f,Tree *p);
Status InsertBST(Tree *T,int e);
int Depth_Make(Tree T);
Status TreeBalance(Tree T);
int main()
{
Tree T;
T=(Tree)malloc(sizeof(Node));
T=NULL;
int e;
printf("What number you want to search--0 to quit:");
scanf("%d",&e);
while(e)
{
if(!InsertBST(&T,e))
printf("Done!");
else
printf("It`s been inserted for the first time.");
printf("\nWhat number you want to search--0 to quit:");
scanf("%d",&e);
}
int h;
h=0;
h=Depth_Make(T);
printf("树的高度为:%d.\n",h);
if(TreeBalance(T))
printf("\n是平衡树。\n");
else
printf("\n不是平衡树.\n");
return 0;
}
Status SearchBST(Tree T,int key,Tree f,Tree *p)
{
if(!T)
{
*p=f;
return FALSE;
}
else if(key==T->data)
{
*p=T;
return TRUE;
}
else if(key<T->data)
{
return SearchBST(T->llink,key,T,p);
}
else
return SearchBST(T->rlink,key,T,p);
}
Status InsertBST(Tree *T,int e)
{
Tree p;
p=(Tree)malloc(sizeof(Node));
if(!SearchBST(*T,e,NULL,&p))
{
Tree s;
s=(Tree)malloc(sizeof(Node));
s->data=e;
s->llink=s->rlink=NULL;
s->depth=1;
if(!p)
(*T)=s;
else if(e<p->data)
p->llink=s;
else
p->rlink=s;
return TRUE;
}
else
return FALSE;
}
int Depth_Make(Tree T)
{
if(T)
{
int left,right;
left=right=0;
if(T->llink)
left=Depth_Make(T->llink);
if(T->rlink)
right=Depth_Make(T->rlink);
T->depth+=(left>right?left:right);
return T->depth;
}
}
Status TreeBalance(Tree T)
{
if(T->llink ||T->rlink)
{
int left,right;
left=right=0;
if(T->llink)
left=T->llink->depth;
if(T->rlink)
right=T->rlink->depth;
if(left-right>1 || right-left>1)
return FALSE;
else if(TreeBalance(T->llink) && TreeBalance(T->rlink))
return TRUE;
else
return FALSE;
}
else
return TRUE;
}
