/* Program for binary search tree*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
//definition of tree structure
struct node
{ int info;
struct node *left;
struct node *right;
};
typedef struct node node; //type definition
//function declaration
void insert(node **,int);
void delete_node(node *,int);
void inorder(node *);
void preorder(node *);
void postorder(node *);
void root_node(node *);
void parent(node **);
void has_child(node**);
void siblings(node **, node **);
void subtrees(node **);
int height(node *);
int depth(node *p);
int internal_node(node *);
int external_node(node *);
void search(node**,int,node**,node**,int *);
//global variables
int num;
node *ptr=NULL;
//main program
void main()
{
char che,ch;
int op;
clrscr();
do
{
printf("\n\tMAIN MENU");
printf("\n 1.Create a BST");
printf("\n 2.Insert a Node in a BST");
printf("\n 3.To Delete a Node from a BST");
printf("\n 4.Inorder Traversal");
printf("\n 5.Preorder Traversal");
printf("\n 6.Postorder Traversal");
printf("\n 7.Find Root nodes");
printf("\n 8.Find parent of a nodes");
printf("\n 9.Find child of a nodes");
printf("\n 10.Find if nodes are siblings or not.");
printf("\n 11.Find no. of subtrees of a nodes");
printf("\n 12.Find Height of BST");
printf("\n 13.Find depth of node inBST");
printf("\n 14.Find Number of Internal nodes");
printf("\n 15.Find Number of External nodes");
printf("\n 0.To Exit the Program");
printf("\n Enter Your Choice: ");
scanf("%d",&op);
switch(op)
{
case 1:
do {//create a node
printf("\nEnter the element in BST: ");
scanf("%d",&num);
insert(&ptr,num);
printf("\ndo you want to enter some more elements:(y/n) ");
che=getche();
}while(che=='y');
break;
case 2:
//insertion
printf("\nEnter the value: ");
scanf("%d",&num);
insert(&ptr,num);
case 3:
//deletion
printf("\nEnter the element to be deleted: ");
scanf("%d",&num);
delete_node(ptr,num);
//delet(&ptr);
break;
case 4:
//inorder traversal
inorder(ptr);
break;
case 5:
//preorder traversal
preorder(ptr);
break;
case 6:
//postorder traversal
postorder(ptr);
break;
case 7:
//root node
root_node(ptr);
break;
case 8:
//patent of a node
parent(&ptr);
break;
case 9:
//child node
has_child(&ptr);
break;
case 10:
//siblings
siblings(&ptr,&ptr);
break;
case 11:
//find no. of subtrees
subtrees(&ptr);
break;
case 12:
//height of BST
printf("\nThe height of tree is: %d", height(ptr));
break;
case 13:
//depth of a node
printf("\nThe depth of tree is: %d", depth(ptr));
break;
case 14:
//Internal nodes
printf("\nTotal number of internal nodes are: %d",(internal_node(ptr)-1));
break;
case 15:
//External nodes
printf("\nTotal number of external nodes are: %d",external_node(ptr));
break;
default :
printf("\nWrong Choice..");
}
printf("\nDo you want to Continue:(y/n): ");
ch=getche();
}while(ch=='y');
}//end main
//function definition
void insert(node **p,int num)
{ //function to insert an element in a BST
if(*p==NULL)//tree is empty
{
*p=(node *)malloc(sizeof(node));
(*p)->left=(*p)->right=NULL;
(*p)->info=num; //root node
}
else
{
if(num < (*p)->info)
insert(&((*p)->left),num);//insert in left subtree
else
insert(&((*p)->right),num);//insert in right subtree
}
}
void delete_node(node *p,int num)
{//function to delete an element in a BST
node* curr;
node* parent;
int found=0;
if(p==NULL)
{
printf("\nThe tree is empty");
return;
}
curr = p;
while(curr!= NULL)
{
if(curr->info == num)
{
found =1;
break;
}
else
{
parent = curr;
if(num>curr->info)
curr = curr->right;//right subtree
else
curr = curr->left;//left subtree
}
}
if(!found)//not found
{
printf("\nThe element do not exists in a BST ");
return;
}
//1.node to be deleted is a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
parent->left = NULL;
else
parent->right = NULL;
free(curr);
return;
}
// 2.Node to be deleted has single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{ //only right child is present
if(parent->left == curr)
{
parent->left = curr->right;
free(curr);
}
else
{
parent->right = curr->right;
free(curr);
}
}
else // only left child present
{
if(parent->left == curr)
{
parent->left = curr->left;
free(curr);
}
else
{
parent->right = curr->left;
free(curr);
}
}
return;
}
//3.Node to be deleted has both left and right child
if (curr->left != NULL && curr->right != NULL)
{ //find inorder successor
node* chk;
chk = curr->right;
if((chk->left == NULL) && (chk->right == NULL))
{
curr = chk;
free(chk);
curr->right = NULL;
}
else // right child has children
{
//the leftmost node has smallest element
if((curr->right)->left != NULL)
{
node* lcurr;
node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->info = lcurr->info;
free(lcurr);
lcurrp->left = NULL;
}
else
{
node* tmp;
tmp = curr->right;
curr->info = tmp->info;
curr->right = tmp->right;
free(tmp);
}
}
return;
}
}
void inorder(node *p)
{//function for inorder traversal (LNR)
if(p!=NULL)
{
inorder(p->left);
printf("\n %d",p->info);
inorder(p->right);
}
}
void preorder(node *p)
{//function for preorder traversal (NLR)
if(p!=NULL)
{
printf("\n %d ",p->info);
preorder(p->left);
preorder(p->right);
}
}
void postorder(node *p)
{ //function for inorder traversal (LRN)
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf("\n %d ",p->info);
}
}
void search(node **root,int num,node **par,node **temp,int *found)
{//function to search an element in BST
node *p;
p=*root;
*found=1;
*par=NULL;
while(p!=NULL)
{
if(p->info==num)
{
*found=0;
*temp=p;
return;
}
*par=p;
if(p->info>num)
p=p->left;
else
p=p->right;
}
}
void has_child(node **p)
{
//function to find child nodes of a node
node *parent,*temp;
int found=0,a;
printf("\nEnter the element whose child you want to find: ");
scanf("%d",&num);
if(*p==NULL)
{
printf("\nThe Tree is Empty.");
return;
}
parent=temp=NULL;
search(p,num,&parent,&temp,&found);
if(temp->left!=NULL)
printf("\nLeft Child is %d",temp->left->info);
if(temp->right!=NULL)
printf("\nRight child is %d",temp->right->info);
if((temp->left==NULL)&&(temp->right==NULL))
printf("The node is a leaf node..");
}