You are required to create a program using C++ programming language to implement binary search tree (BST).
Problem Statement:
You are working for a company that manages a database of employee records. Your task is to implement a binary search tree to store employee records efficiently and in an organized manner. Each employee record consists of a unique employee ID, name, and salary. The binary search tree should allow efficient search and insertion of employee records based on their employee ID.
The program will prompt the user to enter the ID and name as input. The Employee ID should be the last three digits of your VUID and the salary should be the last five digits of the VUID. The program will extract the Employee ID and salary from the VUID entered by the user. For example, if a student has a VUID of "BC123456789", the user should enter "123456789" as the ID, and the program will extract "789" as the Employee ID and "56789" as the salary.
That first record should be hardcoded and that should be your VU ID. Once the program is running, you will be able to search for employee records based on their Employee ID. Additionally, you can insert more records into the binary search tree as your application continues to run.
You are required to create a program using C++ programming language to implement binary search tree (BST).
Program:
#include <iostream>
using namespace std;
class Node {
private:
int empID;
string name;
double salary;
Node* left;
Node* right;
public:
Node(int id, string n, double s) : empID(id), name(n), salary(s), left(NULL), right(NULL) {}
int getEmpID() {
return empID;
}
string getName() {
return name;
}
double getSalary() {
return salary;
}
Node* getLeft() {
return left;
}
Node* getRight() {
return right;
}
friend class BST;
};
class BST {
private:
Node* root;
void printInOrder(Node* node) {
if (node != NULL) {
printInOrder(node->getLeft());
cout << "ID: " << node->getEmpID() << ", Name: " << node->getName() << ", Salary: " << node->getSalary() << endl;
printInOrder(node->getRight());
}
}
public:
BST() : root(NULL) {}
void insert(int id, string name) {
Node* newNode = new Node(id, name, 0.0);
if (root == NULL) {
root = newNode;
cout << "New employee record inserted successfully!" << endl;
return;
}
Node* currNode = root;
Node* parent = NULL;
while (currNode != NULL) {
parent = currNode;
if (id < currNode->getEmpID()) {
currNode = currNode->getLeft();
} else if (id > currNode->getEmpID()) {
currNode = currNode->getRight();
} else {
cout << "Employee record with the same ID already exists!" << endl;
return;
}
}
if (id < parent->getEmpID()) {
parent->left = newNode;
} else {
parent->right = newNode;
}
cout << "New employee record inserted successfully!" << endl;
}
Node* search(int id) {
Node* currNode = root;
while (currNode != NULL) {
if (id < currNode->getEmpID()) {
currNode = currNode->getLeft();
} else if (id > currNode->getEmpID()) {
currNode = currNode->getRight();
} else {
return currNode;
}
}
return NULL;
}
void printAllRecords() {
if (root == NULL) {
cout << "No employee records found!" << endl;
return;
}
cout << "Existing Employee Records:" << endl;
printInOrder(root);
}
};
int main() {
BST bst;
// Hard-coded record
bst.insert(789, "Fahad");
int choice;
do {
cout << "\nEnter 1 to check the existing record" << endl;
cout << "Enter 2 to insert a new employee record" << endl;
cout << "Enter 3 to search for an employee record" << endl;
cout << "Enter 4 to exit" << endl;
cin >> choice;
switch (choice) {
case 1:
bst.printAllRecords();
break;
case 2: {
int id;
string name;
cout << "Enter Employee ID: ";
cin >> id;
cout << "Enter Employee Name: ";
cin >> name;
bst.insert(id, name);
break;
}
case 3: {
int id;
cout << "Enter employee ID: ";
cin >> id;
Node* result = bst.search(id);
if (result != NULL) {
cout << "Employee found: --> ID: " << result->getEmpID() << endl;
cout << "Name: " << result->getName() << endl;
cout << "Salary: " << result->getSalary() << endl;
} else {
cout << "Employee not found!" << endl;
}
break;
}
case 4:
cout << "Exiting program..." << endl;
break;
default:
cout << "Invalid choice! Please try again." << endl;
break;
}
} while (choice != 4);
return 0;
}
Sample Output:
No comments