A) Write menu driven program using ‘C’ for Binary Search Tree. The menu includes
- Create a Binary Search Tree
- Insert element in a Binary Search Tree
- Display
Answers
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
Thus, a binary search tree (BST) divides all its sub-trees into two segments; left sub-tree and right sub-tree and can be defined as
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
Primary operations of a binary search tree are following.
Search − search an element in a tree.
Insert − insert an element in a tree.
Preorder Traversal − traverse a tree in a preorder manner.
Inorder Traversal − traverse a tree in an inorder manner.
Postorder Traversal − traverse a tree in a postorder manner
Define a node having some data, references to its left and right child nodes.
struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
};
ALGORITHM:
Step 1: Start.
Step 2: Create a Binary Search Tree for N elements.
Step 3: Traverse the tree in inorder.
Step 4: Traverse the tree in preorder
Step 6: Traverse the tree in postorder.
Step 7: Search the given key element in the BST.
Step 8: Delete an element from BST.
Step 9: Stop
Answer:
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *lchild;
int info;
struct node *rchild;
};
struct node *insert(struct node *ptr, int ikey);
struct node *Min(struct node *ptr);
struct node *Max(struct node *ptr);
void display(struct node *ptr,int level);
int main( )
{
struct node *root=NULL,*ptr;
int choice,k;
while(1)
{
printf("\n");
printf("1.Insert\n");
printf("2.Display\n");
printf("3.Find minimum and maximum\n");
printf("4.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the key to be inserted : ");
scanf("%d",&k);
root = insert(root, k);
break;
case 2:
printf("\n");
display(root,0);
printf("\n");
break;
case 3:
ptr = Min(root);
if(ptr!=NULL)
printf("\nMinimum key is %d\n", ptr->info );
ptr = Max(root);
if(ptr!=NULL)
printf("\nMaximum key is %d\n", ptr->info );
break;
case 4:
exit(1);
default:
printf("\nWrong choice\n");
}/*End of switch */
}/*End of while */
return 0;
}/*End of main( )*/
struct node *insert(struct node *ptr, int ikey )
{
if(ptr==NULL)
{
ptr = (struct node *) malloc(sizeof(struct node));
ptr->info = ikey;
ptr->lchild = NULL;
ptr->rchild = NULL;
}
else if(ikey < ptr->info) /*Insertion in left subtree*/
ptr->lchild = insert(ptr->lchild, ikey);
else if(ikey > ptr->info) /*Insertion in right subtree */
ptr->rchild = insert(ptr->rchild, ikey);
else
printf("\nDuplicate key\n");
return ptr;
}/*End of insert( )*/
struct node *Min(struct node *ptr)
{
if(ptr==NULL)
return NULL;
else if(ptr->lchild==NULL)
return ptr;
else
return Min(ptr->lchild);
}/*End of min()*/
DELETE(T, z)
if z.left == NULL
TRANSPLANT(T, z, z.right)
elseif z.right == NULL
TRANSPLANT(T, z, z.left)
else
y = MINIMUM(z.right) //minimum element in right subtree
if y.parent != z //z is not direct child
TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.parent = y
TRANSPLANT(T, z, y)
y.left = z.left
y.left.parent = y
SEARCH(x, T)
if(T.root != null)
if(T.root.data == x)
return r
else if(T.root.data > x)
return SEARCH(x, T.root.left)
else
return SEARCH(x, T.root.right)
struct node *Max(struct node *ptr)
{
if(ptr==NULL)
return NULL;
else if(ptr->rchild==NULL)
return ptr;
else
return Max(ptr->rchild);
}/*End of max()*/
void display(struct node *ptr,int level)
{
int i;
if(ptr == NULL )/*Base Case*/
return;
else
{
display(ptr->rchild, level+1);
printf("\n");
for (i=0; i<level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
}
Explanation: