A tree is called binary tree if each node contains zero,one or two sub-trees.In this program,tree is first created.Then the function check_complete,checks every node recursively.Each node is parsed till it reaches NULL.If both the left child and right child are NULL then it is called binary tree.
#include < stdio.h >
#include < conio.h >
#include < alloc.h >
#define new_node (struct node*)malloc(sizeof (struct node))
struct node
{
int data;
struct node *lc;
struct node *rc;
};
struct node *create_bin_pre_rec();
void main()
{
struct node *r;
int reply;
clrscr();
printf("\nCreate a binary tree \n");
r = create_bin_pre_rec();
printf("\n The binary tree is \n");
print_bin_pre_rec(r);
reply = check_complete(r);
if( reply == 1 )
printf("\n Complete tree ");
else
printf("\n Not complete tree ");
}
struct node *create_bin_pre_rec()
{
struct node *c;
int data;
printf("\nData : ");
scanf("%d",&data);
if( data == -1)
return(NULL);
else
{
c = new_node;
c->data = data;
c->lc = create_bin_pre_rec();
c->rc = create_bin_pre_rec();
return(c);
}
} // create
int print_bin_pre_rec(struct node *t)
{
if( t != NULL)
{
printf("%4d",t->data);
print_bin_pre_rec(t->lc);
print_bin_pre_rec(t->rc);
}//if
return;
} // print
int check_complete(struct node *t)
{
int reply;
if( t == NULL)
return(1);
else
if( t->lc == NULL && t->rc == NULL)
return(1);
else
if( t->lc != NULL && t->rc == NULL)
return(0);
else
if( t->lc == NULL && t->rc != NULL)
return(0);
else
{
reply = check_complete(t->lc);
if ( reply == 1 )
reply = check_complete(t->rc);
return(reply);
} // else
} // check complete
No comments:
Post a Comment