• Home
  • MY TRYOUTS
  • tips
  • tech news
  • PROGRAMS
  • Downloads
  • About
  • Contact

Lab program-10

Design, Develop and Implement a menu driven Program in C for the
following operations on Binary
Search Tree (BST) of Integers
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate
message
d. Delete an element (ELEM) from BST
e. Exit

#include <stdio.h>
#include <stdlib.h>
struct BST
{
    int data;
    struct BST *left;
    struct BST *right;
};
typedef struct BST NODE;

NODE *node;


NODE* createtree(NODE  *node, int data)
{
    if (node == NULL)
    {
        NODE *temp;
        temp= (NODE*)malloc(sizeof(NODE));
        temp->data = data;
        temp->left = temp->right = NULL;
        return temp;
    }
    if (data < (node->data))
    {
        node->left = createtree(node->left, data);
    }
    else if (data > node->data)
    {
        node -> right = createtree(node->right, data);
    }
    return node;
}


NODE* search(NODE *node, int data)
{
    if(node == NULL)
        printf("\nElement not found");
    else if(data < node->data)
    {
        node->left=search(node->left, data);
    }
    else if(data > node->data)
    {
        node->right=search(node->right, data);
    }
    else
        printf("\nElement found is: %d", node->data);
        return node;
}
void inorder(NODE *node)
{
    if(node != NULL)
    {
        inorder(node->left);
        printf("%d\t", node->data);
        inorder(node->right);
    }
}

void preorder(NODE *node)
{
    if(node != NULL)
    {
        printf("%d\t", node->data);
        preorder(node->left);
preorder(node->right);
    }
}


void postorder(NODE *node)
{
    if(node != NULL)
    {
        postorder(node->left);
        postorder(node->right);
        printf("%d\t", node->data);
    }
}

NODE* findMin(NODE *node)
{
    if(node==NULL)
    {
        return NULL;
    }
    if(node->left)
        return findMin(node->left);
    else
        return node;
}

NODE* del(NODE *node, int data)
{
    NODE *temp;
    if(node == NULL)
    {
        printf("\nElement not found");
    }
    else if(data < node->data)
{
        node->left = del(node->left, data);
    }
        else if(data > node->data)
    {
        node->right = del(node->right, data);
    }
    else
    {
/* Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree */
    
if(node->right && node->left)
{   /* Here we will replace with minimum element in the right sub tree */
    temp = findMin(node->right);
node -> data = temp->data;
* As we replaced it with some other node, we have to delete that node */
    node -> right = del(node->right,temp->data);
}
else
    {
/* If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child */
    temp = node;
    if(node->left == NULL)
    node = node->right;
    else if(node->right == NULL)
    node = node->left;
    free(temp);     /* temp is longer required */
    }
}
return node;
}

void main()
{
    int data, ch, i, n;
    NODE *root=NULL;
    while (1)
    {
        printf("\n1.Insertion in Binary Search Tree");
        printf("\n2.Search Element in Binary Search Tree");
        printf("\n3.Delete Element in Binary Search Tree");
        printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);

switch (ch)
{
    case 1:     printf("\nEnter N value: " );
        scanf("%d", &n);
        printf("\nEnter the values to create BST                     like(6,9,5,2,8,15,24,14,7,8,5,2)\n");
    for(i=0; i<n; i++)
    {
        scanf("%d", &data);
        root=createtree(root, data);
    }
        break;
    case 2:     printf("\nEnter the element to search: ");
        scanf("%d", &data);
        root=search(root, data);
        break;
    case 3:     printf("\nEnter the element to delete: ");
        scanf("%d", &data);
        root=del(root, data);
        break;


    case 4:     printf("\nInorder Traversal: \n");
        inorder(root);
        break;
    case 5:     printf("\nPreorder Traversal: \n");
        preorder(root);
        break;
    case 6:     printf("\nPostorder Traversal: \n");
        postorder(root);
        break;
    case 7:     exit(0);
    default:    printf("\nWrong option");
    break;
    }
        }
}





Powered by Create your own unique website with customizable templates.
  • Home
  • MY TRYOUTS
  • tips
  • tech news
  • PROGRAMS
  • Downloads
  • About
  • Contact