1, C++ (gcc) - rextester

1

/*
 
//------------------------------------------------------------------------//
 
Name: CHINATN PATEL
 
Roll number: PG-33
 
Assignment: BST(insert, delete, copy, mirror)
 
//------------------------------------------------------------------------//*/
 
 
//----------------------------header files
 
#include<iostream>
 
#include<string.h>
 
#include<cstring>
 
 
using namespace std;
 
 
//----------------------------treenode class
 
class treenode
 
{    
 
    char keyword[50];
 
    char meaning[100];
 
    
 
    treenode *left;
 
    treenode *right;
 
    
 
    friend class tree;
 
};
 
 
//----------------------------dictionary tree class
 
class tree
 
{
 
        treenode *root; 
 
    public:
 
        tree()
 
        {
 
            root = NULL;
 
        }
 
        
 
        //----------------------------functions 
 
        void create();
 
                
 
        void delete_nr();
 
        
 
        void copy_r(tree *);
 
        treenode* copy_r(treenode *);
 
        
 
        void mirror_r();
 
        void mirror_r(treenode *);
 
        void mirror_nr();
 
        
 
        void breadthfd_nr();
 
        
 
        void inorder_r();
 
        void inorder_r(treenode*);
 
};
 
 
//----------------------------non recursive function
 
void tree::create()
 
{
 
    char ch;
 
    do
 
    {
 
        //----------------------------adding root to tree
 
        if( root == NULL)
 
        {
 
            root = new treenode;
 
 
            cout<<"\nenter data: ";
 
        
 
            cout<<"\n\tkeyword: ";
 
            cin>>root->keyword;
 
    
 
            cout<<"\n\tmeaning: ";
 
            cin>>root->meaning;
 
 
            root->left = NULL;
 
            root->right = NULL;
 
        }
 
        
 
        //----------------------------adding nodes to tree
 
        else
 
        {
 
            int flag = 0;
 
 
            treenode *temp = new treenode;
 
            temp = root;
 
 
            treenode *curr = new treenode;
 
 
            cout<<"\nenter data: ";
 
 
            cout<<"\n\tkeyword: ";
 
            cin>>curr->keyword;
 
 
            cout<<"\n\tmeaning: ";
 
            cin>>curr->meaning;
 
 
            curr->left  = NULL;
 
            curr->right = NULL;
 
 
            while(flag == 0)
 
            {                
 
                if( ( strcmp(curr->keyword, temp->keyword) ) < 0 )            
 
                {
 
                    if(temp->left == NULL)
 
                    {
 
                        temp->left = curr;
 
                        flag = 1;
 
                    }
 
                    else
 
                        temp = temp->left;
 
                }
 
 
                else if( ( strcmp(curr->keyword, temp->keyword) ) > 0 )
 
                {
 
                    if(temp->right == NULL)
 
                    {
 
                        temp->right = curr;
 
                        flag = 1;
 
                    }
 
                    else
 
                        temp = temp->right;
 
                }
 
 
                else
 
                {
 
                    temp = curr;
 
                }
 
            }
 
        }
 
        cout<<"do you wanna continue adding node PRESS 'Y' ";
 
        cin>>ch;
 
    }while( (ch == 'Y') || (ch == 'y') );    
 
}
 
 
//----------------------------delete
 
void tree::delete_nr()
 
{
 
    treenode *temp = new treenode;
 
    temp = root;
 
    
 
    //----------------------------the node to be deleted
 
    treenode *curr = new treenode;
 
    
 
    //----------------------------parent node
 
    treenode *parent = new treenode;
 
    
 
    //----------------------------successor node
 
    treenode *s = new treenode;
 
    
 
    //----------------------------ask user for keyword to be deleted
 
    char key[50];
 
    cout<<"Enter the keyword to be delete : ";
 
    cin>>key;
 
    
 
    //----------------------------search for the key in binary search tree
 
    int found = 0;
 
    while(temp != NULL)    
 
    {
 
        //----------------------------if match
 
        if( ( strcmp(key, temp->keyword) ) == 0)  
 
        {
 
            curr = temp;
 
            found = 1;   
 
            break;
 
        }
 
        
 
        //----------------------------if key is smaller
 
        else if( ( strcmp(key, temp->keyword) ) < 0 )
 
        {
 
            parent = temp;
 
            temp = temp->left;
 
        }
 
        
 
        //----------------------------if key is greater
 
        else if( ( strcmp(key, temp->keyword) ) > 0 )
 
        {
 
            parent = temp;
 
            temp = temp->right;
 
        }
 
        
 
    }
 
    
 
    //----------------------------if node found deleting it
 
    if(found = 1)
 
    {
 
        //----------------------------deletion of root node
 
        if(curr == root)  
 
        {
 
            if(curr->right == NULL)
 
                root = root->left;
 
 
            else if(curr->left == NULL)
 
                root = root->right;
 
 
            else if( (curr->right != NULL) && (curr->left != NULL) )
 
            {
 
                temp = curr->left;
 
 
                root = curr->right;
 
 
                s = curr->right;
 
 
                while(s->left != NULL)
 
                {
 
                    s = s->left;
 
                }
 
            
 
                s->left = temp;
 
            }
 
        }
 
    
 
        //----------------------------deletion of a non-root node 
 
        else if(curr != root) 
 
        {
 
            //----------------------------deletion of a leaf node
 
            if( (curr->left == NULL) && (curr->right == NULL) ) 
 
            {
 
 
                if(parent->left == curr)
 
                    parent->left = NULL;
 
                else
 
                    parent->right = NULL;
 
 
            }
 
        
 
            //----------------------------deletion of a node having right child only
 
            else if(curr->left == NULL) 
 
            {
 
                if(parent->left == curr)
 
                    parent->left = curr->right;
 
                else
 
                    parent->right = curr->right;
 
            }
 
        
 
            //----------------------------deletion of a node having left child only
 
            else if(curr->right == NULL)
 
            {
 
                if(parent->left == curr)
 
                    parent->left = curr->left;
 
                else
 
                    parent->right = curr->left;
 
            }
 
 
            //----------------------------deletion of a node having two child
 
            else if( (curr->right != NULL) && (curr->left != NULL) )
 
            {
 
                s = curr->right;
 
                
 
                temp = curr->left;
 
            
 
                while(s->left != NULL)
 
                {
 
                    s = s->left;
 
                }
 
 
                s->left = temp;
 
            
 
                if(parent->left == curr)
 
                    parent->left = curr->right;
 
 
                else
 
                    parent->right = curr->right;
 
 
            }
 
        }
 
    
 
        curr->left = NULL;
 
        curr->right = NULL;
 
        
 
        delete curr;
 
    }
 
    
 
    else
 
    {
 
        cout<<"\n\t element entered can't be found ";
 
    }
 
}
 
 
//----------------------------copy
 
void tree::copy_r(tree *cp)
 
{         
 
    root = copy_r(cp->root);
 
}
 
 
treenode* tree::copy_r(treenode* curr)
 
{        
 
    treenode* temp;    
 
    temp = NULL;
 
    
 
    if (curr != NULL) 
 
    {
 
        temp = new treenode;
 
        
 
        strcpy(temp->keyword, curr->keyword);
 
        strcpy(temp->meaning, curr->meaning);
 
        
 
        temp->left  = copy_r(curr->left);
 
        temp->right = copy_r(curr->right);
 
    }
 
    
 
    return temp;
 
}
 
 
//----------------------------recurssive mirror 
 
void tree::mirror_r()
 
{
 
    mirror_r(root);
 
}
 
 
void tree::mirror_r(treenode *curr)
 
{    
 
    if(curr != NULL)
 
    {
 
        treenode *temp = new treenode;
 
    
 
        temp = curr->left;
 
        curr->left = curr->right;
 
        curr->right = temp;
 
 
        mirror_r(curr->left);
 
        mirror_r(curr->right);
 
    }
 
}
 
 
//----------------------------queue class for breadth-force traversal
 
const int MAXSIZE = 50;
 
class queue
 
{    
 
        int front;
 
        int rear;
 
        treenode *que[MAXSIZE];
 
    public:
 
        queue()
 
        {
 
            front = rear = 0;
 
        }
 
        
 
        //----------------------------queue functions
 
        bool is_empty();
 
        bool is_full();
 
        
 
        void q_insert(treenode *);
 
        treenode *q_delete();
 
};
 
 
//----------------------------function to check emty queue 
 
bool queue::is_empty()
 
{
 
    if(front == rear)    
 
        return true;
 
    else
 
        return false;
 
}
 
 
//----------------------------function to check queue full condition
 
bool queue::is_full()
 
{
 
    if(rear == MAXSIZE)
 
        return true;
 
    else 
 
        return false;
 
}
 
 
//----------------------------insert in queue
 
void queue::q_insert(treenode *temp)
 
{
 
    if(is_full())
 
    {
 
        cout<<"the queue is full";
 
    }
 
    
 
    else
 
    {
 
        que[rear] = temp;
 
        
 
        rear++;
 
    }
 
}
 
 
//----------------------------delete from queue
 
treenode *queue::q_delete()
 
{
 
    if(is_empty())
 
    {    
 
         return NULL;
 
    }
 
         
 
    else
 
    { 
 
        treenode *temp = new treenode;
 
        temp = que[front];
 
        
 
        front++;
 
        
 
        return temp;
 
    }
 
}
 
 
//----------------------------breath force traversal
 
void tree::breadthfd_nr()
 
{
 
    treenode *temp = new treenode;
 
    temp = root;
 
    
 
    queue q;
 
    q.q_insert(temp);
 
        
 
    while( !q.is_empty() )
 
    {            
 
        temp = q.q_delete();
 
        
 
        cout<<"\n\n\tkeyword = "<<temp->keyword<<"\n\tmeaning = "<<temp->meaning;
 
        
 
        if(temp->left != NULL)
 
            q.q_insert(temp->left);
 
 
        if(temp->right != NULL)
 
            q.q_insert(temp->right);
 
    }
 
}
 
 
//----------------------------non-recurssive mirror 
 
void tree::mirror_nr()
 
{
 
    treenode *curr = new treenode;
 
    curr = root;
 
    
 
    queue q;
 
    q.q_insert(curr);
 
    
 
    while( !q.is_empty() )
 
    {
 
        curr = q.q_delete();
 
        
 
        treenode *temp = new treenode;
 
        temp = curr->left;
 
        curr->left = curr->right;
 
        curr->right = temp;
 
        
 
        if(temp->left != NULL)
 
            q.q_insert(temp->left);
 
 
        if(temp->right != NULL)
 
            q.q_insert(temp->right);
 
    }
 
}
 
 
//----------------------------recursive inorder traversal
 
void tree::inorder_r()
 
{
 
    inorder_r(root);
 
}
 
 
void tree::inorder_r(treenode *temp)
 
{
 
    if(temp != NULL)
 
    {
 
        inorder_r(temp->left);
 
        cout<<"\n\n\tkeyword = "<<temp->keyword<<"\n\tmeaning = "<<temp->meaning;
 
        inorder_r(temp->right);
 
    }
 
}
 
 
//----------------------------main function
 
int main()
 
{
 
    tree bst;
 
    tree cp_bst;
 
 
    char cont;
 
    int ch;
 
    do
 
       {
 
           //----------------------------ask user : create or traversal
 
            cout<<"\n Choose from following functions:\n\t1.Create \n\t2.Delete \n\t3.Copy \n\t4.Mirror \n\t5.Exit \n\tchoice(1/2/3/4/5):";
 
            cin>>ch;
 
            
 
        switch(ch)
 
        {
 
            //----------------------------insert
 
            case 1:
 
            {    
 
                
 
                    bst.create(); 
 
                    
 
                    cout<<"\n\tDEPTH-FORCE INORDER TRAVERSAL:";
 
                bst.inorder_r();
 
                
 
                cout<<"\n\tBREADTH-FORCE TRAVERSAL:";
 
                bst.breadthfd_nr();
 
                                 
 
                break;
 
            }
 
            
 
            //----------------------------delete
 
            case 2:
 
            {
 
                    bst.delete_nr();
 
                    
 
                    cout<<"\n\tDEPTH-FORCE INORDER TRAVERSAL FOR UPDATED TREE:";
 
                bst.inorder_r();
 
                
 
                cout<<"\n\tBREADTH-FORCE TRAVERSAL FOR UPDATED TREE:";
 
                bst.breadthfd_nr();
 
                    
 
                break;
 
            }
 
            
 
            //----------------------------copy
 
            case 3:
 
            {
 
                cp_bst.copy_r(&bst);
 
                
 
                cout<<"\n\tDEPTH-FORCE INORDER TRAVERSAL FOR COPIED BST:";
 
                cp_bst.inorder_r();
 
                
 
                cout<<"\n\tBREADTH-FORCE TRAVERSAL FOR UPDATED TREE:";
 
                cp_bst.breadthfd_nr();
 
                                
 
                break;
 
            }
 
            
 
            //----------------------------mirror
 
            case 4:
 
            {
 
                //----------------------------ask user: recursive or non-recursive
 
                int m_ch;
 
                cout<<"\n Choose from following functions:\n\t1.Recursive traversal \n\t2.Non - recursive traversal \n\tchoice(1/2):";
 
                    cin>>m_ch;
 
                    
 
                    if( (m_ch != 1) && (m_ch != 2) )
 
                    {
 
                        cout<<"\n\t\t\tINVALID CHOICE";
 
                        break;
 
                    }
 
                    
 
                    //----------------------------recursive
 
                    else if(m_ch == 1)
 
                    {
 
                        bst.mirror_r();
 
                        
 
                        cout<<"\n\tDEPTH-FORCE INORDER TRAVERSAL FOR MIRRORED TREE:";
 
                    bst.inorder_r();
 
                
 
                    cout<<"\n\tBREADTH-FORCE TRAVERSAL FOR MIRRORED TREE:";
 
                    bst.breadthfd_nr();
 
                    }
 
                    
 
                    //----------------------------non-recursive
 
                    else if(m_ch == 2)
 
                    {
 
                        bst.mirror_nr();
 
                        
 
                        cout<<"\n\tDEPTH-FORCE INORDER TRAVERSAL FOR MIRRORED TREE:";
 
                    bst.inorder_r();
 
                
 
                    cout<<"\n\tBREADTH-FORCE TRAVERSAL FOR MIRRORED TREE:";
 
                    bst.breadthfd_nr();
 
                    }
 
                    
 
                break;
 
            }
 
                    
 
            //----------------------------exit
 
            case 5:
 
            {
 
                return 0;
 
            }
 
            
 
            //----------------------------invalid input
 
            default:
 
            {
 
                cout<<"\n\t\t\tINVALID CHOICE";
 
            }
 
        }
 
        
 
        //----------------------------ask user: want to continue
 
        cout<<"\n\tdo you want to CONTINUE to MAIN MENU(y/n):   ";
 
        cin>>cont;
 
        
 
    }while( (cont == 'y') || (cont == 'Y') );
 
    
 
    return 0;
 
}


run \| edit \| history \| help	0