C++ Binary Search Tree #ifndef MOVIETREE_HPP #define MOVIETREE_HPP #include <str
ID: 3605562 • Letter: C
Question
C++ Binary Search Tree
#ifndef MOVIETREE_HPP
#define MOVIETREE_HPP
#include <string>
struct MovieNode
{
int ranking;
std::string title;
int year;
int quantity;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;
MovieNode(){};
MovieNode(int in_ranking, std::string in_title,
int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
parent = leftChild = rightChild = nullptr;
}
};
class MovieTree
{
public:
MovieTree();
~MovieTree();
void printMovieInventory();
void addMovieNode(int ranking, std::string title,
int releaseYear, int quantity);
void findMovie(std::string title);
void rentMovie(std::string title);
void deleteMovie(std::string title);
void countMovies();
private:
MovieNode *search(MovieNode *node, std::string title);
MovieNode *root;
};
#endif // MOVIETREE_HPP
Here is the code I have so far:
#include "MovieTree.hpp"
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
MovieTree::MovieTree(){
root = NULL;
}
MovieTree::~MovieTree(){
delete root;
}
MovieNode* MovieTree::search(MovieNode *node, string title){
node = root;
if (root == NULL){
cout << "Movie not found." << endl;
}
//node = root;
while (node != NULL){
//int tit_comp = node ->title.compare(title);
if (node && node -> title == title){
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << node -> ranking << endl;
cout << "Title:" << node -> title << endl;
cout << "Year:" << node -> year << endl;
cout << "Quantity:" << node -> quantity << endl;
break;
}
else
{
//cout << "Movie not found." << endl;
break;
}
}
return node;
}
void MovieTree::findMovie(string title){
MovieNode *foundMovie = search(root, title);
if (title < foundMovie -> title)
{
if (foundMovie -> leftChild == NULL)
{
//cout << "Movie not found." << endl;
return;
}
else {
foundMovie = foundMovie->leftChild;
}
}
else
{
if (foundMovie -> rightChild == NULL)
{
//cout << "Movie not found."<< endl;
return;
}
else
{
foundMovie = foundMovie->rightChild;
}
}
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie -> ranking << endl;
cout << "Title:" << foundMovie -> title << endl;
cout << "Year:" << foundMovie -> year << endl;
cout << "Quantity:" << foundMovie -> quantity << endl;
}
void printMovieHelp(MovieNode *node)
{
if (node == NULL)
{
return;
}
else
{
printMovieHelp(node -> leftChild);
cout << "Movie: " << node -> title << " " << node -> quantity <<endl;
printMovieHelp(node -> rightChild);
}
}
void MovieTree::printMovieInventory()
{
if (root == NULL)
{
return;
}
else
{
printMovieHelp(root);
}
}
MovieNode *searchMovieTree(MovieNode *node, string title){
if (node -> title == title)
{
return node -> parent;
}
else if (node ->title > title)
{
if (node -> leftChild == NULL)
{
return node;
}
return searchMovieTree(node -> leftChild, title);
}
else {
if (node -> rightChild == NULL)
{
return node;
}
return searchMovieTree(node -> rightChild, title);
}
}
void addHelper( MovieNode* root, MovieNode* addNode);
void MovieTree::addMovieNode(int ranking, std::string title, int year, int quantity){
MovieNode *addNode = new MovieNode;
addNode -> ranking = ranking;
addNode -> title = title;
addNode -> year = year;
addNode -> quantity = quantity;
addNode -> leftChild = NULL;
addNode -> rightChild = NULL;
if ( root == NULL )
root = addNode;
else
addHelper( root, addNode );
//return root;
}
void addHelper( MovieNode* root, MovieNode* addNode){
//MovieNode *foundMovie = searchMovieTree(root, title);
if( addNode -> title < root -> title ){
if( root -> leftChild != NULL )
addHelper( root -> leftChild, addNode );
else
root -> leftChild = addNode;
}
else {
if( root -> rightChild != NULL )
addHelper( root -> rightChild, addNode );
else
root -> rightChild = addNode;
}
}
void MovieTree::rentMovie(string title){
MovieNode *found_Movie = root;
if (root == NULL){
cout << "Movie not found." << endl;
return;
}
found_Movie = root;
while (found_Movie != NULL){
int tit_comp = found_Movie -> title.compare(title);
if (tit_comp > 0){
found_Movie = found_Movie -> leftChild;
}
else if (tit_comp < 0){
found_Movie = found_Movie -> rightChild;
}
else {
//found_Movie = root;
if (found_Movie -> quantity > 0)
{
found_Movie -> quantity--;
cout << "Movie has been rented." << endl;
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << found_Movie -> ranking << endl;
cout << "Title:" << found_Movie -> title << endl;
cout << "Year:" << found_Movie -> year << endl;
cout << "Quantity:" << found_Movie -> quantity << endl;
//break;
return;
}
else if (found_Movie -> quantity == 0){
cout << "Movie out of stock." << endl;
return;
//break;
}
}
}
if (found_Movie && found_Movie -> title == title){
return;
}
else
{
cout << "Movie not found." << endl;
return;
}
}
PLEASE ADD THE FOLLOWING FUNCTIONS:
void deleteMovie(std::string title);
void countMovies();
YOU CANNOT CHANGE THE PARAMETERS. You may add helper functions if needed however you may not edit the .hpp file. Will give thumbs up for correct answer with explanation
Program Specifications Add the following functionality to your Assignment 5 Binary Search Tree implementation: 1. Delete a movie. When the user selects this option, they should be prompted for the title of the movie to delete. Your code should then search the tree for that movie node, remove it from the tree, re-assign pointers to bypass the removed node, and free the memory used by the node. If the node to be deleted has both left and right children, replace the deleted node with the node with the minimum value in its right subtree. If the movie is not found in the search process, print "Movie not found." and do not attempt to delete. A movie node should also be deleted when the quantity goes to 0 for any movie. Be sure to test your program for movie nodes with 0 children, 1 child, or2 children! 2. Count movies in the tree. When the user selects this option, your program should traverse the tree in any order, count the total number of movie nodes in the tree, and print the count. 3. Delete the tree in the destructor using a postorder traversal When the user selects quit, the destructor for the MovieTree class should be called. In the destructor, all of the nodes in the tree should be deleted You need to use a postorder tree traversal for the delete or you will get segmentation fault errors. You may implement a helper function.Explanation / Answer
Implemented the all the 3 tasks mentioned in the question. Had to modify the header file to include helper functions. Let me know if any issues running the program, will help. If the answer helped, please don't forget to rate it. Thank you.
Since the countMovies() is of void return type, it does not return the count, but simply prints it.
MovieTree.hpp
#ifndef MOVIETREE_HPP
#define MOVIETREE_HPP
#include <string>
struct MovieNode
{
int ranking;
std::string title;
int year;
int quantity;
MovieNode *parent;
MovieNode *leftChild;
MovieNode *rightChild;
MovieNode(){};
MovieNode(int in_ranking, std::string in_title,
int in_year, int in_quantity)
{
ranking = in_ranking;
title = in_title;
year = in_year;
quantity = in_quantity;
parent = leftChild = rightChild = nullptr;
}
};
class MovieTree
{
public:
MovieTree();
~MovieTree();
void printMovieInventory();
void addMovieNode(int ranking, std::string title,
int releaseYear, int quantity);
void findMovie(std::string title);
void rentMovie(std::string title);
void deleteMovie(std::string title);
void countMovies();
private:
void postOrderDelete(MovieNode* node); //helper function to delete tree in post order
int postOrderCount(MovieNode* node); //helper function to count the nodes
MovieNode *search(MovieNode *node, std::string title);
MovieNode *root;
};
#endif // MOVIETREE_HPP
MovieTree.cpp
#include "MovieTree.hpp"
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
MovieTree::MovieTree(){
root = NULL;
}
MovieTree::~MovieTree(){
postOrderDelete(root);
}
MovieNode* MovieTree::search(MovieNode *node, string title){
node = root;
if (root == NULL){
cout << "Movie not found." << endl;
}
//node = root;
while (node != NULL){
//int tit_comp = node ->title.compare(title);
if (node && node -> title == title){
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << node -> ranking << endl;
cout << "Title:" << node -> title << endl;
cout << "Year:" << node -> year << endl;
cout << "Quantity:" << node -> quantity << endl;
break;
}
else
{
//cout << "Movie not found." << endl;
break;
}
}
return node;
}
void MovieTree::findMovie(string title){
MovieNode *foundMovie = search(root, title);
if (title < foundMovie -> title)
{
if (foundMovie -> leftChild == NULL)
{
//cout << "Movie not found." << endl;
return;
}
else {
foundMovie = foundMovie->leftChild;
}
}
else
{
if (foundMovie -> rightChild == NULL)
{
//cout << "Movie not found."<< endl;
return;
}
else
{
foundMovie = foundMovie->rightChild;
}
}
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << foundMovie -> ranking << endl;
cout << "Title:" << foundMovie -> title << endl;
cout << "Year:" << foundMovie -> year << endl;
cout << "Quantity:" << foundMovie -> quantity << endl;
}
void printMovieHelp(MovieNode *node)
{
if (node == NULL)
{
return;
}
else
{
printMovieHelp(node -> leftChild);
cout << "Movie: " << node -> title << " " << node -> quantity <<endl;
printMovieHelp(node -> rightChild);
}
}
void MovieTree::printMovieInventory()
{
if (root == NULL)
{
return;
}
else
{
printMovieHelp(root);
}
}
MovieNode *searchMovieTree(MovieNode *node, string title){
if (node -> title == title)
{
return node -> parent;
}
else if (node ->title > title)
{
if (node -> leftChild == NULL)
{
return node;
}
return searchMovieTree(node -> leftChild, title);
}
else {
if (node -> rightChild == NULL)
{
return node;
}
return searchMovieTree(node -> rightChild, title);
}
}
void addHelper( MovieNode* root, MovieNode* addNode);
void MovieTree::addMovieNode(int ranking, std::string title, int year, int quantity){
MovieNode *addNode = new MovieNode;
addNode -> ranking = ranking;
addNode -> title = title;
addNode -> year = year;
addNode -> quantity = quantity;
addNode -> leftChild = NULL;
addNode -> rightChild = NULL;
if ( root == NULL )
root = addNode;
else
addHelper( root, addNode );
//return root;
}
void addHelper( MovieNode* root, MovieNode* addNode){
//MovieNode *foundMovie = searchMovieTree(root, title);
if( addNode -> title < root -> title ){
if( root -> leftChild != NULL )
addHelper( root -> leftChild, addNode );
else
root -> leftChild = addNode;
}
else {
if( root -> rightChild != NULL )
addHelper( root -> rightChild, addNode );
else
root -> rightChild = addNode;
}
}
void MovieTree::rentMovie(string title){
MovieNode *found_Movie = root;
if (root == NULL){
cout << "Movie not found." << endl;
return;
}
found_Movie = root;
while (found_Movie != NULL){
int tit_comp = found_Movie -> title.compare(title);
if (tit_comp > 0){
found_Movie = found_Movie -> leftChild;
}
else if (tit_comp < 0){
found_Movie = found_Movie -> rightChild;
}
else {
//found_Movie = root;
if (found_Movie -> quantity > 0)
{
found_Movie -> quantity--;
cout << "Movie has been rented." << endl;
cout << "Movie Info:" << endl;
cout << "===========" << endl;
cout << "Ranking:" << found_Movie -> ranking << endl;
cout << "Title:" << found_Movie -> title << endl;
cout << "Year:" << found_Movie -> year << endl;
cout << "Quantity:" << found_Movie -> quantity << endl;
//break;
return;
}
else if (found_Movie -> quantity == 0){
cout << "Movie out of stock." << endl;
return;
//break;
}
}
}
if (found_Movie && found_Movie -> title == title){
return;
}
else
{
cout << "Movie not found." << endl;
return;
}
}
void MovieTree::postOrderDelete(MovieNode* node)
{
if(node == nullptr) return;
postOrderDelete(node->leftChild);
postOrderDelete(node->rightChild);
delete node;
root = nullptr;
}
void MovieTree::deleteMovie(std::string title)
{
//locate the node to be deleted
MovieNode * curr = root;
while(curr != nullptr)
{
if(curr->title == title)
break;
else if(title < curr->title )
curr = curr->leftChild;
else
curr = curr->rightChild;
}
if(curr == nullptr)
{
cout << "Movie " << title << " not found " << endl;
return;
}
//delete leaf node
if(curr->leftChild== NULL && curr->rightChild == NULL)
{
if(curr == root)
root = NULL;
else
{
if(curr->parent->leftChild== curr) //is curr the left child of its parent
curr->parent->leftChild= NULL;
else
curr->parent->rightChild = NULL;
}
delete curr;
}
else if(curr->leftChild== NULL && curr->rightChild != NULL) //delete node with only right child
{
if(curr == root)
root = curr->rightChild;
else
{
if(curr->parent->leftChild== curr)//is curr the left child of its parent
curr->parent->leftChild= curr->rightChild;
else
curr->parent->rightChild = curr->rightChild;
}
curr->rightChild->parent = curr->parent;
delete curr;
}
else if(curr->leftChild!= NULL && curr->rightChild == NULL) //delete node with only left child
{
if(curr == root)
root = curr->leftChild;
else
{
if(curr->parent->leftChild== curr)//is curr the left child of its parent
curr->parent->leftChild= curr->leftChild;
else
curr->parent->rightChild = curr->leftChild;
}
curr->leftChild->parent = curr->parent;
delete curr;
}
else //delete node with both children
{
//find successor in right subtree
MovieNode* succ = curr->rightChild;
while(succ->leftChild != nullptr)
succ = succ->leftChild;
MovieNode copy = *succ; //save successor's value
deleteMovie(succ->title);//delete successor
//copy over saved values
curr->ranking = copy.ranking;
curr->title = copy.title;
curr->year = copy.year;
curr->quantity = copy.quantity;
}
}
void MovieTree::countMovies()
{
cout << "Number of movies : " << postOrderCount(root) << endl;
}
int MovieTree::postOrderCount(MovieNode* node)
{
if(node == nullptr)
return 0;
else
return postOrderCount(node->leftChild) + postOrderCount(node->rightChild) + 1;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.