A binary tree is a max heap if it satisfies the following two properties: (i) the binary tree is essentially complete and (ii) the data for every internal node is greater than or equal to the data of its two child nodes. In class, we saw the BFS-based algorithm (pseudo code is given in the slides) to determine whether a binary tree is essentially complete or not. The idea is briefly as follows: We do a BFS of the nodes starting from the root node. We keep track of whether we come across a state wherein an internal node does not have a child node. The moment we come across an internal node with a missing Child node (left node or right node), we set the boolean noChildZoneStarts to true. If we come across an internal node with a child node when the boolean noChildZoneStarts is true, we declare the tree is not essentially complete! If we are done with BFS and do not come across any internal node with a child node after the boolean noChildZoneStarts is set to true, we say the binary tree is essentially complete! To implement the isMaxHeap( ) function, you could go over the arrayOfBTNodes[...] from index (n/2)-1 and check whether for each internal node, the data at the internal node is greater than or equal to the data of its child node(s). Consider the code for the binary tree given to you for this question. Add code in the blank space provided for the member function isEssentiallyComplete( ) and isMaxHeap( ) in the BinaryTree class. These member functions should check whether the binary tree satisfies the two requirements to serve as a Max Heap. The input by the user is a binary tree (in the form of the edges and data information stored in two separate files; similar to Project 7 wherein you will have to input two files: one file for the edge information and the other file for the data associated with the nodes). You are provided a sample of two files that constitute the edges and data for a binary tree that is also a max heap. You could validate your code with these two files. The main function of the code given to you is already updated to input the above two files. Your task is only to implement the isEssentiallyComplete() and isMaxHeap() functions and test their working through files that represent the edges and data for a binary tree. Your main function should be able to test for three scenarios: (a) Binary tree that is essentially complete and a max-heap; (a) Binary tree that is essentially complete, but not a max-heap; (c) Binary tee that is not essentially complete (in this case, we need not check for the max-heap property). Make small changes to the input text files (that currently reflect scenario-a) given to you in such a way that the corresponding binary trees reflect scenarios-b and c. Capture the screenshots of the outputs. What to submit (in a word document, through Canvas): The complete code, including the implementation of the isEssentiallyComplete() and isMaxHeap() functions in the BinaryTree class as well as the main function. Draw the binary trees corresponding to the three scenarios (a), (b) and (c) and include screenshots of the outputs obtained by running the code with the three scenarios of input files.

#include

#include

#include

#include // for string tokenizer and c-style string processing

#include // max function

using namespace std;

class BTNode{

private:

int nodeid;

int data;

int levelNum;

BTNode* leftChildPtr;

BTNode* rightChildPtr;

public:

BTNode(){}

void setNodeId(int id){

nodeid = id;

}

int getNodeId(){

return nodeid;

}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setLevelNum(int level){

levelNum = level;

}

int getLevelNum(){

return levelNum;

}

void setLeftChildPtr(BTNode* ptr){

leftChildPtr = ptr;

}

void setRightChildPtr(BTNode* ptr){

rightChildPtr = ptr;

}

BTNode* getLeftChildPtr(){

return leftChildPtr;

}

BTNode* getRightChildPtr(){

return rightChildPtr;

}

int getLeftChildID(){

if (leftChildPtr == 0)

return -1;

return leftChildPtr->getNodeId();

}

int getRightChildID(){

if (rightChildPtr == 0)

return -1;

return rightChildPtr->getNodeId();

}

};

class Node{

private:

int data;

Node* nextNodePtr;

Node* prevNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

void setPrevNodePtr(Node* nodePtr){

prevNodePtr = nodePtr;

}

Node* getPrevNodePtr(){

return prevNodePtr;

}

};

class Queue{

private:

Node* headPtr;

Node* tailPtr;

public:

Queue(){

headPtr = new Node();

tailPtr = new Node();

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

Node* getTailPtr(){

return tailPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void enqueue(int data){

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

Node* lastNodePtr = tailPtr->getPrevNodePtr();

if (lastNodePtr == 0){

headPtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(0);

}

else{

lastNodePtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(lastNodePtr);

}

tailPtr->setPrevNodePtr(newNodePtr);

}

int dequeue(){

Node* firstNodePtr = headPtr->getNextNodePtr();

Node* nextNodePtr = 0;

int poppedData = -100000; //empty queue

if (firstNodePtr != 0){

nextNodePtr = firstNodePtr->getNextNodePtr();

poppedData = firstNodePtr->getData();

}

else

return poppedData;

if (nextNodePtr != 0){

nextNodePtr->setPrevNodePtr(0);

headPtr->setNextNodePtr(nextNodePtr);

}

else{

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

return poppedData;

}

int peek(){

Node* firstNodePtr = headPtr->getNextNodePtr();

if (firstNodePtr != 0)

return firstNodePtr->getData();

else

return -100000; //empty queue

}

};

class BinaryTree{

private:

int numNodes;

int rootNodeID;

BTNode* arrayOfBTNodes;

public:

BinaryTree(int n){

numNodes = n;

arrayOfBTNodes = new BTNode[numNodes];

rootNodeID = 0;

for (int id = 0; id < numNodes; id++){

arrayOfBTNodes[id].setNodeId(id);

arrayOfBTNodes[id].setLevelNum(-1);

arrayOfBTNodes[id].setLeftChildPtr(0);

arrayOfBTNodes[id].setRightChildPtr(0);

}

}

void setLeftLink(int upstreamNodeID, int downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(&arrayOfBTNodes[downstreamNodeID]);

}

void setRightLink(int upstreamNodeID, int downstreamNodeID){

arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[downstreamNodeID]);

}

void setNodeData(int nodeid, int data){

arrayOfBTNodes[nodeid].setData(data);

}

int getNodeData(int nodeid){

return arrayOfBTNodes[nodeid].getData();

}

void printLeafNodes(){

for (int id = 0; id < numNodes; id++){

if (arrayOfBTNodes[id].getLeftChildPtr() == 0 && arrayOfBTNodes[id].getRightChildPtr() == 0)

cout << id << " ";

}

cout << endl;

}

bool isLeafNode(int nodeid){

if (arrayOfBTNodes[nodeid].getLeftChildPtr() == 0 && arrayOfBTNodes[nodeid].getRightChildPtr() == 0)

return true;

return false;

}

int getNodeHeight(int nodeid){

if (nodeid == -1 || isLeafNode(nodeid) )

return 0;

int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist

int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist

return max(getNodeHeight(leftChildID), getNodeHeight(rightChildID)) + 1;

}

int getTreeHeight(){

return getNodeHeight(0);

}

bool isEssentiallyComplete(){

}

bool isMaxHeap(){

}

};

int main(){

string treeEdgesFilename;

cout << "Enter the file name for the edges of the tree: ";

cin >> treeEdgesFilename;

int numNodes;

cout << "Enter number of nodes: ";

cin >> numNodes;

string treeDataFilename;

cout << "Enter the file name for the data of the nodes: ";

cin >> treeDataFilename;

BinaryTree binaryTree(numNodes);

ifstream treeEdgeFileReader(treeEdgesFilename);

if (!treeEdgeFileReader){

cout << "File cannot be opened!! ";

return 0;

}

int numCharsPerLine = 10;

char *line = new char[numCharsPerLine];

// '10' is the maximum number of characters per line

treeEdgeFileReader.getline(line, numCharsPerLine, ' ');

// ' ' is the delimiting character to stop reading the line

while (treeEdgeFileReader){

char* cptr = strtok(line, ",: ");

string upstreamNodeToken(cptr);

int upstreamNodeID = stoi(upstreamNodeToken);

cptr = strtok(NULL, ",: ");

int childIndex = 0; // 0 for left child; 1 for right child

while (cptr != 0){

string downstreamNodeToken(cptr);

int downstreamNodeID = stoi(downstreamNodeToken);

if (childIndex == 0 && downstreamNodeID != -1)

binaryTree.setLeftLink(upstreamNodeID, downstreamNodeID);

if (childIndex == 1 && downstreamNodeID != -1)

binaryTree.setRightLink(upstreamNodeID, downstreamNodeID);

cptr = strtok(NULL, ",: ");

childIndex++;

}

treeEdgeFileReader.getline(line, numCharsPerLine, ' ');

}

ifstream treeDataFileReader(treeDataFilename);

treeDataFileReader.getline(line, numCharsPerLine, ' ');

// ' ' is the delimiting character to stop reading the line

while (treeDataFileReader){

char* cptr = strtok(line, " ");

string nodeidToken(cptr);

int nodeid = stoi(nodeidToken);

cptr = strtok(NULL, " ");

string dataToken(cptr);

int data = stoi(dataToken);

binaryTree.setNodeData(nodeid, data);

treeDataFileReader.getline(line, numCharsPerLine, ' ');

}

if (binaryTree.isEssentiallyComplete()){

if (binaryTree.isMaxHeap()){

cout << "The binary tree is essentially complete and a Max-heap!!" << endl;

}

else{

cout << "The binary tree is essentially complete, but not a max heap" << endl;

}

}

else{

cout << "The binary tree is not essentially complete; hence it is not a max heap " << endl;

}

return 0;

}