Question
HELP fill out BSTree.hpp! Assignment Description: For many movie lovers, actors and directors, the annual Academy Awards are the highlight of the year. Everyone dresses
HELP fill out BSTree.hpp!
Assignment Description:
For many movie lovers, actors and directors, the annual Academy Awards are the highlight of the year. Everyone dresses up, they walk the red-carpet, listen to long and boring speeches and generally pat themselves on the backbut have you ever wondered which movies are the top movies, or who has received the most awards. We are going to do our own data analysis. You will develop a simple database system. The database is to handle multiple records, each composed of several fields. The database will store its information to a file, addition, and deletion of records, field modifications, and it will allow users to sort records based on the selected keys, and produce reports (output) according to predefined criteria.
My Request/Question:
I need help filling out the functionality for the BSTree.hpp file! Can someone please fill in the correct functionality where it says in a comment "Student must fill in"
All Given Code Download Link:
(https://online.coffeecloudstorage.com/index.php/s/YwHJsFjjBjbWQyx)
Code is also in plain Text Below:
BSTree.hpp Code (This is the code I need help with)(It is also included in the download link with all the other code) :
//To be used in conjunction with BSTree.h and Node.h
//When you modify this, please add your name and list any changes that you made
//A few member functions have been left blank so you, the student can implemement
/*Template Directions: #include "BSTREEInt.hpp"
but do NOT compile it (or add it to the project)*/
#include "BSTree.h"
// Constructor
template
BSTree::BSTree() {
root = nullptr;
}
// Destructor
template
BSTree::~BSTree() {
if (root !=nullptr)
freeNode(root);
}
// Free the node
template
void BSTree::freeNode(Node * leaf)
{
//Student must fill in
//if the root is the leaf, delete that leaf
// otherwise if the leaf is not null
//recursive call of the leaf's left
//recursive call of the leaf's right
//now delete the leaf
}
// Add a node
template
void BSTree::addNode(KEYTYPE key, DATATYPE &data)
{
if (Root() == nullptr)
{
Node * newNodePtr = new Node;
newNodePtr->setKey(key);
newNodePtr->setData(data);
root = newNodePtr;
root->setParent(root);
}
else
addNode(key, root, data);
}
// Add a node (private)
template
void BSTree::addNode(KEYTYPE key, Node * leaf, DATATYPE& data) {
//Student must fill in
//Don't forget to set your key, Parent, then left or right
//Based on the case you use you will addNode recursively to the left or right
//First check if root is null
//make a new node
//set the key and data
//set the root
//Otherwise
//Check to see if the key is < the leaf's key
// if left is not null then
//Add the node to the left (recursively)
// Otherwise make a new node and attach it to the left
//Check to see if the key >= leaf's key
// if leaf's right is not null then
//Add the node to the right (recursively)
// Otherwise make new node and attach it to the right
}
template
Node * BSTree::findNode(KEYTYPE key)
{
return findNode(key, root);
}
// Find a node
template
Node * BSTree::findNode(KEYTYPE key, Node * node)
{
//Student must fill in
// trap nullptr first in case we've hit the end unsuccessfully.
// success base case
//Greater than (Right), Less than (Left)
}
template
void BSTree::printInorder()
{
printInorder(root);
}
template
void BSTree::printInorder(Node * node)
{
//Student must fill in. Use recursive algorithm.
//Note that this prints using an Inorder, Depth-first search
//but you may want to do something else when "visiting" the node....
//like moving visited data to another datastructure
//Don't forget your base case!
}
template
void BSTree::print(ostream & out, const DATATYPE & data)
{
out << data.number << "\t" << data.name << endl;
}
template
void BSTree::deleteNode(KEYTYPE key)
{
setRoot(deleteNode(Root(), key));
}
//deleteNode (Private)
template
Node * BSTree::deleteNode(Node * aRoot,KEYTYPE value)
{
/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
// base case
if (aRoot == nullptr) return aRoot;
// If the key to be deleted is smaller than the aRoot's key,
// then it lies in left subtree
if (value < aRoot->Key())
aRoot->setLeft(deleteNode(aRoot->Left(), value));
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (value > aRoot->Key())
root->setRight(deleteNode(aRoot->Right(), value));
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (aRoot->Left() == nullptr)
{
Node *temp = aRoot->Right();
delete aRoot;
return temp;
}
else if (aRoot->Right() == nullptr)
{
Node *temp = aRoot->Left();
delete aRoot;
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node * temp = min(aRoot->Right());
// Copy the inorder successor's content to this node
aRoot->setKey(temp->Key());
aRoot->setData(temp->Data());
// Delete the inorder successor
aRoot->setRight(deleteNode(aRoot->Right(), temp->Key()));
}
return aRoot;
}
// Find the node with min key
// Traverse the left sub-BSTree recursively
// till left sub-BSTree is empty to get min
template
Node * BSTree::min(Node * node)
{
Node * current = node;
/* loop down to find the leftmost leaf */
while (current->Left() != nullptr)
current = current->Left();
return current;
}
// Find the node with max key
// Traverse the right sub-BSTree recursively
// till right sub-BSTree is empty to get max
template
Node * BSTree::max(Node * node)
{
Node * tempNode = node;
if (node == nullptr)
tempNode = nullptr;
else if (node->Right())
tempNode = max(node->Right());
else
tempNode = node;
return tempNode;
}
BSTree.h Code:
//To be used in conjunction with Node.h and BSTree.cpp
//If you modify this, please add your name and list any changes that you made
#ifndef BSTREEINT_H
#define BSTREEINT_H
#include
using namespace std;
#include "Node.h"
// Binary Search Tree class
template
class BSTree {
private:
Node * root;
void addNode(KEYTYPE key, Node * leaf, DATATYPE& data);
Node * deleteNode(Node * node, KEYTYPE key);
void freeNode(Node * leaf);
void printInorder(Node * node);
Node * findNode(KEYTYPE key, Node * node);
public:
BSTree();
~BSTree();
Node * Root() { return root; }
void setRoot(Node * _root) {root = _root;}
void addNode(KEYTYPE key, DATATYPE &data);
Node * findNode(KEYTYPE key);
void printInorder();
void print(ostream & out, const DATATYPE & data);
void deleteNode(KEYTYPE key);
Node * min(Node * node);
Node * max(Node * node);
};
#endif //BST
Node.h Code:
//To be used in conjunction with BSTree.h and BSTree.hpp
//If you modify this, please add your name and list any changes that you made
#ifndef NODE_
#define NODE_
#include
#include
using namespace std;
// A tree node class for ints
//Placeholder for a composite data type
struct GeneralData
{
int number; //Update this to your data field
string name;
};
//Binary Tree Node
template
class Node {
private:
int key; //This should be the datatype of your key...sorted field in tree
DATATYPE data;
Node * left;
Node * right;
Node * parent;
public:
Node() {left=nullptr; right=nullptr; parent = nullptr;};
void setKey(KEYTYPE aKey) { key = aKey; };
void setData(DATATYPE aData) { data = aData; }
void setLeft(Node * aLeft) { left = aLeft; };
void setRight(Node * aRight) { right = aRight; };
void setParent(Node * aParent) { parent = aParent; };
KEYTYPE Key() { return key; };
DATATYPE Data() { return data; }
Node * Left() { return left; };
Node * Right() { return right; };
Node * Parent() { return parent; };
};
#endif
BSTDriver.cpp Code:
/*Template Directions: #include "BSTREEInt.hpp"
but do NOT compile it (or add it to the project)*/
#include
#include "BSTree.h"
#include "BSTree.hpp"
using namespace std;
int main()
{
BSTree *tree = new BSTree;
cout << "Adding Nodes... ";
GeneralData tempData;
tempData.number = 10;
tempData.name = "Gamma";
tree->addNode(tempData.number, tempData);
tempData.number = 5;
tempData.name = "Gamma";
tree->addNode(tempData.number, tempData);
tempData.number = 1;
tempData.name = "Alpha";
tree->addNode(tempData.number, tempData);
tempData.number = 20;
tempData.name = "Delta";
tree->addNode(tempData.number, tempData);
tempData.number = 30;
tempData.name = "Eta";
tree->addNode(tempData.number, tempData);
tempData.number = 25;
tempData.name = "Epsilon";
tree->addNode(tempData.number, tempData);
tempData.number = 2;
tempData.name = "Beta";
tree->addNode(tempData.number, tempData);
cout << "Printing in order... ";
tree->printInorder();
if (tree->findNode(25) != nullptr)
cout << "25 found ";
else
cout << "25 not found ";
if (tree->findNode(26) != nullptr)
cout << "26 found ";
else
cout << "26 not found ";
cout << "After Deleting 1... ";
tree->deleteNode(1);
tree->printInorder();
cout << "After Deleting 10... ";
tree->deleteNode(10);
tree->printInorder();
cout << "After Deleting 25... ";
tree->deleteNode(25);
tree->printInorder();
cout << "After Deleting 2... ";
tree->deleteNode(2);
tree->printInorder();
cout << "After Deleting 5... ";
tree->deleteNode(5);
tree->printInorder();
cout << "After Deleting 20... ";
tree->deleteNode(20);
tree->printInorder();
cout << "After Deleting 30... ";
tree->deleteNode(30);
tree->printInorder();
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
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