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 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();

}