please find attached specification of assignmentBinary Search Tree Overview Your task is to...

Question

please find attached specification of assignment

Binary Search Tree Overview Your task is to implement a BST class, where every vertex is denoted by a string, and every vertex has a weight. The class should allow the weight to be any numeric data type, such as int, float, or double. The vertices are sorted by their weights. For example, the following BST has 8 vertices: "C", "A", "H", "D", "G", "F", "B", "E" (we list the vertices in breath-first traversal order). These vertices have weights of 5, 1, 10, 3, 20, 15, 30, 17. The class should offer a reasonably effective suite of operations, including but not limited to: · Adding and removing nodes (and relevant edge adding and removal). · Depth-first and breadth-first traversals (Preorder, Inorder, Postorder, BFS). · Finding paths that meet certain conditions. The Code You are provided with two files: · tree.hpp: this includes most of the basic definitions you will need. You should define data structures to represent a Binary Search Tree and implement the functions so that they can work correctly. You may add new includes, classes, functions, and/or variables to the class per your need, as long as they do not interfere with the existing definitions. You must NOT change the class name, template, parameters, or return types of functions. · main.cpp: this includes a main function. You may write some code to test your data structures and function implementations for the class. This file will not be marked so you can do anything you like with it -- just ensure it does not cause any error. When the "run" button is pressed, it will compile and run main.cpp. The code has been commented on to explain the purpose of each function. Remember to read over all the code before starting. MAIN.CPP #include "tree.hpp" int main(){ BST t; t.add_vertex("A", 1); t.add_vertex("B", 3); t.add_vertex("C", 5); t.add_vertex("D", 10); t.add_vertex("G", 20); t.add_vertex("E", 15); t.add_vertex("H", 30); t.add_vertex("F", 17); cout < boolalpha;="" cout="">< t.num_vertices()="">< endl;="" cout="">< t.num_edges()="">< endl;="" cout="">< t.sum_weight()="">< endl;="" for(auto="" x="" :="" t.path_with_largest_weight()){="" cout="">< x="">< "="" ";="" }="" cout="">< endl;="" }="" tree.hpp="" #include=""> #include #include #include #include

#include #include #include #include #include #include #include #include #include using namespace std; template // the template allows the weight of vertex to take any numeric data type (denoted by T). class BST { public: /* define your data structure to represent a binary search tree (bst) */ /* test1 */ BST(); // the contructor function. ~BST(); // the destructor function. size_t num_vertices(); // returns the total number of vertices in the bst. size_t num_edges(); // returns the total number of edges in the bst. T sum_weight(); // return the total weight of all the vertices in the bst. /* test2 */ void add_vertex(const string&, const T&); // adds a vertex, which has a weight, to the tree -- every vertex uses a string as its unique identifier. bool contains(const string&); // checks if a vertex is in the bst -- returns true if the bst contains the given vertex; otherwise, returns false. /* test3 */ vector get_vertices(); // returns a vector of all the vertices in the bst. vector get_leaves(); // returns a vector of all the leaves in the bst. // Leaves are the vertices that do not have any children in the bst. /* test4 */ bool adjacent(const string&, const string&); // check if there is an edge between the two vertices in the bst -- returns true if the edge exists; otherwise, returns false. /* test5 */ vector<>> get_edges(); // returns a vector of all the edges in the bst -- each edge is represented by a pair of vertices incident to the edge. /* test6 */ vector get_neighbours(const string&); // returns a vector of all the vertices, each of which is directly connected with the given vertex via an edge. size_t degree(const string&); // returns the degree of a vertex. /* test7 */ vector preorder_traversal(); // returns a vector of all the vertices in the visiting order of a preorder traversal over the bst. /* test8 */ vector inorder_traversal(); // returns a vector of all the vertices in the visiting order of an inorder traversal over the bst. /* test9 */ vector postorder_traversal(); // returns a vector of all the vertices in the visiting order of a postorder traversal over the bst. /* test10 */ vector breadth_first_traversal(); // returns a vector of all the vertices in the visiting order of a breadth first traversal over the bst. /* test11 */ vector path(const string&, const string&); // returns a vector of all the vertices in the path from the first vertex to the second vertex. // A path should include the source and destination vertices at the begining and the end, respectively. /* test12 */ vector path_with_largest_weight(); // returns a path that has the largest weight in the bst. // The weight of a path is the sum of the weights of all the vertices (including the source and destination vertices) in the path. /* test13 */ size_t height(); // returns the height of bst. Height of a tree is the number of edges that form the longest path from root to any leaf. /* test14 */ void remove_vertex(const string&); // delete the given vertex from bst -- note that, all incident edges of the vertex should be deleted as well. }; /* test1 */ template BST::BST() {} template BST::~BST() {} template size_t BST::num_vertices() { return 0; } template size_t BST::num_edges() { return 0; } template T BST::sum_weight() { return 0; } /* test2 */ template void BST::add_vertex(const string& u, const T& w) { } template bool BST::contains(const string& u) { return false; } /* test3 */ template vector BST::get_vertices() { return vector(); } template vector BST::get_leaves() { return vector(); } /* test4 */ template bool BST::adjacent(const string& u, const string& v) { return false; } /* test5 */ template vector<>> BST::get_edges() { return vector<>>(); } /* test6 */ template vector BST::get_neighbours(const string& u) { return vector(); } template size_t BST::degree(const string& u) { return 0; } /* test7 */ template vector BST::preorder_traversal() { return vector(); } /* test8 */ template vector BST::inorder_traversal() { return vector(); } /* test9 */ template vector BST::postorder_traversal() { return vector(); } /* test10 */ template vector BST::breadth_first_traversal() { return vector(); } /* test11 */ template vector BST::path(const string& u, const string& v){ return vector(); } /* test12 */ template vector BST::path_with_largest_weight(){ return vector(); } /* test13 */ template size_t BST::height() { return 0; } /* test14 */ template void BST::remove_vertex(const string& u) { }

binary-search-tree-rsuugicn.docx

Binary Search Tree Overview Your task is to implement a BST class, where every vertex is denoted by a string, and every vertex has a weight. The class should allow the weight to be any numeric data...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment