DS (II) Assignment 1: Set A- a)

a) Implement a Binary search tree (BST) library (btree.h) with operations – create, search, insert, inorder, preorder and postorder. Write a menu driven program that performs the above operations.

Solution:

#include<stdio.h>
#include"btree.h"
void main()
{
    struct node *root, *temp;
    int ch,count, val;
    root=NULL;
    while(1)
    {
        printf("\nBST OPERATIONS ---");
        printf("\n1 - Create BST\n");
        printf("2 - Insert an element into tree\n");
        printf("3 - Search an element in the tree\n");
        printf("4 - Inorder Traversal\n");
        printf("5 - Preorder Traversal\n");
        printf("6 - Postorder Traversal\n");
        printf("7 - Exit\n");
        printf("\nEnter your choice : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
                while(1)
                {
                    printf("\nEnter The data");
                    scanf("%d", &val);
                    if(val==0)
                        break;
                    else
                    {
                        root=create(root, val);
                    }
                }
                break;
            case 2:    
                printf("\nEnter The data to Insert\n");
                scanf("%d", &val);
                root=insert(root, val);
                break;
            case 3:    
                printf("\nEnter The data to Search\n");
                scanf("%d", &val);
                temp=searchBST(root, val);
                if(temp==NULL)
                    printf("\n%d is Not Found", val);
                else
                    printf("\n%d is Found", val);
                break;
            case 4:    
                inorder(root);
                break;
            case 5:    
                preorder(root);
                break;
            case 6:    
                postorder(root);
                break;
            case 7:    
                  exit(0);
            default :     
               printf("Wrong choice, Please enter correct choice  ");
                break;    
        }
    }
}

Library Function ( .h file )
NOTE: save file name as ' btree.h'. 

 

#include<stdio.h>
#include<malloc.h>
struct node
{
    int data;
    struct node *left, *right;
};
struct node *create(struct node *root, int x)
{
    if(root==NULL)
    {
        root=(struct node*)malloc(sizeof(struct node));
        root->data=x;
        root->left=root->right=NULL;
        return(root);
    }
    else if(x<root->data)
    {
        root->left=create(root->left, x);           
    }
    else
        root->right=create(root->right, x);
    return(root);
}
struct node *insert(struct node *root, int key) {
  // Return a new node if the tree is empty
  if (root == NULL)
  {
          root=(struct node*)malloc(sizeof(struct node));
        root->data=key;
        root->left=root->right=NULL;
        return(root);
  }
  // Traverse to the right place and insert the node
  if (key < root->data)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);
  return root;
}
void preorder(struct node *root)
{
    if(root!=NULL)
    {
        printf(" %d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node *root)
{
    if(root!=NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf(" %d ", root->data);
    }
}
void inorder(struct node *root)
{
    if(root!=NULL)
    {
        inorder(root->left);
        printf(" %d ", root->data);
        inorder(root->right);
    }
}
struct node *searchBST(struct node *root, int data)
{
    if(root==NULL)
    {
        return(NULL);
    }
    if(root->data==data)
    {
        return(root);
    }
    else if(data<root->data)
        return(searchBST(root->left,data));
    else
        return(searchBST(root->right,data));
}