Need help with a small C++ project involving dynamic memory management and implementation of a dynamic data structure. The main.cpp (which can not be changed), node.h, tst.h, tst.cpp, and tst.data are all given below after the specifications.

main.cpp that is given:

#include  #include  #include  #include "tst.h" char getOption() { string option; cout  "; cin >> option; return toupper(option[0]); } // getOption() void doInsert(tst & t) { int key; string data; cout > key; cout  
 
 
node.h that is given:
 
#pragma once #include  using namespace std; class node { public: private: int key; // search key string data; // data stored for this key node * left; // pointer to the BST left child (all keys  this key) }; 
 
 
 
tst.h that is given:
 
//-------------------------------------------------------------------- // class tst //-------------------------------------------------------------------- // Describes a Trinary Search Tree, a variation of a Binary Search // Tree where each node (in addition to a left and right subtree) // has a linked list of nodes with the same key value, // where the most-recent value for the key is stored in the BST node // and the older nodes are stored in a linked list in historical order //-------------------------------------------------------------------- #pragma once #include  #include "node.h" using namespace std; class tst { public: tst(); // constructor ~tst(); // destructor void insert(int k, string s); // insert new node with given key/data void print(); // print the TST int height(); // returns the Tree Height int count(); // returns number of BST nodes int fullCount(); // returns number of all nodes string search(int k); // returns current and historical data void read(); // reads data from a file int maxKey(); // returns the largest key in the tree private: void print(node * r, int level); void insert(node * p, node * r, node * rParent); // suggested void insertEqual(node *p, node *r, node * rParent); // suggested node * root; }; 
 
 
 
tst.cpp that is given:
 
#include  #include  #include  #include "tst.h" using namespace std; //-------------------------------------------------------------------- // Constructor/Destructor //-------------------------------------------------------------------- //-------------------------------------------------------------------- // insert - public //-------------------------------------------------------------------- // given a new key and data, allocates and populates a new node // When the tree is empty, makes the new node the root // When the tree is not empty, inserts the new node into the root // (parent of root is NULL) //-------------------------------------------------------------------- void tst::insert(int k, string s) { } // public //-------------------------------------------------------------------- // insert - private //-------------------------------------------------------------------- // given: pointer to a newly-allocated and populated node to insert // pointer to the tree/subtree into which the new node is to // be inserted // pointer to the parent of r. The parent's right or left // child will need to be modified if this is a // "duplicate" key, as the new node replaces the // current node (r) in the tree. //-------------------------------------------------------------------- void tst::insert(node * p, node * r, node * rParent) { // if the new node's key is LESS THAN r's key, // insert new node on the LEFT side of r. if (p->key key) { if (r->left != NULL) // r already has a left child //WRITE THIS LINE! // insert new node into r's left child else // else r has no left child //WRITE THIS LINE! // make p the new left child } else if (p->key > r->key) { // FINISH THIS!! } else insertEqual(p, r, rParent); } // insert() //-------------------------------------------------------------------- // insert - private //-------------------------------------------------------------------- // Sub method of insert()-private // p's key and r's key are equal, so p's node will replace r's in the // BST. //-------------------------------------------------------------------- void tst::insertEqual(node *p, node *r, node * rParent) { } //-------------------------------------------------------------------- // maxKey //-------------------------------------------------------------------- // returns the highest key in the tree, or -1 for an empty tree int tst::maxKey() { } //-------------------------------------------------------------------- // print //-------------------------------------------------------------------- void tst::print() { cout right, level + 1); // print this node for (int i = 0; i key data; // print the equal nodes of this node node * p = r->equal; while (p != NULL) { cout data; p = p->equal; } cout left, level + 1); } // print() //-------------------------------------------------------------------- // read //-------------------------------------------------------------------- void tst::read() { ifstream f; int k; string data; // open input file cout > data; f.open(data); if (f.fail()) { cout > k; f.ignore(); getline(f, data); while (k != -1) { // while not sentinel value insert(k, data); // insert data into TST f >> k; // read next record f.ignore(); getline(f, data); } f.close(); } // read() //-------------------------------------------------------------------- // height //-------------------------------------------------------------------- int tst::height() { } //-------------------------------------------------------------------- // count //-------------------------------------------------------------------- // returns the number of nodes in the BST, not including the nodes // in the equal lists int tst::count() { } //-------------------------------------------------------------------- // fullCount //-------------------------------------------------------------------- // returns the number of nodes in the entire structure, including the // nodes in the equal lists. int tst::fullCount() { } //-------------------------------------------------------------------- // search //-------------------------------------------------------------------- // given: a key to search for // returns: When found: a string with the current data, with the data // for any equal nodes appended with a :: between each value. // When not found: returns "NOT FOUND" //-------------------------------------------------------------------- string tst::search(int k) { } 
 
 
 
tst.txt that is given:
 
150 One Fifty 130 One Thirty 170 One Seventy 120 One Twenty 140 One Forty 160 One Sixty 180 One Eighty -1 End of data 
  Learning Objectives Use of dynamic memory management - - Implementation of a dynamic data structure General Description: Complete the coding of a Trinary Search Tree (aka Unique-keyed Duplicate-saving Binary Search Tree), using dynamic memory management. A description of the standard Binary Search Tree will be given in class and in the class notes. Enhance this data structure in the following manner: Besides the standard left and right subtrees, each node will have a linked list of nodes where the keys of nodes in the linked list all have the same key as the node itself. The nodes in the linked list represent a chronological/historical record of the data values for the key at a previous time. When a node of the same key is inserted, the current node is "pushed down" onto the linked list, and the new node replaces it in the BST structure Example INSERT KEY 20 DATA-Alpha INSERT KEY-10 DATA-Beta INSERT KEY-30 DATA-Gamma INSERT KEY-20 DATA-A Prime INSERT KEY-20 DATA-A Deuter Standard BST (equals to the right) TST (equals replaced, old nodes pushed down) inserted third Primeinserted second inserted first ipha Specifications: Start with the cpp and .h files provided. You should not have to change the main.cpp except adding your name where indicated. You may of course use your own main() function while unit testing your code... just be sure to use the main) given for your final tests and when submitting.  Learning Objectives Use of dynamic memory management - - Implementation of a dynamic data structure General Description: Complete the coding of a Trinary Search Tree (aka Unique-keyed Duplicate-saving Binary Search Tree), using dynamic memory management. A description of the standard Binary Search Tree will be given in class and in the class notes. Enhance this data structure in the following manner: Besides the standard left and right subtrees, each node will have a linked list of nodes where the keys of nodes in the linked list all have the same key as the node itself. The nodes in the linked list represent a chronological/historical record of the data values for the key at a previous time. When a node of the same key is inserted, the current node is "pushed down" onto the linked list, and the new node replaces it in the BST structure Example INSERT KEY 20 DATA-Alpha INSERT KEY-10 DATA-Beta INSERT KEY-30 DATA-Gamma INSERT KEY-20 DATA-A Prime INSERT KEY-20 DATA-A Deuter Standard BST (equals to the right) TST (equals replaced, old nodes pushed down) inserted third Primeinserted second inserted first ipha Specifications: Start with the cpp and .h files provided. You should not have to change the main.cpp except adding your name where indicated. You may of course use your own main() function while unit testing your code... just be sure to use the main) given for your final tests and when submitting