/*Implement program for Binary Search Tree and Display
1. Height of Tree
2. Leaf Node
*/
#include<stdio.h>
#include<stdlib.h>
struct btree
{
int data;
struct btree *lchild,*rchild;
};
struct queue
{
struct btree *q[max];
int front,rear;
};
typedef struct queue queue;
typedef struct btree NODE;
NODE *create(NODE *);
NODE *getnode();
NODE *del(queue *);
void add(queue *,NODE *);
void height(NODE *);
void leaf(NODE *);
void display(NODE*);
int main()
{
NODE *root;
int choice,n,i;
char ch;
root=NULL;
do
{
printf("\n\n\t\tMENU");
printf("\n\t1.Create BST");
printf("\n\t2.Display");
printf("\n\t3.Height");
printf("\n\t4.Print leaf nodes");
printf("\n\t0.Exit");
printf("\nEnter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nCreate a binary serach tree\n");
root=create(root);
break;
case 2:
printf("\nDisplay\n\n");
display(root);
break;
case 3:
printf("\nHeaight of tree\n\n");
height(root);
break;
case 4:
printf("\nThe leaf nodes are \n\n");
leaf(root);
break;
case 0:
exit(0);
break;
default:
printf("\nWrong choice");
break;
}
printf("\nDo you want to continue(y/n):");
scanf("%s",&ch);
}while(ch=='y'||ch=='Y');
return(0);
}
void add(queue *s,NODE *t)
{
s->rear=s->rear+1;
s->q[s->rear]=t;
}
NODE *del(queue *s)
{
NODE *temp;
s->front=s->front+1;
temp=s->q[s->front];
return(temp);
}
int empty(queue *s)
{
return(s->front==s->rear);
}
NODE *getnode()
{
NODE *temp;
temp=(NODE *)malloc(sizeof(NODE));
printf("\nEnter data: ");
scanf("%d",&temp->data);
temp->rchild=NULL;
temp->lchild=NULL;
return(temp);
}
NODE *create(NODE *root)
{
NODE *temp,*ptr;
char ch;
do
{
temp=getnode();
if(root==NULL)
root=temp;
else
{
ptr=root;
while(ptr!=NULL)
{
if(ptr->data>temp->data)
{
if(ptr->lchild!=NULL)
ptr=ptr->lchild;
else
{
ptr->lchild=temp;
break;
}
}
else
{
if(ptr->rchild!=NULL)
ptr=ptr->rchild;
else
{
ptr->rchild=temp;
break;
}
}
}
}
printf("\nAdd more(y/n): ");
scanf("%s",&ch);
}while(ch=='y'||ch=='Y');
return(root);
}
void display(NODE *h)
{
queue que;
NODE *temp;
que.front=NULL;
que.rear=NULL;
temp=h;
add(&que,temp);
add(&que,NULL);
while(!empty(&que)==1)
{
temp=del(&que);
if(temp==NULL)
{
if(!empty(&que)==1)
{
printf("\n");
add(&que,NULL);
}
}
else
{
printf("\t");
printf("%d",temp->data);
if(temp->lchild!=NULL)
add(&que,temp->lchild);
if(temp->rchild!=NULL)
add(&que,temp->rchild);
}
}
}
void height(NODE *h)
{
int count=0,total=0,level=0;
queue que;
NODE *temp;
que.front=NULL;
que.rear=NULL;
temp=h;
add(&que,temp);
add(&que,NULL);
while(!empty(&que)==1)
{
temp=del(&que);
if(temp==NULL)
{
if(!empty(&que)==1)
{
printf("\n");
level++;
add(&que,NULL);
}
}
else
{
total++;
printf("%d ",temp->data);
if(temp->lchild!=NULL)
add(&que,temp->lchild);
if(temp->rchild!=NULL)
add(&que,temp->rchild);
}
}
printf("\n\n---------------------------------");
printf("\n\nTotal Nodes=%d\n",total);
printf("\nHeight of tree=%d\n\n",level);
}
void leaf(NODE *h)
{
int k=0;
queue que;
NODE *temp;
que.front=que.rear=NULL;
temp=h;
add(&que,temp);
while(!empty(&que)==1)
{
temp=del(&que);
if(temp->lchild!=NULL)
add(&que,temp->lchild);
if(temp->rchild!=NULL)
add(&que,temp->rchild);
if(temp->lchild==NULL && temp->rchild==NULL)
{
k++;
printf(" %d ",temp->data);
}
}
printf("\n\nNumber of leaf nodes are=%d",k);
}
