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();
}
