Answered step by step
Verified Expert Solution
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 Cmake 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 we will experience all of these characteristics. Instead of using a hash table, we will use close to the same data as Programming Assignment but this time with a binary search tree.
Specifics
In Programming Assignment 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 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 nonlinear 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 egData Structures
New: keyword that is part of the website address that can be used for sortingsearching eg CarranoDataAbstraction You can create the keyword yourself.
Website address
Summary of what you can find at this address egThe classic, bestselling Data Abstraction and Problem Solving with C: Walls and Mirrors book provides a firm foundation in data structures
Review eg your thoughts about how helpful this site is
Rating stars being not very useful, 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: CarranoDataAbstraction
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 and the height is 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 writeup 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 menubased user interface should allow user to usetest 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. EgEnter the rating eg :
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 h file and cpp files. Never #include" cpp files!
Use the iostream library for all IO; 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 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 successfail information back to the calling routine.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started