Implementing and Querying Binary Search Trees in C++: A Sample Assignment Solution

Welcome to our detailed sample solution for the C++ programming assignment, crafted to provide expert C++ assignment help. In this project, we demonstrate the application of recursive data structures, specifically binary search trees, in C++. You will learn to implement and query binary search trees, addressing tasks such as counting total advisees and identifying faculty members with no direct or indirect supervisees. This sample not only highlights our proficiency in handling complex C++ problems but also provides a clear example of how to manage recursive algorithms and data structures effectively. Through this demonstration, you’ll gain valuable insights into advanced programming techniques and best practices in C++. For further assistance and comprehensive support, feel free to reach out for help with programming assignments.

Question:

Solution:

Demo

C++ CODE

//TODO: WRITE YOUR HEADER COMMENT :-) #include <iostream> #include <fstream> #include <string> #include <stdlib.h> using namespace std; struct Node { string name; Node *supervisee_1; Node *supervisee_2; int advisee_count; }; const string PRINT = "p"; const string ADD_A = "a"; const string ADD_F = "f"; const string TOTAL = "t"; const string SLACKER = "s"; const string QUIT = "q"; Node *new_node(string name); Node *read_file(string filename); void print_advisees(Node *curr_node, string bureaucracy); Node *find_node(Node *curr_node, string name); int count_advisees(Node* curr_node); void print_slackers(Node* curr_node); void delete_tree(Node* curr_node); //STYLE NOTE: You do not have to worry about making main() fit in 30 lines for //this assignment! int main(int argc, char *argv[]) { if (argc < 2) { cerr << "ERROR: No filename provided as an argument" << endl; exit(EXIT_FAILURE); } Node *boss = read_file(argv[1]); //Loop to continually prompt for queries string c; cout << "Enter a query: "; while (cin >> c) { if (c == PRINT) { print_advisees(boss, ""); } else if (c == TOTAL) { /////////// YOUR CODE GOES HERE /////////// string facultyName; cin >> facultyName; Node* facultyNode = find_node(boss, facultyName); if (facultyNode == nullptr) { cout << "Faculty member not found." << endl; } else { int totalAdvisees = count_advisees(facultyNode); cout << facultyName << " is responsible for " << totalAdvisees << " advisee(s)." << endl; } } else if (c == SLACKER) { print_slackers(boss); } else if (c == QUIT) { delete_tree(boss); exit(0); } else if (c == ADD_A) { } else if (c == ADD_F) { } else { cout << c << " not recognized." << endl; } cout << endl << "Enter a query: "; } return 0; } //Print the tree path of every person who has advisees void print_advisees(Node *curr_node, string bureaucracy) { //Base Case: If we are at a person who has advisees, print the count if (curr_node->advisee_count > 0) { cout << bureaucracy; cout << curr_node->name + "->"; cout << curr_node->advisee_count << endl; } else { //Recursive Cases: If we are at a person who doesn't have advisees, //recurse to their subtrees if (curr_node->supervisee_1 != nullptr) { string bureaucracy_left = bureaucracy + curr_node->name + "->"; print_advisees(curr_node->supervisee_1, bureaucracy_left); } if (curr_node->supervisee_2 != nullptr) { string bureaucracy_right = bureaucracy + curr_node->name + "->"; print_advisees(curr_node->supervisee_2, bureaucracy_right); } } } //Read file and build tree structure, returning root "boss" node. //STYLE NOTE: You do not have to worry about paring down read_file() to a //30-line limit for this assignment. Node *read_file(string filename) { //Open the given file ifstream infile(filename); if (infile.fail()) { cerr << "ERROR: Error opening file, please check file name: " << filename << endl; exit(EXIT_FAILURE); } //Read the first line of the file string supervisor; string supervisee; infile >> supervisor; infile >> supervisee; Node *boss = new_node(supervisor); bool first_line = true; //Process each line of the file while (!infile.eof()) { Node *supervisor_node; //Initialize the root node if we're on the first line of the file if (first_line) { supervisor_node = boss; first_line = false; } else { supervisor_node = find_node(boss, supervisor); } //Check if we're dealing with an advisor or a supervisor if (supervisee == "Advisee") { supervisor_node->advisee_count++; } else { //Determine if supervisee should be the first or second supervisee if (supervisor > supervisee) { supervisor_node->supervisee_1 = new_node(supervisee); } else { supervisor_node->supervisee_2 = new_node(supervisee); } } //Read the next line infile >> supervisor; infile >> supervisee; } infile.close(); return boss; } //Finds and returns the node with the given name Node *find_node(Node *curr_node, string name) { //Base Case: If curr_node is the person we're looking for, return it if (curr_node->name == name) { return curr_node; //Recursive Cases: Search either the left or right subtree for the name } else if (curr_node->name > name) { if (curr_node->supervisee_1 == nullptr) { return nullptr; } return find_node(curr_node->supervisee_1, name); } else { if (curr_node->supervisee_2 == nullptr) { return nullptr; } return find_node(curr_node->supervisee_2, name); } return nullptr; } //Returns a new node that is blank except for the provided name Node *new_node(string name) { Node *new_node = new Node; new_node->name = name; new_node->supervisee_1 = nullptr; new_node->supervisee_2 = nullptr; new_node->advisee_count = 0; return new_node; } int count_advisees(Node* curr_node) { if (curr_node == nullptr) return 0; int total = curr_node->advisee_count; total += count_advisees(curr_node->supervisee_1); total += count_advisees(curr_node->supervisee_2); return total; } void print_slackers(Node* curr_node) { if (curr_node == nullptr) return; // Check if the current node is a 'slacker' if (curr_node->advisee_count == 0 && curr_node->supervisee_1 == nullptr && curr_node->supervisee_2 == nullptr) { cout << "Slacker: " << curr_node->name << endl; } // Recursive calls print_slackers(curr_node->supervisee_1); print_slackers(curr_node->supervisee_2); } void delete_tree(Node* curr_node) { if (curr_node == nullptr) return; delete_tree(curr_node->supervisee_1); delete_tree(curr_node->supervisee_2); delete curr_node; }