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 stores 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.:

1,Shawshank Redemption,1994,45 2,The Godfather,1972,34 3,The Godfather: Part II,1974,12 4,The Dark Knight,2008,90 5,Pulp Fiction,1994,34 6,12 Angry Men,1957,56 7,Schindler's List,1993,10 8,The Good the Bad and the Ugly,1966,2 9,The Lord of the Rings: The Return of the King,2003,4 10,Fight Club,1999,6 11,The Lord of the Rings: The Fellowship of the Ring,2001,20 12,Star Wars: Episode V - The Empire Strikes Back,1980,12 13,Forrest Gump,1994,1 14,Inception,2010,10 15,One Flew Over the Cuckoo's Nest,1975,10 16,The Lord of the Rings: The Two Towers,2002,5 17,Goodfellas,1990,5 18,The Matrix,1999,5 19,Star Wars: Episode IV - A New Hope,1977,6 20,Seven Samurai,1954,7 21,Interstellar,2014,8 22,City of God,2002,9 23,Se7en,1995,11 24,The Usual Suspects,1995,2 25,The Silence of the Lambs,1991,19 26,It's a Wonderful Life,1946,21 27,Once Upon a Time in the West,1968,12 28,Leon: The Professional,1994,31 29,Life Is Beautiful,1997,3 30,Casablanca,1942,5 31,Raiders of the Lost Ark,1981,6 32,American History X,1998,1 33,Saving Private Ryan,1998,3 34,City Lights,1931,10 35,Spirited Away,2001,10 36,Psycho,1960,6 37,Rear Window,1954,7 38,Whiplash,2014,8 39,The Untouchables,2011,3 40,Modern Times,1936,9 41,Terminator 2: Judgment Day,1991,10 42,Memento,2000,9 43,The Green Mile,1999,8 44,The Pianist,2002,7 45,The Departed,2006,7 46,Apocalypse Now,1979,5 47,Sunset Blvd.,1950,5 48,Gladiator,2000,5 49,Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb,1964,5 50,Back to the Future,1985,5 

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 its 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: "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: "<title<Quit cout << "Goodbye!" << endl;

This is MovieTree.h:

#ifndef MOVIETREE_H #define MOVIETREE_H #include  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 = NULL; leftChild = NULL; rightChild = NULL; } }; class MovieTree { public: MovieTree(); ~MovieTree(); void printMovieInventory(); int countMovieNodes(); void deleteMovieNode(std::string title); void addMovieNode(int ranking, std::string title, int releaseYear, int quantity); void findMovie(std::string title); void rentMovie(std::string title); protected: private: void DeleteAll(MovieNode * node); //use this for the post-order traversal deletion of the tree void printMovieInventory(MovieNode * node); void countMovieNodes(MovieNode *node, int *c); MovieNode* search(std::string title); MovieNode* searchRecursive(MovieNode *node, std::string value); MovieNode* treeMinimum(MovieNode *node); MovieNode *root; }; #endif // MOVIETREE_H