QuestionQuestion

Description
In this lab you will be implementing a custom binary search tree class. In your custom binary search tree class we will be separating the value that the tree stores, from the key (index) over which the tree is sorted.

Getting Started with git
This assignment assumes basic fluency with git, and the use of github.com, so (whether you turned it in on time or not for credit) I would recommend immediately completing the version control software engineering toolkit assignment.

Please start by:

Creating a new repository on your machine and pushing to github.com (follow the instructions on the github.com repo I provide under (...or create a new repository on the command line). The steps are basically what we outlined in the start of the tools assignment for git.
Creating, committing, and pushing files that will form the skeleton for your project. At minimum this would be:
main.cpp,
binary_search_tree.cpp/.h,
Makefile,
test.dat,
and a README.
Getting to work!

Example
In order to consider separating the tree's key from its data, consider the following tree example (we will use a string as the key value and store an integer value as data. A node for the tree will resemble the following:

class Node {
private:
    Node *left, *right;
    std::string key;
    int data;
    ...
public:
    Node(std::string key);
    ...
};
      
Remember to use proper access control--any methods that comprise your interface should be public. In general, helper methods should be private.
At the start, our tree is simply a null pointer. Now, suppose we wish to store the following (somewhat arbitrary) values in order:

a key of "the" with a value of 5,
a key of "best" with a value of 2,
a key of "of" with a value of 4, and
a key of "times" with a value of 7.

What we have described here is essentially a custom-built tree implementation of a map/dictionary type (you can see the C++ example of the map container, however you aren't allowed to use this in your assignment). By overloading the bracket operator (bonus) we will provide the user with array-like access to our structure (i.e., map["string"] = value;).

What you must implement
At minimum, you must implement a node class and a binary search tree class. Your BST class must have (at minimum) the following public member functions:

A class constructor.
A class destructor
set - takes a string and an integer as parameters and stores the pair in the BST, overwriting the current value if it is already in the tree.
find - takes an string parameter, and returns the value is already in the BST (you can define the behavior when the tuple isn't already in the tree).
print - prints the contents of the BST in order to the user as (key, value) pairs.
min - finds and prints the smallest (leftmost) key in the tree.
max - finds and prints the largest (rightmost) key in the tree.
save_file - takes the name of a file as a parameter, and stores the contents of the tree in order in the file.
delete - takes a string parameter, and removes the first instance of that value from the BST. You can find approximate pseudocode for delete here.

¡¡¡Bonus!!! If you get all of the above implemented, overload operator[] to provide an array-like interface for your class. The operator[] should take a string (the key) as its parameter and should return a reference to the integer value. This will allow us to do things like:
tree["word"]++;             // Increment the value at position "word"
tree["another word"] = 15; // Set the value at position "another word" to be 15
      
Modify your program to work with this new interface (note that you will have to define two versions of operator[] for both accessing and mutating).
Driver/testing your program
Implemented as an associative array your binary search tree class would be immediately useful for doing simple analysis of bodies of text. In order to test your program you should create a menu-based interface that allows the user the ability to manually test all of the functionality of your data structure.

Your menu should also give the user the ability to read text data from an arbitrary file. When it does, your program should increment in the binary tree the value stored for each word every time it is seen. After the program is done, your tree should store the total number of times that each word of the file was seen. Your program should only store words without whitespace and should filter out punctuation and other symbols (I'm leaving the definition of a word up to you--it would be reasonable to consider "o'clock" a word). As a test for your program's reading functionality, you can find the text for Arthur Conan Doyle's The Adventures of Sherlock Holmes.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#ifndef HEAP_H
#define HEAP_H

#include <cstdlib>
#include <vector>
using namespace std;

const unsigned int MAX_HEAP_SIZE = 99999;
template<class T>
class heap {
private:
    std::vector<T> buffer;
    int hsize;
public:
    heap();
    int size();
    bool isEmpty();
    void insert(T value);
    void remove_max();
    T max();
    void print();
    void heapRebuild(int root);
};

template< class T >
heap<T>::heap(){
// set heap size
    hsize = 0;
    // set max size of the vector
    buffer.resize(MAX_HEAP_SIZE);
}...
$63.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats