Program - Binary tree creation

Algorithm and Program - Binary tree creation

cretate_tree(list.lower,upper)

Where

List-> represents list of elements that forms a binary tree.

Lower-> represents lower limit of the list that is lower index value of the list.

Upper-> represents upper limit of the list that is upper index value.

Step -1 : [Find middle of the list]

(i)                                                                           mid=(lower+upper)/2  [integer division]

(ii)                                                                         info[node]=list[mid]

Step-2  : if lower >=upper

(i)                                                                           left_child[node]=NULL

(ii)                                                                         right_child[node]=NULL

(iii)                                                                       return(node)

Step-3  : if lower<=mid-1

                 left_child=call create_tree(list,lower,mid-1)

             else

                left_child[node]=NULL

Step-4 : if upper>=mid+1

                right_child=call create_tree(list,mid+1,upper)

             else

                right_child[node]=NULL

Step- 5 : return(node)

Program

// creating binary tree

#include<stdio.h>

#include<conio.h>

struct tree

{

        char  info;

        struct tree *leftchild;

        struct tree *rightchild;

};

struct tree * create_tree(char*,int,int);

void output(struct tree*,int);

struct tree * create_tree(char *list,int low,int up)

{

        struct tree *node;

        int mid=(low+up)/2;

        node=(struct tree *)malloc(sizeof(struct tree));

        node->info=list[mid];

        if(low>=up)

        {

                node->leftchild=NULL;

                node->rightchild=NULL;

                return(node);

        }

        if(low<=mid-1)

                node->leftchild=create_tree(list,low,mid-1);

        else

                node->leftchild=NULL;

        if(mid+1<=up)

                node->rightchild=create_tree(list,mid+1,up);

        else

                node->rightchild=NULL;

        return(node);

}

void output(struct tree *t,int level)

{

        int i;

        if(t)

        {

                output(t->rightchild,level+1);

                printf("\n");

                for(i=0;i<level;i++)

                        printf(" ");

                printf("%c",t->info);

                output(t->leftchild,level+1);

        }

}

void main()

{

        char list[100];

        int num=0;

        char info,ch;

        struct tree *t=(struct tree *)malloc(sizeof(struct tree));

        clrscr();

        t=NULL;

        printf("Input choice 'b' to break:");

        ch=getchar();

        fflush(stdin);

        while(ch!='b')

        {

                printf("Input information of the node:");

                scanf("%c",&info);

                list[num++]=info;

                fflush(stdin);

                printf("Input choice 'b' to break:");

                ch=getchar();

                fflush(stdin);

        }

        printf("\nNumber of elements in the list is %d",num);

        num--;

        t=create_tree(list,0,num);

        output(t,1);

        getch();

}

Posted By : Ruchita Pandya