Question: 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
Question: 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
std::string to_string(const Pokemon& p) { return to_string(p.number) + ": " + p.name + " (" + p.type + ")"; }
// constructor // F?X??: make the tree start out empty BST::BST() {}
// This is the insert function // F?X??: 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 }
// F?X??: 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); }
// F?X??: 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 // F?X??: 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 }
// F?X??: 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
list
nodeDefinitions.push_back(nodeName + " [ label = \"" + to_string(n->key) + ": " + n->data.name + nodeInfo + "\" ];"); }
vector
stringstream ss; ss
string leftNode; if (n->left != nullptr) { ss.str(""); ss 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 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;
Step by Step Solution
There are 3 Steps involved in it
Step: 1
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Authors: Dharma P. Agrawal, Qing An Zeng
4th edition
1305087135, 978-1305087132, 9781305259621, 1305259629, 9781305537910 , 978-130508713
