C++ // Specification file for the IntBinaryTree class #ifndef STRBINARYTREE_H #define STRBINARYTREE_H class StrBinaryTree { private: struct TreeNode { std::string value; TreeNode *left; TreeNode *right; }; TreeNode *root; void insert(TreeNode *&, TreeNode *&); void destroySubTree(TreeNode *); void deleteNode(std::string, TreeNode *&); void makeDeletion(TreeNode *&); int count_nodes(TreeNode *) const; void displayInOrder(TreeNode *) const; void displayPreOrder(TreeNode *) const; void displayPostOrder(TreeNode *) const; public: // Constructor StrBinaryTree() { root = nullptr; } // Destructor ~StrBinaryTree() { destroySubTree(root); } // Binary tree operations void insertNode(std::string); bool searchNode(std::string); void remove(std::string); int count(){ return count_nodes(root);}; void displayInOrder() const { displayInOrder(root); } void displayPreOrder() const { displayPreOrder(root); } void displayPostOrder() const { displayPostOrder(root); } }; #endif 

// Implementation file for the StrBinaryTree class #include  #include  #include "StrBinaryTree.h" using namespace std; //************************************************************** // insert accepts a TreeNode pointer and a pointer to a node. * // The function inserts the node into the tree pointed to by * // the TreeNode pointer. This function is called recursively. * //************************************************************** void StrBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode) { if (nodePtr == nullptr) nodePtr = newNode; // Insert the node. //else if (newNode->value value) else if (newNode->value.compare(nodePtr->value)left, newNode); // Search the left branch. else insert(nodePtr->right, newNode); // Search the right branch. } //*********************************************************** // insertNode creates a new node to hold num as its value, * // and passes it to the insert function. //*********************************************************** void StrBinaryTree::insertNode(string s) { TreeNode *newNode = nullptr; // Pointer to a new node. // Create a new node and store num in it. newNode = new TreeNode; newNode->value = s; newNode->left = newNode->right = nullptr; // Insert the node. insert(root, newNode); } //*************************************************** // destroySubTree is called by the destructor. It * // deletes all nodes in the tree. //*************************************************** void StrBinaryTree::destroySubTree(TreeNode *nodePtr) { if (nodePtr) { if (nodePtr->left) destroySubTree(nodePtr->left); if (nodePtr->right) destroySubTree(nodePtr->right); delete nodePtr; } } //******************************************************* // searchNode determines whether a value is present in * // the tree. If so, the function returns true. // Otherwise, it returns false. //******************************************************* bool StrBinaryTree::searchNode(string s) { TreeNode *nodePtr = root; while (nodePtr) { if (nodePtr->value == s) return true; else if (nodePtr->value.compare(s) > 0) nodePtr = nodePtr->left; else nodePtr = nodePtr->right; } return false; } //*********************************************** // remove calls deleteNode to delete the // node whose value member is the same as num. * //*********************************************** void StrBinaryTree::remove(string s) { deleteNode(s, root); } //******************************************** // deleteNode deletes the node whose value * // member is the same as num. //******************************************** void StrBinaryTree::deleteNode(string s, TreeNode *&nodePtr) { if (nodePtr->value.compare(s) > 0) deleteNode(s, nodePtr->left); else if (nodePtr->value.compare(s) right); else makeDeletion(nodePtr); } //*********************************************************** // makeDeletion takes a reference to a pointer to the node * // that is to be deleted. The node is removed and the // branches of the tree below the node are reattached. //*********************************************************** void StrBinaryTree::makeDeletion(TreeNode *&nodePtr) { // Define a temporary pointer to use in reattaching // the left subtree. TreeNode *tempNodePtr = nullptr; if (nodePtr == nullptr) cout right == nullptr) { tempNodePtr = nodePtr; nodePtr = nodePtr->left; // Reattach the left child. delete tempNodePtr; } else if (nodePtr->left == nullptr) { tempNodePtr = nodePtr; nodePtr = nodePtr->right; // Reattach the right child. delete tempNodePtr; } // If the node has two children. else { // Move one node to the right. tempNodePtr = nodePtr->right; // Go to the end left node. while (tempNodePtr->left) tempNodePtr = tempNodePtr->left; // Reattach the left subtree. tempNodePtr->left = nodePtr->left; tempNodePtr = nodePtr; // Reattach the right subtree. nodePtr = nodePtr->right; delete tempNodePtr; } } //************************************************************* // The displayInOrder member function displays the values // in the subtree pointed to by nodePtr, via inorder traversal. * //************************************************************* void StrBinaryTree::displayInOrder(TreeNode *nodePtr) const { if (nodePtr) { displayInOrder(nodePtr->left); cout value right); } } //************************************************************* // The displayPreOrder member function displays the values // in the subtree pointed to by nodePtr, via preorder traversal. * //************************************************************* void StrBinaryTree::displayPreOrder(TreeNode *nodePtr) const { if (nodePtr) { cout value left); displayPreOrder(nodePtr->right); } } //************************************************************* // The displayPostOrder member function displays the values // in the subtree pointed to by nodePtr, via postorder traversal. * //************************************************************* void StrBinaryTree::displayPostOrder(TreeNode *nodePtr) const { if (nodePtr) { displayPostOrder(nodePtr->left); displayPostOrder(nodePtr->right); cout value left) + count_nodes(nodePtr->right); } else return 0; } 

using the text file

fire sit door consumer drop analysis think herself accept with option most financial give security pass somebody purpose quite prove minute bar face Congress head war force their keep station provide he clear main national prove space back part physical scene through report material president several from agreement raise believe although treat whole follow stay much whether series nearly like cost reality budget that carry knowledge pretty at position perform will memory practice shoulder home suggest represent benefit my site indicate kitchen data your behind stage so alone reason far free system rock person approach ten relationship front land economic time thus station personal ahead wish increase tonight discover indeed focus one first guess back choice treat president tax reality central artist we woman myself Mr detail face weight respond rise class next our clearly man make money pick home music adult measure receive ever own vote indeed know cup back front analysis wife teach wall deal seven style popular value store human family apply nothing understand without old generation crime paper radio read improve major end his especially cup task pull evidence high act adult science may yeah change far result paper strategy cultural bank check idea sure leg few summer peace computer thus suffer and miss else expert true goal majority ok they modern guy southern foot phone my event treatment four public ok toward tree floor direction federal environment enough result control within billion Mr carry scene rock difference television certain power minute else live because century green walk blue imagine develop spring morning wall may learn human like per must heart power behavior each PM kind address player positive wear conference catch cultural budget heavy if lead happen science television risk floor identify huge after another always artist including action oil station section parent south expert career college skill page middle believe fill attorney only song adult full charge those former describe partner perhaps could expect focus when every kind baby follow yard agency Congress pattern try week cold radio amount sound organization show believe figure message long something focus modern total lay hair stop billion hold country maintain moment possible treat choice own head ability return watch beautiful power expect care capital identify discover than art activity hear phone begin rule professor huge special recently support also tell myself job important impact business class son while area build none himself television hospital election other once last career assume bill would play capital project food tell reveal single early this onto need quickly become major past simply task inside address whatever scene able far blue personal too important response assume front generation he never resource after realize main sit million employee happy last drug happen home point our property much necessary apply theory much assume hold pretty production improve feeling they certainly newspaper him great really almost finish take information animal recently ago law responsibility cold at general fish receive bag doctor other idea north assume past win mother note now part author benefit garden difficult explain TV billion quality job inside manager current hospital current rise worker eat risk give effort back day movement make degree all heavy cover quality seat reveal stay card free despite law worry blue hospital read into campaign worker important difference anything future range talk second all feel value her gun wide support body conference focus perform common heavy economy local interview ability fight garden trial attack trade participant another get open whatever morning condition consider election still high again attorney plant those natural herself small clearly leg space maybe seem son bring cell Congress thing interesting sister hand American education fish plan grow poor trade ask close for guy for arrive next make especially tree us decade town including mission view air right future garden performance accept very top citizen show season exist democratic future ability about color clearly age know road subject about trade company strategy single current similar responsibility source community each I husband west tree movie source quickly best open worker reduce claim speech score public station purpose read technology try conference nor young recognize any last professional choice amount wear company site modern if source surface win most husband technology eat experience world establish station be main group visit actually gas rich compare skin check project possible operation you American billion identify painting house decide as yes entire dinner main include subject thing no policy measure national may teacher food hour easy upon industry surface reveal government vote article carry degree resource machine own about open soon right current day reason tough toward service brother expect meet purpose hear agreement really new it fire service its professor such pull history course item recent compare board particular firm final maybe drive form author year not month assume less serious impact protect coach exactly source cause fund commercial win these administration argue study guess husband book door huge page out during series order kind while administration film top nature camera himself thing office process human stop lead down direction main truth official produce consider when near big attack technology night sister natural position enter share special power watch strong dog decade ahead type green one pretty man case player focus none join cause particular Mr change interest oil consider week race focus movie leader town whether according attorney instead himself rather real on foot near by rise environment view never fire everyone property particularly everyone heavy him staff represent spring guess road sing why opportunity food blue himself end top agreement they case beautiful huge significant remember color rather including only certain next into thought term feel again play toward stage enough common difference small worry move per past investment night candidate against live later performance right buy shoulder family relationship politics win about firm school recently audience word wonder Democrat probably though his official not guess experience coach open do threat every situation support difficult choice natural should structure last hair hear third book short something heart home hair bill beautiful amount sign table toward body 

Using the attached binary search tree class and input file, create a driver to do the following: Read in a file of words, and insert each word into your BST as a single string Display the number of words in your BST to the user. Next, prompt the user to choose Inorder, PreOrder, Postorder. Then display the contents of your BST in the order that was selected by the user