Write a C++ program to do the following:

Inputs a line of text.

Tokenizes the line into separate words.

Inserts the words into a binary search tree (BST).

Do a postorder traversal of the tree and print it.

Do a preorder traversal of the tree and print it.

Do an inorder traversal of the tree and print it.

Print the heights and the number of leafs in each of the three binary search trees.

Please upload the following:

The class .cpp file

The main program

The class .h file

Output File

However, I am trying to utilize this header:

-------------------------------------------------------------------------------------------------------------------

//Binary.h

#pragma once #include

using namespace std;

template struct nodeType { T info; string data; nodeType* lLink; nodeType* rLink; };

template class BinaryTreeType { protected: nodeType *root; public: BinaryTreeType(); protected: ~BinaryTreeType(); public: bool isEmpty() const; virtual void insert(const T& item) = 0; virtual void deleteNode(const T& item) = 0; virtual bool search(const T& item) = 0; void inOrderTraversal() const; void preOrderTraversal() const; void postOrderTraversal() const; private: void inOrder(nodeType *p) const; void preOrder(nodeType *p) const; void postOrder(nodeType *p) const; void destroy(nodeType * &p); int findTreeHeight(nodeType *p) const; int getLeafCount(nodeType* p) const; }; template class BST : public BinaryTreeType { protected: ~BST() = default; private: void insert(const T& item) override; void deleteNode(const T& item) override; bool search(const T& item) override { return false; } private: void deleteFromTree(nodeType * &p); };

template void BinaryTreeType::preOrder(nodeType *p) const { if (root != nullptr) { cout << root->data << " "; preOrder(root->lLink); preOrder(root->rLink); } }

template BinaryTreeType::BinaryTreeType() { root = nullptr; }

template BinaryTreeType::~BinaryTreeType() { destroy(root); }

template bool BinaryTreeType::isEmpty() const { return (root == nullptr); }

template void BinaryTreeType::inOrderTraversal() const { inOrder(root); }

template void BinaryTreeType::preOrderTraversal() const { preOrder(root); }

template void BinaryTreeType::postOrderTraversal() const { postOrder(root); }

template void BinaryTreeType::inOrder(nodeType *p) const { if (root != nullptr) { inOrder(root->lLink); cout << root->data << " "; inOrder(root->rLink); } }

template void BinaryTreeType::postOrder(nodeType *p) const { if (root != nullptr) { postOrder(root->lLink); postOrder(root->rLink); cout << root->data << " "; } }

template void BinaryTreeType::destroy(nodeType*& p) { if (p != nullptr) { destroy(p->lLink); destroy(p->rLink); cout << "Destroying " << p->info << endl; delete p; p = nullptr; } }

template int BinaryTreeType::findTreeHeight(nodeType *temp) const { if (temp == nullptr) return -1;

return (max(findTreeHeight(temp->lLink), findTreeHeight(temp->rLink)) + 1); }

template void BST::insert(const T& item) { nodeType *newNode; nodeType *current; nodeType *trail;

newNode = new nodeType; newNode->info = item; newNode->lLink = nullptr; newNode->rLink = nullptr; if (root == nullptr) root = newNode; else { current = root; trail = nullptr; while (current != nullptr) { trail = current;

if (current->info == item) { cout << "No duplicates allowed" << endl; } else if (current->info > item) current = current->lLink; else current = current->rLink; } if (trail->info > item) trail->lLink = newNode; else trail->rLink = newNode; } }

template void BST::deleteNode(const T& item) { nodeType *curr; nodeType *trail; bool found = false;

if (root == nullptr) cout << "Nothing to delete" << endl; else { curr = root; trail = curr; while (curr != nullptr && !found) { if (curr->info == item) found = true; else { trail = curr; if (curr->info > item) curr = curr->lLink; else curr = curr->rLink; } } if (found) { if (curr == root) deleteFromTree(root); else if (trail->info > item) deleteFromTree(trail->lLink); else deleteFromTree(trail->rLink); } else cout << "Item is not found" << endl; } }

template void BST::deleteFromTree(nodeType*& p) { nodeType *curr; nodeType *trail; nodeType *temp;

if (p == nullptr) cout << "Nothing to delete" << endl; else if (p->lLink == nullptr && p->rLink == nullptr) { temp = p; p = nullptr; delete temp; } else if (p->lLink == nullptr) { temp = p; p = temp->rLink; delete temp; } else if (p->rLink == nullptr) { temp = p; p = temp->lLink; delete temp; } else { curr = p->lLink; trail = nullptr; while (curr->rLink != nullptr) { trail = curr; curr = curr->rLink; } p->info = curr->info; if (trail == nullptr) //curr did not move p->lLink = curr->lLink; else trail->rLink = curr->lLink; delete curr; } }

template int BinaryTreeType::getLeafCount(nodeType *p) const { if (p == nullptr) { return 0; } if (p->lLink == nullptr && p->rLink == nullptr) { return 1; } return getLeafCount(p->lLink) + getLeafCount(p->rLink); }

--------------------------------------------------------------------------------------

//source.cpp

#include #include #include "Binary.h" using namespace std;

int main() {

BST* root = nullptr;

string s;

int i, j = -1;

string p;

getline(cin, s);

for (i = 0; s[i] != '\0'; i++)

{ if (s[i] == ' ')

{ p = s.substr(j + 1, i - j - 1);

j = i;

root = insert(root, p); } }

p = s.substr(j + 1, i - j);

root = insert(root, p);

cout << "Post Order Traversal is: " << endl;

postOrder(root);

cout << endl << "Pre Order Traversal is: " << endl;

preOrder(root);

cout << endl << "In Order Traversal is: " << endl;

InOrder(root);

cout << endl << "Height of tree is: " << FindHeight(root);

cout << endl << " No of leaf nodes in tree is: " << getLeafCount(root) << endl;;

return 0; }