Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Please follow all the instructions, in C + + make sure to read all the prompts and do what it says, make sure it has

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Professional Microsoft SQL Server 2014 Integration Services

Authors: Brian Knight, Devin Knight

1st Edition

1118850904, 9781118850909

More Books

Students also viewed these Databases questions