Question

Need this in C++

Goals:

Your task is to implement a binary search tree of linked lists of movies. 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.

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;

​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

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 title:" << endl;

●Quit:​

Exit after printing a friendly message to the user:

cout << "Goodbye!" << endl;

Included Files

Movietree.hpp

/****************************************************************/
/* MovieTree Definition */
/****************************************************************/
/* LEAVE THIS FILE AS IS! DO NOT MODIFY ANYTHING! =] */
/****************************************************************/

#ifndef MOVIETREE_HPP
#define MOVIETREE_HPP

#include <string>

/* Linked List node structure that will be stored at each node in the BST*/
struct LLMovieNode
{
int ranking; // Rank of the movie
std::string title; // Title of the movie
int year; // Release year
float rating; // Movies rating
struct LLMovieNode* next; // Pointer to the next node

LLMovieNode(){} // default constructor

// Parametrized constructor
LLMovieNode(int r, std::string t, int y, float q) : ranking(r), title(t),
year(y), rating(q), next(NULL) {}
};

/* Node struct that will be stored in the MovieTree BST */

struct TreeNode
{
LLMovieNode* head = NULL; // Pointer to the head node of a LL
char titleChar; // Starting character of the titles stored in the linked list
TreeNode *parent = NULL; // Pointer to its parent node in BST
TreeNode *leftChild = NULL; // Pointer to its leftChild in BST
TreeNode *rightChild = NULL; // Pointer to its rightChild in BST
};

/* Class for storing and manipulating the TreeNode's of BST*/

class MovieTree
{
public:
// Check writeup for detailed function descriptions
MovieTree();
~MovieTree();
void printMovieInventory();
void addMovie(int ranking, std::string title, int year, float rating);
void deleteMovie(std::string title);

private:
TreeNode *root;
};

#endif

Answer 1

Complete Program:

File: Movietree.hpp

/****************************************************************/
/* MovieTree Definition */
/****************************************************************/
/* LEAVE THIS FILE AS IS! DO NOT MODIFY ANYTHING! =] */
/****************************************************************/

#ifndef MOVIETREE_HPP
#define MOVIETREE_HPP

#include <string>

/* Linked List node structure that will be stored at each node in the BST*/
struct LLMovieNode
{
   int ranking; // Rank of the movie
   std::string title; // Title of the movie
   int year; // Release year
   float rating; // Movies rating
   struct LLMovieNode* next; // Pointer to the next node

   LLMovieNode() {} // default constructor

                   // Parametrized constructor
   LLMovieNode(int r, std::string t, int y, float q) : ranking(r), title(t),
       year(y), rating(q), next(NULL) {}
};

/* Node struct that will be stored in the MovieTree BST */
struct TreeNode
{
   LLMovieNode* head = NULL; // Pointer to the head node of a LL
   char titleChar; // Starting character of the titles stored in the linked list
   TreeNode *parent = NULL; // Pointer to its parent node in BST
   TreeNode *leftChild = NULL; // Pointer to its leftChild in BST
   TreeNode *rightChild = NULL; // Pointer to its rightChild in BST
};

/* Class for storing and manipulating the TreeNode's of BST*/
class MovieTree
{
public:
   // Check writeup for detailed function descriptions
   MovieTree();
   ~MovieTree();
   void printMovieInventory();
   void addMovie(int ranking, std::string title, int year, float rating);
   void deleteMovie(std::string title);

private:
   TreeNode *root;
};
#endif

File: Movietree.cpp

// Header files section
#include "Movietree.hpp"
#include <iostream>

// default constructor implementaion
MovieTree::MovieTree()
{
   root = NULL;
} // end of constructor

// destroyTree function implementation
void destroyTree(TreeNode* t)
{
   if (t)
   {
       destroyTree(t->leftChild);
       destroyTree(t->rightChild);
       delete t;
   }
} // end of destroyTree function

// destructor implementaion
MovieTree::~MovieTree()
{
   destroyTree(root);
} // end of destructor

// printMovieInventoryHelper function implementation
void printMovieInventoryHelper(TreeNode* t)
{
   if (t != NULL)
   {
       printMovieInventoryHelper(t->leftChild);

       std::cout << "Movies starting with letter: " << t->titleChar << std::endl;
       LLMovieNode* m = t->head;
       while (m != NULL)
       {
           std::cout << " >> " << m->title << " " << m->rating << std::endl;
           m = m->next;
       }

       printMovieInventoryHelper(t->rightChild);
   }
} // end of printMovieInventoryHelper function

// printMovieInventory function implementation
void MovieTree::printMovieInventory()
{
   printMovieInventoryHelper(root);
} // end of printMovieInventory function

// addMovieHelper function implementation
TreeNode* addMovieHelper(TreeNode* &t, TreeNode* newNode)
{
   if (t == NULL)
   {
       return newNode;
   }

   if (newNode->titleChar < t->titleChar)
   {
       TreeNode* leftNode = addMovieHelper(t->leftChild, newNode);
       t->leftChild = leftNode;
       leftNode->parent = t;
   }
   else if (newNode->titleChar > t->titleChar)
   {
       TreeNode* rightNode = addMovieHelper(t->rightChild, newNode);
       t->rightChild = rightNode;
       rightNode->parent = t;
   }
   else if (newNode->titleChar == t->titleChar)
   {
       LLMovieNode* nodeToInsert = newNode->head;
       LLMovieNode* curr = t->head;
       LLMovieNode* prev = NULL;
       while (curr != NULL && curr->title.compare(nodeToInsert->title) < 0)
       {
           prev = curr;
           curr = curr->next;
       }

       if (curr != NULL && curr->title.compare(nodeToInsert->title) == 0)
       {
           return t; // duplicate title
       }
       else
       {
           if (prev == NULL)
           {
               nodeToInsert->next = t->head;
               t->head = nodeToInsert;
           }
           else if (curr == NULL)
           {
               prev->next = nodeToInsert;
           }
           else
           {
               prev->next = nodeToInsert;
               nodeToInsert->next = curr;
           }
       }
   }

   return t;
} // end of addMovieHelper function

// addMovie function implementation
void MovieTree::addMovie(int ranking, std::string title, int year, float rating)
{
   LLMovieNode* m = new LLMovieNode(ranking, title, year, rating);

   TreeNode* newNode = new TreeNode;
   newNode->titleChar = title.at(0);
   newNode->head = m;
   newNode->leftChild = NULL;
   newNode->rightChild = NULL;
   newNode->parent = NULL;

   root = addMovieHelper(root, newNode);
} // end of addMovie function

// deleteMovieHelper function implementation
TreeNode* deleteMovieHelper(TreeNode* t, std::string title)
{
   // base case
   if (t == NULL)
   {
       std::cout << "Movie: " << title << " not found, cannot delete." << std::endl;
       return t;
   }

   if (title.at(0) < t->titleChar)
   {
       t->leftChild = deleteMovieHelper(t->leftChild, title);
   }
   else if (title.at(0) > t->titleChar)
   {
       t->rightChild = deleteMovieHelper(t->rightChild, title);
   }
   else if (title.at(0) == t->titleChar)
   {
       LLMovieNode* currNode = t->head;
       LLMovieNode* prevNode = NULL;

       while (currNode != NULL && currNode->title.compare(title) != 0)
       {
           prevNode = currNode;
           currNode = currNode->next;
       }

       if (currNode == NULL)
       {
           std::cout << "Movie: " << title << " not found, cannot delete." << std::endl;
           return t;
       }

       if (prevNode == NULL && t->head->next != NULL)
       {
           t->head = t->head->next;          
           return t;
       }

       if (prevNode != NULL && currNode != NULL)
       {
           prevNode->next = currNode->next;          
           return t;
       }

       if (t->leftChild == NULL && t->rightChild == NULL)
       {
           delete t;
           t = NULL;
       }
       else if (t->leftChild == NULL)
       {
           TreeNode *tempNode = t;
           t->rightChild->parent = t->parent;
           t = t->rightChild;          
           delete tempNode;
       }
       else if (t->rightChild == NULL)
       {
           TreeNode *tempNode = t;
           t->leftChild->parent = t->parent;
           t = t->leftChild;          
           delete tempNode;
       }
       else
       {
           TreeNode* minValueNode = t->rightChild;
           while (minValueNode->leftChild != NULL)
           {
               minValueNode = minValueNode->leftChild;
           }
           t->head = minValueNode->head;
           t->titleChar = minValueNode->titleChar;
           t->rightChild = deleteMovieHelper(t->rightChild, minValueNode->head->title);
       }
   }

   return t;
} // end of deleteMovieHelper function

// deleteMovie function implementation
void MovieTree::deleteMovie(std::string title)
{
   root = deleteMovieHelper(root, title);
} // end of deleteMovie function

File: main.cpp

// Header files section
#include "Movietree.hpp"
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>

// start main function
int main(int argc, char* argv[])
{
   if (argc < 2)
   {
       std::cout << "The comma separated movies file should be passed in as a command-line argument." << std::endl;
       std::cout << std::endl << std::endl;
       system("pause");
       return 1;
   }

   std::ifstream infile;
   infile.open(argv[1]);
   if (!infile)
   {
       std::cout << argv[1] << " file cannot be opened!" << std::endl;
       system("pause");
       return 1;
   }

   MovieTree tree;
   std::string line;
   std::string tempStr;
   int ranking = 0;
   std::string title = "";
   int year = 0;
   float rating = 0;
   int option;

   std::getline(infile, line);
   while (infile)
   {
       if (line.compare("") != 0)
       {
           std::stringstream ss(line);
           if (getline(ss, tempStr, ','))
               ranking = stoi(tempStr);
           if (getline(ss, tempStr, ','))
               title = tempStr;
           if (getline(ss, tempStr, ','))
               year = stoi(tempStr);
           if (getline(ss, tempStr, ','))
               rating = stof(tempStr);

           tree.addMovie(ranking, title, year, rating);
       }

       getline(infile, line);
   }
   infile.close();

   do
   {
       std::cout << "======Main Menu======" << std::endl;
       std::cout << "1. Print the inventory" << std::endl;
       std::cout << "2. Delete a movie" << std::endl;
       std::cout << "3. Quit" << std::endl;
       std::cout << "Enter your option:" << std::endl;
       std::cin >> option;
       std::getline(std::cin, tempStr); // read remaining line

       switch (option)
       {
       case 1:
           tree.printMovieInventory();
           break;

       case 2:
           std::cout << "Enter title:" << std::endl;
           std::getline(std::cin, title);

           tree.deleteMovie(title);
           break;

       case 3:
           std::cout << "Goodbye!" << std::endl;
           break;

       default:
           std::cout << "Invalid option!" << std::endl;
       }
       std::cout << std::endl;
   } while (option != 3);

   std::cout << std::endl << std::endl;
   system("pause");
   return 0;
} // end of main function

Input file: Movies.csv

Output on Console: