Assignment 7 - Binary Search Trees II

OBJECTIVES

    1. Delete nodes in a BST

    2. Create a super data structure combining BST and LL

Overview

This assignment builds off of the previous one conceptually, although the data structure is fundamentally different. Make sure to use the ​MovieTree.hpp​file uploaded on Moodle for assignment 7,​not ​the ​MovieTree.hpp​of the previous assignment 6. As usual, ​do not ​modify the header file. ​You may implement helper functions in your .cpp file to facilitate recursion if you want as long as you don’t add those functions to the MovieTree class​.

MovieTree Class

Your task is to implement a binary search tree of linked lists of movies.​​Disclaimer: this diabolical super data structure is not practical; it is meant to challenge you and improve your skills manipulating and traversing BST’s and LL’s.​Tree nodes will contain a letter of the alphabet and a linked list. The linked list will be an alphabetically sorted list of movies which start with that letter. For example:




MovieTree()

    • Constructor: Initialize any member variables of the class to default

~MovieTree()

    • Destructor: Free all memory that was allocated

void printMovieInventory()

    • Print every movie in the data structure in alphabetical order of titles using the following format. For TreeNode ​t​and LLMovieNode ​m​:


// for every TreeNode (t) in the tree
cout​​<<​​"Movies starting with letter: "​​<<​​t->titleChar​​<<​​endl; // for every LLMovieNode (m) attached to t

cout​​<<​​" >> "​​<<​​m->title <<​​" "​​<< m->rating <<​​endl;


Sample output format


Movies starting with letter: ​B
    • ​Bowling for Columbine 8 Movies starting with letter: ​D
    • ​Dancin' Outlaw 8.1

    • ​Dogtown and Z-Boys 7.7

    • ​Down from the Mountain 7.4


void addMovie(int ​ranking​,std::string ​title​,int ​year​,float ​rating​)
    • Add a movie to the data structure in the correct place based on its ​title​.
        ◦ If there is no tree node corresponding to the first letter of ​title​,create it and insert it in the tree in the alphabetically correct position
        ◦ Create a linked list node with ​ranking​,​title​,​year ​and​​rating​,​​and insert it in the linked list associated with the tree node associated with the first letter of ​title​.The linked list must also be in alphabetical order, such that for each ​node,


node->title < node->next->title

Hint: you can compare strings with <, >, ==, etc. ​Also, ​you may assume that no two movies have the same title

void deleteMovie(std::string ​title​)


    • Delete the linked list node that contains ​title​.If as a result of this deletion, the linked list becomes empty, delete the associated tree node. If the movie does not exist in the data structure, print the following message


cout​<< ​"Movie: " ​<< title << ​" not found, cannot delete."​<< ​endl​;

Driver

Your main function should first read information about each movie from a file and store that

information in a MovieTree object. ​The name of the file with this information should be passed in as a command-line argument.​An example file is ​Movies.csv​on Moodle. It is in the format:


<Movie 1 ranking>,<Movie 1 title>,<Movie 1 year>,<Movie 1 rating> <Movie 2 ranking>,<Movie 2 title>,<Movie 2 year>,<Movie 2 rating> Etc…

Note: For autograding’s sake, insert the nodes to the tree in the order they are read in​.​After reading in the information on each movie from the file, display a menu to the user.


cout​<< ​"======Main Menu======"​<< ​endl​; cout​<< ​"1. Print the inventory"​<< ​endl​; cout​<< ​"2. Delete a movie"​<< ​endl​; cout​<< ​"3. Quit"​<< ​endl​;

The options should have the following behavior:

    • Print the inventory: ​Call your tree’s ​printMovieInventory​​function

    • Delete a movie: ​Call your ​deleteMovie​function on a title specified by the user. Prompt the user for a movie title using the following code:


cout​<< ​"Enter a movie title:"​<< ​endl​;

    • Quit: ​Exit after printing a friendly message to the user: cout​<< ​"Goodbye!"​<< ​endl​;



"Please note that once you are done with your assignment on code runner you need to click on 'finish attempt' and the 'submit all and finish'. If you don't do this, you will not get graded."