binary tree

Program 13:
Write a C program:
a] To construct a binary search tree of integers.
b] To traverse the tree using all methods i.e., inorder , preorder and postorder.
c] To display the elements in the tree.


#include"stdio.h" /*PREPROCESSOR DIRECTIVES*/
#include"conio.h"
#include"alloc.h"
struct node /*STRUCTURE TEMPLATE DECLARATION*/
{
int info;
struct node *llink;
struct node *rlink;
};
typedef struct node *Node;

/*FUNCTION PROTOTYPE DECLARATION*/
Node insert(int,Node);
void preorder(Node);
void inorder(Node);
void postorder(Node);
void main()
{
Node root=NULL; /*VARIBLE DECLARATION*/
int choice,item,ch;
clrscr();
do{ /*DO-WHILE LOOP*/
printf("1:Insert item\n");
printf("2:Preorder\n");
printf("3:Inorder\n");
printf("4:Postorder\n");
printf("5:Exit\n");
printf("Enter your choice\n");
scanf("%d",&choice);
switch(choice) /*SWITCH STATEMENT*/
{
case 1:printf("Enter the item to be inserted\n");
scanf("%d",&item);
root=insert(item,root);
break;
case 2:if(root==NULL)
printf("Tree is Empty\n");
else
{
printf("Preorder Traversal\n");
preorder(root);
printf("\n");
}
break;
case 3:if(root==NULL)
printf("Tree is Empty\n");
else
{
printf("Inorder Traversal\n");
inorder(root);
printf("\n");
}
break;
case 4:if(root==NULL)
printf("Tree is Empty\n");
else
{
printf("Postorder Traversal\n");
postorder(root);
printf("\n");
}
break;
case 5:exit(1);
break;
default:printf("Invalid Choice\n");
} /*END OF SWITCH STATEMENT*/
printf("Do you want to continue(y/n)?:");
ch=getche();
}
while(ch!='n'); /*END OF DO-WHILE LOOP*/
getch();
}

/*FUNCTION TO ALLOCATE MEMORY DYNAMICALLY*/
Node getnode()
{
Node temp;
temp=(Node)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("Out of Memory\n");
exit(1);
}
return temp;
}

/*FUNCTION TO INSERT ELEMENTS INTO THE TREE*/
Node insert(int item,Node root)
{
Node temp,p,q;
temp=getnode();
temp->info=item;
temp->llink=NULL;
temp->rlink=NULL;
if(root==NULL)
return temp;
p=q=root;
while(item!=p->info && q!=NULL)
{
p=q;
if(item< p->info)
q=p->llink;
else
{
q=p->rlink;
}
}
if(item==p->info)
printf("%d is Duplicate\n",item);
else
{
if(item< p->info)
p->llink=temp;
else
p->rlink=temp;
}
return root;
}

/*FUNCTION TO TRAVERSE THE TREE USING PREORDER*/
void preorder(Node root)
{
if(root!=NULL)
{
printf("%d\t",root->info);
preorder(root->llink);
preorder(root->rlink);
}
}

/*FUNCTION TO TRAVERSE THE TREE USING INORDER*/
void inorder(Node root)
{
if(root!=NULL)
{
inorder(root->llink);
printf("%d\t",root->info);
inorder(root->rlink);
}
}

/*FUNCTION TO TRAVERSE THE TREE USING POSTORDER*/
void postorder(Node root)
{
if(root!=NULL)
{
postorder(root->llink);
postorder(root->rlink);
printf("%d\t",root->info);
}
}