Binary Search Trees An online movie service needs help keeping track of their st
ID: 3862078 • Letter: B
Question
Binary Search Trees
An online movie service needs help keeping track of their stock. You should help
them by developing a program that stores the movies in a Binary Search Tree (BST)
ordered by movie title. For each of the movies in the store’s inventory, the following
information is kept:
- IMDB ranking
- Title
- Year released
- Quantity in stock
Your program will have a menu similar to previous assignments from which the
user could select options. In this assignment, your menu needs to include options for
finding a movie, renting a movie, printing the inventory, deleting a movie, and
quitting the program.
Your program needs to incorporate the following functionality. These are not menu
options, see Appendix A for the specific menu options.
Insert all the movies in the tree.
When the user starts the program they will pass it the name of the text file
that contains all movie information. Each line in the file shows the IMDB
ranking, title, year released, and quantity in stock. Your program needs to
handle that command line argument, open the file, and read all movie data in
the file. From this data, build the BST ordered by movie title. All other
information about the movie should also be included in the node for that
movie in the tree. Note: the data should be added to the tree in the order it
is read in. The name of the file that contains the movie data is
Assignment8Movies.txt.:
Find a movie.
When the user selects this option from the menu, they should be prompted
for the name of the movie. Your program should then search the tree and
display all information for that movie. If the movie is not found in the tree,
your program should display, “Movie not found.”
Rent a movie.
When the user selects this option from the menu, they should be prompted
for the name of the movie. If the movie is found in the tree, your program
should update the Quantity in stock property of the movie and display the
new information about the movie. If the movie is not found, your program
should display, “Movie not found.” When the quantity reaches 0, the movie
should be deleted from the tree.
Print the entire inventory.
When the user selects this option from the menu, your program should
display all movie titles and the quantity available in sorted order by title. See
the lecture notes and recitation exercises on in-order tree traversal for more
information.
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, delete
it if it’s found, re-assign to the parent and child pointers to bypass the deleted
node, and free the memory assigned to the node. 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 its quantity goes to 0.
Count movies in the tree.
When the user selects this option, your program should traverse the tree in
any order and count the total movie nodes in the tree and print the count.
Quit the program.
When the user selects this option, your program should delete the nodes in
the tree and exit the program.
When the user selects quit, the destructor for the MovieTree class should be
called and 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.
Use the cout statements in Appendix A to set the order of the menu options.
Implementation details
Your BST should be implemented in a class. You are provided with a MovieTree.h
file on Moodle that includes the class prototype for this assignment. You need to
implement the class functionality in a corresponding MovieTree.cpp file and
Assignment8.cpp file. To submit your work, zip all files together and submit them to
COG. If you do not get your assignment working on COG, you will have the option of
a grading interview.
Appendix A – cout statements that COG expects
Display menu
cout << "======Main Menu======" << endl;
cout << "1. Find a movie" << endl;
cout << "2. Rent a movie" << endl;
cout << "3. Print the inventory" << endl;
cout << "4. Delete a movie" << endl;
cout << "5. Count the movies" << endl;
cout << "6. Quit" << endl;
Find a movie
cout << "Enter title:" << endl;
Display found movie information
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;
If movie not found
cout << "Movie not found." << endl;
Rent a movie
//If movie is in stock
cout << "Movie has been rented." << endl;
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;
//If movie not found in tree
cout << "Movie not found." << endl;
Print the inventory
//For all movies in tree
cout<<"Movie: "<title<<" "<quantity< Count movies in the tree
cout<<"Tree contains: "<<mt.countMovieNodes()<<" movies."
<< endl;
Delete movie
cout << "Enter title:" << endl;
//If movie not found in tree
cout << "Movie not found." << endl;
Delete all nodes in the tree
//For all movies in tree
cout<<"Deleting: "<<node->title<<endl;
Quit
cout << "Goodbye!" << endl;
This is MovieTree.h:
Explanation / Answer
There are mainly 3 steps which you need to do. Just follow below steps :
1) You need a main function which will be showing the menus and taking inputs from the user and based on the user's input it will show the result.
2) As yo already have the header file "MovieTree.h", so i believe ou don't require this. Hence, I have directly called into my main function and used their prededfined objects.
3) I am assuming that you have saved the list of movie list and its detail into a file name called "Assignment8Movies.txt" so I am using this file into my program directly.
Note : Before executing this whole program, please keep all the required files(main.cpp,Functions page and Assignmnet8Movies.txt) into same folder and "MovieTree.h" into the header file library folder.
main.cpp:
#include <iostream>
#include <fstream>
#include "MovieTree.h"
using namespace std;
int main()
{
//declarations
char *fileName; //stores the file we will be opening
int input; //takes a number from the main menu
string t; //used for cin of a movie title in if statement 1
bool is_running = true; //keeps the while loop running and if set to false shuts down the program
//opening a file
fileName = "Assignment8Movies.txt"; //argv[1];
ifstream myFile;
myFile.open(fileName);
MovieTree *tree = new MovieTree;
//opening and reading the file
if (myFile.is_open());
{
while (!myFile.eof())
{
string ranking;
getline(myFile,ranking,',');
int rankig = stoi(ranking);
string title;
getline(myFile,title,',');
string year;
getline(myFile, year, ',');
int yearInt = stoi(year);
string quantity;
getline(myFile,quantity);
int quanInt = stoi(quantity);
tree -> addMovieNode(rankig, title, yearInt, quanInt);
//cout<<rankig<< title << yearInt<< quantity; //FOR TESTING PURPOSES
}
}
while(is_running == true)
{
//Main Menu
cout << "======Main Menu=====" << endl;
cout << "1. Find a movie" << endl;
cout << "2. Rent a movie" << endl;
cout << "3. Print the inventory" << endl;
cout << "4. Delete a movie" << endl;
cout << "5. Count the movies" << endl;
cout << "4. Quit" << endl;
cin >> input;
if(input == 1)
{
std::cout<<"Enter title:"<<std::endl;
getline(std::cin, t);
tree->findMovie(t);
}
if(input == 2)
{
std::cout<<"Enter title:"<<std::endl;
getline(std::cin, t);
tree->rentMovie(t);
}
if(input == 3)
{
tree->printMovieInventory(tree->getRoot());
}
if(input == 4)
{
std::cout<<"Goodbye!"<<std::endl;
is_running = false;
}
}
myFile.close();
return 0;
}
Function :
#include <string>
#include "MovieTree.h"
MovieTree::MovieTree()
{
//ctor
}
MovieTree::~MovieTree()
{
//dtor
}
MovieNode* MovieTree::getRoot()
{
return root;
}
void MovieTree::addMovieNode(int ranking, std::string title, int in_year, int in_quantity)
{
if(root == NULL)
{
root = new MovieNode(ranking, title, in_year, in_quantity);
}
else
{
MovieNode *temp = root;
while(true)
{
if(temp->title.compare(title) > 0)
{
if(temp->leftChild != NULL)
{
temp = temp->leftChild;
}
else
{
temp->leftChild = new MovieNode(ranking, title, in_year, in_quantity);
break;
}
}
else
{
if(temp->rightChild != NULL)
{
temp = temp->rightChild;
}
else
{
temp->rightChild = new MovieNode(ranking, title, in_year, in_quantity);
break;
}
}
}
}
}
void MovieTree::findMovie(std::string title)
{
if(searchMovieTree(root,title) == NULL)
{
std::cout<<"Movie not found."<<std::endl;
}
else
{
std::cout<<"Movie Info:"<<std::endl;
std::cout<<"==========="<<std::endl;
std::cout<<"Ranking:"<<searchMovieTree(root,title)->ranking<<std::endl;
std::cout<<"Title:"<<searchMovieTree(root,title)->title<<std::endl;
std::cout<<"Year:"<<searchMovieTree(root,title)->year<<std::endl;
std::cout<<"Quantity:"<<searchMovieTree(root,title)->quantity<<std::endl;
}
}
void MovieTree::rentMovie(std::string title)
{
if(searchMovieTree(root,title)->quantity == 0)
{
std::cout<<"Movie out of stock."<<std::endl;
}
else
{
std::cout<<"Movie has been rented."<<std::endl;
searchMovieTree(root,title)->quantity--;
findMovie(title);
}
}
MovieNode* MovieTree::searchMovieTree(MovieNode *node, std::string title)
{
node = root;
while(true)
{
if(node->title.compare(title)==0)
{
return node;
}
if(node->title.compare(title) > 0)
{
if(node->leftChild != NULL)
{
node = node->leftChild;
}
else
{
return NULL;
break;
}
}
else
{
if(node->rightChild != NULL)
{
node = node->rightChild;
}
else
{
return NULL;
break;
}
}
}
}
void MovieTree::printMovieInventory(MovieNode *m)
{
if(m->leftChild != NULL)
{
printMovieInventory(m->leftChild);
}
std::cout<<"Movie: "<<m->title<<' ';
if(m->rightChild != NULL)
{
printMovieInventory(m->rightChild);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.