DO NOT USE any of the STL (including the stack and queue type) in your code. Binary Search Tree (BST) For this PA, you will be implementing a BST using a linked representation to store the top songs on Billboard 2020. The class should be named SongBST, and the class structure should match the tree class structure covered in lectures. TreeNode with an array TreeNode will hold information about each song including the dates it appeared on the Billboard chart. These dates will be stored in a static array dotes, and frequency indicates how many times the song appeared on the chart in 2020. struct TreeNode string title; //used as key string artist; string dates (52); //filled starting from index o int frequency: // should match # of elements in dates TreeNoder left; TreeNode* right; }; Reading in Songs The list of songs to add to the tree will be in top1.csv. Discard the first line of the file in the driver, then read in each song similarly to how you read in Orders for PA 1. Pass all the information to the SongBST insert function to add each song to the tree. The nodes in the tree should be ordered by song title. BST Functions Implement all basic class functions (default constructor, copy constructor, destructor, copy assignment) and basic tree functions: void insert(string title, string artist, string date): creates and adds a TreeNode to the tree. Set the first index of dates to the date that is passed in. If the song is already in the tree, update frequency and dates accordingly. You can assume that two songs won't have the same title. bool remove(string title): returns false if the song is not in the tree. Implement the following functions: 1.print(): prints the title and frequency of all the songs in the tree using an inorder traversal. 2.printSong(string title): finds and prints all the information about the song. See execution example for the print format. 3. int topSong(): returns the maximum number of times a single song appeared on the chart (i.e. highest frequency in the tree) using recursion. Testing and submission Provide a driver/client program to demonstrate your functions. Test ALL the functions of your class thoroughly in the driver, including all the edge cases. Submit your program using the following command: /home/fac/hkong/submit/cpsc2430/submit_pa3 The SongBST class should be in two files named songbst.h and songbst.cpp. The driver should be in a file named pa3.cpp. Execution example [pa3]./pa3 Hello! Processing the topl.csv file. Printing tree: All I Want For Christmas Is You x 3 Blinding Lights x 4 Cardigan x 1 Circles x 1 Dynamite x 3 Franchise x 1 Life Goes On x 1 Mood x 6 Positions x 1 Rain On Me x 1 Rockstar x7 Savage x 1 Savage Love (Laxed Siren Beat) x 1 Say So x 1 Stuck With U x 1 The Box X 11 The Scotts x 1 Toosie Slide x 1 Trollz x 1 WAP X 4 Watermelon Sugar x 1 Which song do you want to print? All I Want For Christmas Is You Title: All I Want For Christmas Is You Artist: Mariah Carey Appeared on the Billboard chart 3 times on: 2020-01-04 2020-01-11 2020-12-26 Which song do you want to remove? The Box The Box has been removed. Printing updated tree: All I Want For Christmas Is You x 3 Blinding Lights x 4 Cardigan x 1 Circles x 1 Dynamite x 3 Franchise x 1 Life Goes On x 1 Mood x 6 Positions x 1 Rain On Me x 1 Rockstar x 7 Savage x 1 Savage Love (Laxed - Siren Beat) x 1 Say So x 1 Stuck With U x 1 The Scotts x 1 Toosie Slide x 1 Trollz x 1 WAP X 4 Watermelon Sugar x 1 The top song appeared 7 times on Billboard 100. DO NOT USE any of the STL (including the stack and queue type) in your code. Binary Search Tree (BST) For this PA, you will be implementing a BST using a linked representation to store the top songs on Billboard 2020. The class should be named SongBST, and the class structure should match the tree class structure covered in lectures. TreeNode with an array TreeNode will hold information about each song including the dates it appeared on the Billboard chart. These dates will be stored in a static array dotes, and frequency indicates how many times the song appeared on the chart in 2020. struct TreeNode string title; //used as key string artist; string dates (52); //filled starting from index o int frequency: // should match # of elements in dates TreeNoder left; TreeNode* right; }; Reading in Songs The list of songs to add to the tree will be in top1.csv. Discard the first line of the file in the driver, then read in each song similarly to how you read in Orders for PA 1. Pass all the information to the SongBST insert function to add each song to the tree. The nodes in the tree should be ordered by song title. BST Functions Implement all basic class functions (default constructor, copy constructor, destructor, copy assignment) and basic tree functions: void insert(string title, string artist, string date): creates and adds a TreeNode to the tree. Set the first index of dates to the date that is passed in. If the song is already in the tree, update frequency and dates accordingly. You can assume that two songs won't have the same title. bool remove(string title): returns false if the song is not in the tree. Implement the following functions: 1.print(): prints the title and frequency of all the songs in the tree using an inorder traversal. 2.printSong(string title): finds and prints all the information about the song. See execution example for the print format. 3. int topSong(): returns the maximum number of times a single song appeared on the chart (i.e. highest frequency in the tree) using recursion. Testing and submission Provide a driver/client program to demonstrate your functions. Test ALL the functions of your class thoroughly in the driver, including all the edge cases. Submit your program using the following command: /home/fac/hkong/submit/cpsc2430/submit_pa3 The SongBST class should be in two files named songbst.h and songbst.cpp. The driver should be in a file named pa3.cpp. Execution example [pa3]./pa3 Hello! Processing the topl.csv file. Printing tree: All I Want For Christmas Is You x 3 Blinding Lights x 4 Cardigan x 1 Circles x 1 Dynamite x 3 Franchise x 1 Life Goes On x 1 Mood x 6 Positions x 1 Rain On Me x 1 Rockstar x7 Savage x 1 Savage Love (Laxed Siren Beat) x 1 Say So x 1 Stuck With U x 1 The Box X 11 The Scotts x 1 Toosie Slide x 1 Trollz x 1 WAP X 4 Watermelon Sugar x 1 Which song do you want to print? All I Want For Christmas Is You Title: All I Want For Christmas Is You Artist: Mariah Carey Appeared on the Billboard chart 3 times on: 2020-01-04 2020-01-11 2020-12-26 Which song do you want to remove? The Box The Box has been removed. Printing updated tree: All I Want For Christmas Is You x 3 Blinding Lights x 4 Cardigan x 1 Circles x 1 Dynamite x 3 Franchise x 1 Life Goes On x 1 Mood x 6 Positions x 1 Rain On Me x 1 Rockstar x 7 Savage x 1 Savage Love (Laxed - Siren Beat) x 1 Say So x 1 Stuck With U x 1 The Scotts x 1 Toosie Slide x 1 Trollz x 1 WAP X 4 Watermelon Sugar x 1 The top song appeared 7 times on Billboard 100
