Please follow all the instructions, in C$++$make sure to read all the prompts and do what it says, make sure it has everything the $.$h fiels and $.$cpp because i have to put it on a linux server using vim, just please make sure it follows the instructions this is really important

The goal of this program is to create a binary search tree $($BST$)$ and to implement the BST algorithms recursively.

In Programming Assignment $4$ we will experience all of these characteristics. Instead of using a hash table, we will use close to the same data as Programming Assignment $3$ but this time with a binary search tree.

Specifics

In Programming Assignment $4$ we will use a BST to search for a website. You will be basing this program off of the same data as in Programming Assignment $3$ but now using a DIFFERENT data structure! We are moving away from hash tables and learning about BSTs$.$

Part I: BST ADT

The binary search tree should be a non$-$linear implementation $($using left and right pointers$).$ Each item in our tree will have the following information $($at a minimum$),$ which should be stored as a struct or a class:

Topic name $($e$.$g$.,$Data Structures$)$

New: keyword that is part of the website address that can be used for sorting$/$searching $($e$.$g$.,$ Carrano$-$Data$-$Abstraction$).$ You can create the keyword yourself.

Website address

Summary of what you can find at this address $($e$.$g$.,$The classic, best$-$selling Data Abstraction and Problem Solving with C$++$: Walls and Mirrors book provides a firm foundation in data structures$)$

Review $($e$.$g$.,$ your thoughts about how helpful this site is$)$

Rating $(1-5$ stars $1$ being not very useful, $5$ being very useful$)$

The ADT operations that must be performed on this data are:

Constructor $$ initialize all data members

Destructor $$ deallocate $($release$)$ all dynamic memory and reset the data members to their zero equivalent value; this should call a recursive function that performs postorder traversal $($recursively$)$ to deallocate all data and nodes.

Insert a new website based on the keyword in the website address. For example, in the above it would be: Carrano$-$Data$-$Abstraction

Remove all matches to a topic name

Remove a particular website based on keyword $($only one match$)$

Retrieve the information about a particular website $($based on its keyword$)$ a$.$ Remember, retrieve is NOT a display function and should supply the matching information back to the calling routine through the argument list

Display all websites $($sorted alphabetically by keyword!$).$

Monitor the height of the tree. Evaluate the performance of storing and retrieving items from this tree. Monitor the height of the tree and determine how that relates to the number of items. If the number of items is $100$ and the height is $90,$ we know that we do not have a relatively balanced tree!! Use the information from the Carrano reading to assist in determining if we have a reasonable tree, or not. Your efficiency write$-$up must discuss what you have discovered.

Part II: The Driver or the Test Program

The test program needs to first load the test data set from external file at the beginning of the program.

The test program needs to test all the functionalities of the tree ADT.

The menu$-$based user interface should allow user to use$/$test ALL the functionalities of the program. Try to make the user interface easier to use.

Always prompt user when you need input data.

The prompt needs to be meaningful. Example works great. E$.$g$.$Enter the rating $($e$.$g $1-5)$: $$

When asking user to choose some existing data, index works great. You can display the data with index preceding each one first.

Do not use statically allocated arrays in your classes or structures. All memory must be dynamically allocated and kept to a minimum!

All data members in a class must be private

Never perform input operations from your data structure class in

Global variables are not allowed in

Do not use the String class! $($use arrays of characters instead and the cstring library!$)$

Use modular design, separating the $.$h files from the $.$cpp files. Remember, $.$h files should contain the class header and any necessary prototypes. The $.$cpp files should contain function definitions. You must have at least $1.$h file and $2.$cpp files. Never $"$#include" $.$cpp files!

Use the iostream library for all I$/$O; do not use stdio.h$.$

Make sure to define a constructor and destructor for your class. Your destructor must deallocate all dynamically allocated memory.

NEVER use global variables in these programs!

Avoid the use of exit, continue, or break to alter the flow of control of loops

Avoid using while$(1)$ type of loop control

NEVER use the string class $$ instead use arrays of characters

Abstract Data Types should NEVER prompt the user or read information in$.$ All information should be passed from the client program or application

Abstract Data Types should NEVER display error messages but instead supply success$/$fail information back to the calling routine.