Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Vaues:
(1). Create a BST with a single node as its Root Node;
(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node);
(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist;
(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree";
(5). Check whether it is a complete binary tree or not;
(6). Find Height of the Binary Search Tree;
(7). Find Difference b/w left and right subtree's heights;
".C" file is available in downloadable format at :
(Open the link and click on the download arrow on the top right to download the file.)
Given below is the code for "C program for Advanced BST, with calculation of height and checking whether it is complete BST or not" :
-----------------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#define size 30
typedef struct tree
{
int info;
struct tree* left;
struct tree* right;
}node;
node* create (node*);
void insert (node*, node*);
node* search (node*, int);
node* del (node*, int);
node* display(node*);
int height (node*);
int diffheights ();
node* create (node* root)
{
int no,ele,i=0;
node* n=NULL;
node *key;
printf("\nNumber of entries:\t");
scanf("%d", &no);
while (i<no)
{
printf("\n----------------------------------INSERT------------------------------------");
printf("\nEnter data:\t");
scanf("%d", &ele);
if (ele> 0)
{
key= search(root, ele);
if (key==NULL)
{
n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL;
n->right=NULL;
if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
i++;
}
else
printf("The node data: %d already exists in the tree.",ele);
}
else printf("\nOnly Positive integers are allowed");
}
return root;
}
void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;
while(q!=NULL)
{
p=q;
if(nw->info>q->info)
q=q->right;
else
q=q->left;
}
if (p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
}
node* search(node* root, int ele)
{
node *q;
q=root;
while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
return q;
}
node* del(node* root, int ele)
{
node* p , *q;
p=root;
while((p!=NULL)&&(p->info!=ele))
{
q=p;
if(p->info > ele)
p = p->left;
else
p=p->right;
}
if((p->right==NULL)&&(p->left==NULL))
{
if (q->info>ele)
q->left=NULL;
else
q->right=NULL;
}
if((p->left==NULL)&&(p->right!=NULL))
{
if (q->info>ele)
q->left=p->right;
else
q->right=p->right;
}
if((p->right==NULL)&&(p->left!=NULL))
{
if (q->info>ele)
q->left=p->left;
else
q->right=p->left;
}
if((p->left!=NULL)&&(p->right!=NULL))
{
node *s, *r = p->left;
while(r->right!=NULL)
{
s=r;
r=r->right;
}
p->info = r->info;
s->right = r-> left;
}
return root;
}
node* display (node* q)
{
if(q!=NULL)
{
q->left=display(q->left);
printf(" | %d | ", q->info);
q->right=display(q->right);
}
return q;
}
int height (node* p)
{
if(p==NULL)
return 0;
else
{
int leftheight = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
return leftheight+1;
}
else
{
return rightheight+1;
}
}
}
int diffheights (node* p)
{
int diff;
int leftheight = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
diff = (-1)*(leftheight-rightheight);
}
else
{
diff = (rightheight-leftheight);
}
return diff;
}
void main()
{
node *root=NULL, *q;
int choice, ele, h, dif;
while(1)
{
printf("\n\n\n1. Create\n2. Search\n3. Delete a node.\n4. Display (Inorder)\n5. Is it a Complete Binary Tree?\n6. Height\n7. Difference b/w left and right heights.\n8. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);
switch(choice)
{
case 1: root=create(root); printf("\n\nCREATED"); break;
case 2: printf("Enter value to be searched:\t"); scanf("%d", &ele); q= search(root, ele);
if(q==NULL)
{
printf("\n%d doesn't exist in the tree.", ele);
}
else
{
printf("\n%d found",q->info);
} break;
case 3: printf("Enter value to be deleted:\t");
scanf("%d", &ele);
if(search(root, ele)==NULL)
printf("\nERROR: The value doesnot exist");
else
root = del(root, ele); printf("\nDeleted !"); break;
case 4: display (root); break;
case 5: if(root==NULL)
printf ("\nThe tree is Empty");
else
{
if(diffheights(root))
printf("\n Nope !");
else printf("\n Yes, it is.");
}
break;
case 6: h = height(root); printf("\nHeight = %d\n", h); break;
case 7: dif = diffheights(root);
if(dif==0)
printf("\nIt's a complete binary tree, difference is zero!");
if (dif<0)
printf("Height of Left subtree is greater than Right subtree by %d", (-1)*(dif));
if(dif>0)
printf("Height of Right subtree is greater than Left subtree by %d", dif);
break;
case 8: if(root==NULL)
printf("\nExiting with empty tree\n\n");
else
{
root->right=NULL; root->left=NULL;
free(root);
printf("\nTree Cleared !\n\n");
} exit(0);
default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}
}
}
Thanks a ton, man !!
ReplyDeleteGreat that I found this code :)