Implementing the Tree-based or Ordered Map Implementing the Tree-based or Ordered Map Input: ● Line 1 indicates number of lines to follow ● Each line starts with a command that indicates which method...

#include
#include
#include
#include
#include
#include
#include
using std::cout;
using std::cin;
using std::getline;
using namespace std;
//AVL tree implementation
//TreeNode class that contains constructors
class TreeNode {
public:
string idNum;
string name;
int height;
int balanceFactor;
TreeNode *left;
TreeNode *right;
//constructor
TreeNode(string name, string x, int height) : idNum(x), name(name),
height(height), left(nullptr), right(nullptr) {};
};
//Counts the number of nodes in a tree through recursive function
int countNodes(TreeNode *root, int &numOfNodes) {
//if the tree is empty
if (root == NULL)
return 0;
else //If there is a node found in the tree
{
numOfNodes = 1 + countNodes(root->left, numOfNodes) +
countNodes(root->right, numOfNodes);
return numOfNodes;
}
}
//returns the height of a tree
//helper function for insert
int getheight(TreeNode *root, int &numOfNodes) {
int numOfRight = 0;
int numOfLeft = 0;
if (root == NULL)
return 0;
else {
//storing height of the subtree
numOfRight = 1 + countNodes(root->right, numOfNodes);
numOfLeft = 1 + countNodes(root->left, numOfNodes);
//finds which subtree has the greater height and returns the greater height
if (numOfRight > numOfLeft)
return numOfRight;
else
return numOfLeft;
}
}
//updates the balance factor if the node passed in
//helper function for insert
void balanceFactor(TreeNode *root, int &numOfNodes) {
int numOfRight = 0;
int numOfLeft = 0;
//if the root has a key
if (root != NULL) {
numOfRight = 1 + countNodes(root->right, numOfNodes);
numOfLeft = 1 + countNodes(root->left, numOfNodes);
//computing balance factor
int balanceFactor = numOfLeft - numOfRight;
//updating the root variable with proper balance factor
root->balanceFactor = balanceFactor;
}
}
//Traversals
//Inorder
vector inorder(TreeNode *&head, int &numOfNodes, int count,
vector &nameVecInOrder, vector &InOrderKey) {
if (head == NULL)
cout << "";
else {
//recursive call of left subtree
inorder(head->left, numOfNodes, count, nameVecInOrder, InOrderKey);
//pushes name into a vector inorder
//This vector is passed by reference into the function and is used in the main for printing
nameVecInOrder.push_back(head->name);
//pushes the ID number (inorder) into the vector
//This vector is used for the deletion of Nth node function
InOrderKey.push_back(head->idNum);
//recursive call of right subtree
inorder(head->right, numOfNodes, count, nameVecInOrder, InOrderKey);
}
return nameVecInOrder;
}
//preorder
void preorder(TreeNode *&head, int &numOfNodes, int count, vector &
nameVecPreOrder) {
if (head == NULL)
cout << "";
else {
//pushes name into a vector preorder
//This vector is passed by reference into the function and is used in the main for printing
nameVecPreOrder.push_back(head->name);
//recursive call of left subtree
preorder(head->left, numOfNodes, count, nameVecPreOrder);
//recursive call of right subtree
preorder(head->right, numOfNodes, count, nameVecPreOrder);
}
}
//postorder
void postorder(TreeNode *&head, int &numOfNodes, int count, vector &
nameVecPostOrder) {
if (head == NULL)
cout << "";
else {
//recursive call of left subtree
postorder(head->left, numOfNodes, count, nameVecPostOrder);
//recursive call of right subtree
postorder(head->right, numOfNodes, count, nameVecPostOrder);
//pushes name into a vector postorder
//This vector is passed by reference into the function and is used in the main for printing
nameVecPostOrder.push_back(head->name);
}
}
//n-Ary Level order
int levelOrder(TreeNode *&root) {
//creation of que for children
queue queueOfNodes;
//push the root of the tree into the que
queueOfNodes.push(root);
//variable counting levels of the tree
int countLevels = 0;
//if there is no root then there are zero levels printed
if (root == NULL) {
cout << "0" << endl;
return 0;
}
//while the que data structure is empty
//no children in the level
while (queueOfNodes.size() != 0) {
int numOfNodesinLevels = queueOfNodes.size();
//While the number of nodes in the level surpass zero
while (numOfNodesinLevels > 0) {
//a temp node variable pointing to the front of the que
TreeNode *temp = queueOfNodes.front();
//printing nodes on each levels
...