In this assignment, you will be implementing a 2-3 tree to handle the database for a provider of streaming movies. Nodes will store the titles of the movies. The title will be stored as a string and titles may consist of multiple words. Include AT LEAST the following functions for your 2-3 tree. For each operation I have included the function prototype that you must use so that your tree will interface with the main test file. This is by no means an exhaustive list of the functions that you will be writing.

Required Functions

Print the tree in the following manners. When printing a value, print the string followed by a , and 1 space. You must follow these guidelines exactly! For example: Aliens, The Lord of the Rings, Kill Bill,

void preOrder( ) const: Traverse and print the tree in preorder notation.

void inOrder( ) const: Traverse and print the tree in inorder notation

void postOrder( ) const: Traverse and print the tree in postorder notation

void insert(const string &): Insert an item into the 2-3 tree. Be sure to maintain the 2-3 tree properties.

void remove(const string &): Remove a specified item from the tree. Be sure to maintain the 2-3 tree properties. Some removes can be resolved in multiple ways. To make sure that your output matches mine exactly, follow the examples listed in the notes below. If an ambiguous case arises that I have not specified, ask me and I will make the specification.

bool search(const string &) const: Search for a specified item in the tree. Return true if the item exists in the tree. Return false if the item does not exist.

Node.h: contains the Node class definition. You may add additional variables and functions to this class but you MAY NOT add another Node * or another string variable. You will lose points if you add either of these types of variables.

Tree.h: You may add additional variables and functions to this class but you MAY NOT add another Node * or another string variable. You will lose points if you add either of these types of variables.

//Node.h

#ifndef __NODE_H #define __NODE_H

#include

using namespace std;

class Node {

friend class Tree;

private: string small; string large;

Node *left; Node *middle; Node *right; Node *parent;

// Add additional functions/variables here. Remember, you may not add any // Node * or string variables.

};

#endif

//Tree.h

#ifndef __TREE_H #define __TREE_H

#include "Node.h"

class Tree { private: Node *root;

public: Tree( ); ~Tree( ); void insert(const string &); void preOrder( ) const; void inOrder( ) const; void postOrder( ) const; void remove(const string &); bool search (const string &) const;

private: // Add additional functions/variables here };

#endif

//main.cpp

#include "Tree.h" #include

using namespace std;

void printOrders(Tree *tree) { cout << "Preorder = "; tree->preOrder( ); cout << "Inorder = "; tree->inOrder( ); cout << "Postorder = "; tree->postOrder( ); }

int menu() { int choice = 0; cout << endl << "Enter menu choice: "; cout << endl; cout << "1. Insert" << endl << "2. Remove" << endl << "3. Print" << endl << "4. Search" << endl << "5. Quit" << endl; cin >> choice; // fix buffer just in case non-numeric choice entered // also gets rid of newline character cin.clear(); cin.ignore(256, ' '); return choice; }

int main( ) {

Tree tree;

int choice = menu();

string entry; while (choice != 5) { if (choice == 1) { cout << "Enter movie title to insert: "; getline(cin, entry); cout << endl; tree.insert(entry); } else if (choice == 2) { cout << "Enter movie title to remove: "; getline(cin, entry); cout << endl; tree.remove(entry); } else if (choice == 3) { printOrders(&tree); } else if (choice == 4) { cout << "Enter movie title to search for: "; getline(cin, entry); cout << endl; if (tree.search(entry)) { cout << "Found" << endl; } else { cout << "Not Found" << endl; } }

//fix buffer just in case non-numeric choice entered choice = menu(); } return 0; }