Wednesday, April 17, 2013

Check binary tree

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