Sunday, 9 December 2018

CS301 Assignment No 01 Solution Fall 2018

Leave a Comment

Binary Search tree is the most efficient data structure for solving different problems. Construction of BST (Binary Search Tree) depends on the order in which data is inserted into the tree. For building a Binary Search Tree, data should be inserted into a tree in a way that nodes with smaller data values appears on left side and larger node values appears on right side of the root node.
Write a menu based system program in C++ that will allow you to:
Enter Employee data in BST buildBST()
Post order traversal of all the Employee data postOrder()
Show data in ascending order asscendingOrder()


Take the following attributes of an Employee from the user:
empId, empNname, empSalary
You have to implement the above scenario using BST on the basis of Employee Id. i.e. if the Id of the Employee is lesser than the root node then enter the next Employee data in the left child otherwise in right child.
Note:
  • BST will implement using Linked List.
  • Program will not allow entering duplicate employee id.
  • Design the program in a way that the user will be able to enter maximum 10 records.
  • Take empId, empName, empSalary from the user. At least 4 students record should be already entered (hard coded records).
You will use following already entered Employees data (hard coded records).
Emp Id Name EmpSalary
32 Raza 3000
56 Sajjad 25000
93 Rabia 19230
5 Sehar 24000
10 Ali 22200

Solution Guidelines:
  • You will use buildBST() method to build Binary Search Tree from the above given data.
  • Use the ascendingOredr() method to show the output in ascending order. With respect to empId.
  • Use postOrder() method to traverse the records in post-order.

Sample output 1:

Solution:     Download.cpp
#include<iostream>
#include<conio.h>
#include<string>
#include<cstring>

using namespace std;

struct Node
{
    int empId;
    char* empName;
    double empSalary;

    Node* left;
    Node* right;
};
Node* buildBST(Node* root, int i,int id, char* name, double salary)
{

    if(root== NULL)
    {
        Node* newNode = new Node();
        newNode->empId = id;
        newNode->empName = name;
        newNode->empSalary = salary;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if(root->empId == id)  // if the element already exists dont need to enter it again...
    {
        return root;
    }
    else if(id <= root->empId)
    {
        root->left = buildBST(root->left, i, id, name, salary);
    }
    else
    {
        root->right = buildBST(root->right, i, id, name, salary);
    }
}
void ascendingOrder(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    ascendingOrder(root->left);
    cout<<endl<<root->empId<<"\t"<<root->empName<<"\t"<<root->empSalary<<endl;
    ascendingOrder(root->right);
}
void postOrder(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->empId<<"\t"<<root->empName<<"\t"<<root->empSalary<<endl;
}

main()
{

    int id[]= {32,56,93,5,10};
    char* name[]= {"Raza","Sajid","Rabia","Sehar","Ali"};
    double salary[]= {3000, 25000, 19230, 24000, 22200};
    int c;
    int x = (sizeof(id)/sizeof(*id)); // getting the elements of the array, in that case '5'
    Node* root = NULL;
    char string[20]; //  for new entry a temporary array for getting name....


// loop for entering of the given table in the tree...
    for(int i=0; i<x; i++)
    {
        root = buildBST(root, i, id[i], name[i], salary[i]);
    }


// conditions...
s:
    cout<<endl<<"Press 1 to Enter Data \n";
    cout<<"Press 2 to see the Records in Ascending Order \n";
    cout<<"Press 3 to see the Records in Post Order \n";
    cout<<"Press 4 to Exit\n ";
    cin>>c;
    switch(c)
    {
    case 1:
    {
r:
        cout<<endl<<"Enter Employee ID : ";
        cin>>id[x];
        cout<<endl<<"Enter Employee Salary : ";
        cin>>salary[x];
        cout<<endl<<"Enter Employee Name : ";
        cin>>string;
// checking redundancy (duplication) for ID...
        for(int i=0; i<x; i++)
        {
            if(id[x] == id[i])
            {
                cout<<endl<<"Record Already Exists...";
                goto r;
            }
        }
// assigning name a dynamic memory....
        name[x] = new char[strlen(string)+1];
        strcpy(name[x], string);

// again update the tree...
        for(int i=0; i<(x+1); i++)
        {
            root = buildBST(root, i, id[i], name[i], salary[i]);
        }
        break;
    }
    case 2:
        cout<<"Ascending Order: \n";
        ascendingOrder(root);
        break;
    case 3:
        cout<<"Post Order: \n";
        postOrder(root);
        break;
    case 4:
        break;
    default:
        cout<<"\nWrong Input.";
        break;
    }
    char ch;
y:
    cout<<endl<<"DO YOU WANT TO DO SOMETHING ELSE...\nYES = y \t NO = n";
    ch = getch();
    if(ch=='y')
    {
        goto s;
    }
    else if(ch=='n')
    {
        cout<<"\nBye!";
    }
    else
    {
        cout<<endl<<"\nWrong input.";
        goto y;
    }
}

If You Enjoyed This, Take 5 Seconds To Share It

0 Questions:

Post a Comment