Group B Assignment 11 : BST Program for Dictionary

 Problem Statement: 


A Dictionary stores keywords and its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.





Program :

#include<iostream>
#include<string.h>
using namespace std;

struct word
{
    char key[15];
    char meaning[20];
};

struct node
{
    word data;
    node *left, *right;
};

 
class BST
{
    public: 
    node *root;
    
    BST()
    {
        root=NULL;
    }
    
    node *create_BST(); 
    node *insert(node *,word);
    void display(node *);
    
};

node *BST ::create_BST()
{
    int n,i;
    word x;
    cout<<"Enter Total Number Of Node :";
    cin>>n;
    
    for(i=0;i<n;i++)
    {
        cout<<"Enter data :";
        cin>>x.key;
        cout<<"Enter Meaning :";
        cin>>x.meaning;
        root=insert(root,x);
    }
    
    return root;
}

node *BST :: insert(node *T,word x)
{
    if(T==NULL)
    {
        T= new node ;
        T->data=x;
        T->left=NULL;
        T->right=NULL;
        
        return T;
    }
    else
    {
        if(strcmp(x.key,T->data.key)>0)
        {
            T->right=insert(T->right,x);
            return T;
        }
        
        if(strcmp(x.key,T->data.key)<0)
        {
            T->left=insert(T->left,x);
            return T;
        }
        
    }
}

void BST ::display(node * T)
{
    
    if(T!=NULL)
    {
        display(T->left);
        cout<<"("<<T->data.key<<" - "<<T->data.meaning<<")";
        display(T->right);
    }
}


int main()
{
    BST b1;
    int ch;
    word x1;
    char ans;
    do
    {
    cout<<" \n MAIN MENU \n 1. Create \n 2. Insert \n 3.Display ";
    cout<<"\n\n Enter your choice : ";
    cin>>ch;
    switch(ch)
    {
        case 1: 
                b1.root=b1.create_BST(); 
                break;
        case 2:
                cout<<"\nData : ";
                cin>>x1.key; 
                cout<<"\nMeaning : ";
                cin>>x1.meaning;
                b1.root=b1.insert(b1.root,x1); 
                break;
        case 3:
                cout<<"\nTHE BST TREE in INORDER : "; 
                b1.display(b1.root); 
                break;
        
    }
    cout<<"\n\n Do You Want To Go Main menu? ";
    cin>>ans;
    }while(ans=='y');
    
    return 0;
}

/*_______________::OUTPUT::____________________

 
 MAIN MENU 
 1. Create 
 2. Insert 
 3.Display 

 Enter your choice : 1
Enter Total Number Of Node :3
Enter data :Phone
Enter Meaning :Electronics
Enter data :Car
Enter Meaning :Vehicle
Enter data :Movies
Enter Meaning :Entertainment


 Do You Want To Go Main menu? y
 
 MAIN MENU 
 1. Create 
 2. Insert 
 3.Display 

 Enter your choice : 3

THE BST TREE in INORDER : (Car - Vehicle)(Movies - Entertainment)(Phone - Electronics)

 Do You Want To Go Main menu? y
 
 MAIN MENU 
 1. Create 
 2. Insert 
 3.Display 

 Enter your choice : 2

Data : School

Meaning : Education


 Do You Want To Go Main menu? y
 
 MAIN MENU 
 1. Create 
 2. Insert 
 3.Display 

 Enter your choice : 3

THE BST TREE in INORDER : (Car - Vehicle)(Movies - Entertainment)(Phone - Electronics)(School - Education)

 Do You Want To Go Main menu? n


...Program finished with exit code 0
Press ENTER to exit console.
*/

Comments