hello there

In C++, implement the cpp file by following the instructions given in the comments of the code #ifndef BST_H #define BST_H #include // We will be storing Pokemon in the nodes of our BST struct Pokemon { int number; std::string name; std::string type; }; std::string to_string(const Pokemon& p); class BST { public: BST(); // insert void catchPokemon(const Pokemon& p); // delete void releasePokemon(int key); // search const Pokemon* searchForPokemon(int key) const; // in-order traversal and pretty printing std::string orderedListOfCaughtPokemon() const; // This has been implemented for you for debugging purposes std::string toGraphviz() const; private: struct BSTNode { int key; Pokemon data; BSTNode* left; BSTNode* right; BSTNode* parent; }; // in-order traversal recursive helper std::string inOrder(BSTNode* root) const; // search helper function BSTNode* search(int key) const; // remove helper function void remove(BSTNode* key); // predecessor function, used in the remove function BSTNode* predecessor(BSTNode* n) const; // pointer to the root node BSTNode* root; }; #endif /* BST_H */ // cpp file #include "bst.h" #include #include #include #include using namespace std; std::string to_string(const Pokemon& p) { return to_string(p.number) + ": " + p.name + " (" + p.type + ")"; } // constructor // FX: make the tree start out empty BST::BST() {} // This is the insert function // FX: add a new BSTNode (created on the heap) into the current tree // the key of the new node is p.number, and the data is p void BST::catchPokemon(const Pokemon& p) { // emtpy tree case: make this pokemon the root and you're done // Otherwise, the root is not null and we need to search-- // Search for the node to make sure it's not already there. // If it's already there, just return from this function without // doing anything. // If we got this far, add a new Node in the correct location // Remember to set the parent, left, and right properly } // FX: search for a node by key // return a pointer if you find it // otherwise return nullptr if the key doesn't exist in the tree BST::BSTNode* BST::search(int key) const { return nullptr; } // call the search() helper function to do the heavy lifting const Pokemon* BST::searchForPokemon(int key) const { BSTNode* n = search(key); if (n == nullptr) return nullptr; else return &n->data; } std::string BST::orderedListOfCaughtPokemon() const { return inOrder(root); }\ std::string BST::inOrder(BSTNode* root) const { if (root == nullptr) return ""; else return inOrder(root->left) + to_string(root->data) + ' ' + inOrder(root->right); } // FX: return the predecessor of a given node // return nullptr if there is no predecessor BST::BSTNode* BST::predecessor(BSTNode* n) const { // if n has a left node, go left and then right as far as you can // otherwise, if n has no left pointer, one of the parents is the predecessor // SPECIAL CASE: Return nullptr if there is no predecessor return nullptr; } // This is the "remove" function that the user gets to see/use // FX: use the search and remove functions to delete a key if it exists void BST::releasePokemon(int key) { // first we need to search to find the node // case 0: node doesn't exist; do nothing // if the node does exist, call the remove method on it } // FX: Implement this method // deletes a given node from the tree--remember to implement every case! void BST::remove(BSTNode* n) { // case 1: node is a leaf; just delete it and make the parent forget // case 2: node has one child; replace the parent's child with that one // case 3: node has two children; now we need to use the predecessor // remember to actually delete the node in cases 1 and 2! } // use this method to help you debug // paste the output into webgraphviz.com to visualize your tree // you can call this method in GDB with "call puts(b.toGraphviz())" std::string BST::toGraphviz() const { if (root == nullptr) { return "The root is null--there is no tree to draw!"; } string out = "Paste everything between the ===== lines into " " webgraphviz.com " "==================================== " "digraph BST { " " node [fontname=\"Arial\" ]; "; vector nodes; queue q; q.push(root); while (!q.empty()) { BSTNode* front = q.front(); q.pop(); nodes.push_back(front); if (front->left != nullptr) q.push(front->left); if (front->right != nullptr) q.push(front->right); } list nodeDefinitions; for (BSTNode* n : nodes) { stringstream ss; ss << n; string nodeName = "n" + ss.str(); string nodeInfo = ""; // mark which is the root if (n == root) { nodeInfo = "\ (root)"; } else if (n->parent != nullptr) { nodeInfo = "\ (parent is " + to_string(n->parent->key) + ")"; } nodeDefinitions.push_back(nodeName + " [ label = \"" + to_string(n->key) + ": " + n->data.name + nodeInfo + "\" ];"); } vector edges; for (BSTNode* n : nodes) { stringstream ss; ss << n; string nodeName = "n" + ss.str(); string leftNode; if (n->left != nullptr) { ss.str(""); ss << n->left; leftNode = "n" + ss.str(); } else { // make a null node leftNode = "nullleft" + nodeName; // this node needs to appear before the right child // just put it at the front if (n->right != nullptr) { // we've already pushed the right node to the nodeDefinitions vector // for the correct order this left node needs to appear before it nodeDefinitions.push_front(leftNode + " [ shape = point ];"); } else { nodeDefinitions.push_back(leftNode + " [ shape = point ];"); } } string rightNode; if (n->right != nullptr) { ss.str(""); ss << n->right; rightNode = "n" + ss.str(); } else { // make a null node rightNode = "nullright" + nodeName; nodeDefinitions.push_back(rightNode + " [ shape = point ];"); } // edges.push_back(nodeName + " -> { " + leftNode + " " + rightNode + " // };"); edges.push_back(nodeName + " -> " + leftNode + " [ label = \"left\"] ;"); edges.push_back(nodeName + " -> " + rightNode + " [ label = \"right\"] ;"); } for (const string& s : nodeDefinitions) { out += " " + s + " "; } out += " "; for (const string& s : edges) { out += " " + s + " "; } out += "} " "==================================== "; return out; }