×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

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

September 06, 2024
Alexander Gough
Alexander Gough
🇺🇸 United States
C++
Alexander Gough is a seasoned C++ programmer with over a decade of experience in developing advanced algorithms and data structures. Specializing in recursive problem-solving and binary search trees, Alexander excels in providing tailored solutions for complex programming assignments. His expertise ensures clear, efficient code and insightful guidance, making him a top choice for C++ assignment help.
Key Topics
  • Question:
  • Solution:
    • Demo
    • C++ CODE
Tip of the day
Use the REPL (Read-Eval-Print Loop) to test your code interactively, and practice writing concise, readable expressions to harness Scala’s powerful syntax effectively.
News
In 2024, universities abroad, like Dublin City University, have introduced cutting-edge programming courses, including Computer Engineering programs focusing on AI and machine learning.

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:

Querying-Binary

Querying-Binary-1

Querying-Binary-2

Querying-Binary-3

Querying-Binary-4

Querying-Binary-5

Querying-Binary-6

Solution:

Querying-Binary-7

Querying-Binary-Search-Trees

Querying Binary Search Trees-1

Demo

Querying-Binary-9

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; }

Similar Samples

We offer professional programming assignment services tailored to student needs. Browse our sample programming questions to evaluate the quality of our work and rate them. Let our expertise help you succeed with accurate, timely solutions designed to simplify your academic journey.