The objective of this project is to design and implement an iterative algorithm (using the Stack ADT) to do a preorder traversal of the vertices in a binary tree and find the vertex ID with the maximum data as well as the maximum data. Each vertex in the binary tree have an associated data value. You are given the code for a binary tree implementation (including all the associated classes) and the main function that will accept two files as input: binaryTree-2000001.txt and data-2000001.txt. The binaryTree-2000001.txt contains the entries storing the structure of a binary tree of 1000000 internal nodes plus a root node as well as another 1000000 leaf nodes (a total of 2000001 nodes). Assume the root NodeID is 0 and the preorder traversal starts from the root node. The data-2000001.txt file contains the data associated with the 2000001 nodes. The code given to you has the implementation of the recursive procedure to do a preorder traversal of the binary tree and determine the vertex (nodeID) with the maximum data as well as the associated data value. You could go through the recursive implementation to get an idea for finding the node with the maximum data and the associated maximum data value. The code for the Stack ADT (class Stack and class Node) is also included along with the other classes in the file given. Your task in this project will be to design and implement the code for an iterative algorithm (nonrecursive) that uses the Stack ADT to traverse the nodes of a binary tree in a preorder fashion and determine the vertex (nodeID) with the maximum data as well as the associated data value. The iterative algorithm is to be implemented as a member function of the BinaryTree class as indicated in the code provided. The main function has the code setup to call the recursive and iterative procedures on the binary tree object (setup based on the two input files) as well as the timers setup to calculate the run times of these two procedures. After you implement the iterative algorithm, you will run the code for five trials and report the running times for both the procedures for each of the trials as well as the average value. Compare the average running times for the recursive and iterative procedures and interpret the results. .cpp file #include #include #include #include // for string tokenizer and c-style string processing #include // max function #include #include #include #include using namespace std; 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 Stack { private: Node * headPtr; Node* tailPtr; public: Stack() { 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 push(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 pop() { Node* lastNodePtr = tailPtr->getPrevNodePtr(); Node* prevNodePtr = 0; int poppedData = -100000; //empty stack if (lastNodePtr != 0) { prevNodePtr = lastNodePtr->getPrevNodePtr(); poppedData = lastNodePtr->getData(); } else return poppedData; if (prevNodePtr != 0) { prevNodePtr->setNextNodePtr(0); tailPtr->setPrevNodePtr(prevNodePtr); } else { headPtr->setNextNodePtr(0); tailPtr->setPrevNodePtr(0); } return poppedData; } int peek() { Node* lastNodePtr = tailPtr->getPrevNodePtr(); if (lastNodePtr != 0) return lastNodePtr->getData(); else return -100000; // empty stack } }; 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 BinaryTree { private: int numNodes; int maxDataPerNode; int maxDataNodeID; BTNode* arrayOfBTNodes, root; public: BinaryTree(int n) { numNodes = n; arrayOfBTNodes = new BTNode[numNodes]; for (int id = 0; id < numNodes; id++) { arrayOfBTNodes[id].setNodeId(id); arrayOfBTNodes[id].setLevelNum(-1); arrayOfBTNodes[id].setLeftChildPtr(0); arrayOfBTNodes[id].setRightChildPtr(0); } maxDataPerNode = -1; maxDataNodeID = -1; } 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 setMaxData(int data) { maxDataPerNode = data; } int getMaxData() { return maxDataPerNode; } void setMaxDataNodeID(int nodeid) { maxDataNodeID = nodeid; } int getMaxDataNodeID() { return maxDataNodeID; } 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); } void recursivePreOrderTraversal() { preOrderTraversal(0); //cout << endl; } void preOrderTraversal(int nodeid) { if (nodeid == -1) return; //cout << nodeid << " "; if (arrayOfBTNodes[nodeid].getData() > getMaxData()) { setMaxData(arrayOfBTNodes[nodeid].getData()); setMaxDataNodeID(nodeid); } preOrderTraversal(arrayOfBTNodes[nodeid].getLeftChildID()); preOrderTraversal(arrayOfBTNodes[nodeid].getRightChildID()); } void IterativePreOrderTraversalUsingStack() { // Implement here the code for the iterative procedure to // do preorder traversal of the binary tree using a Stack... }; 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 = 25; char *line = new char[numCharsPerLine]; // '25' 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, ' '); } using namespace std::chrono; high_resolution_clock::time_point t1 = high_resolution_clock::now(); binaryTree.recursivePreOrderTraversal(); high_resolution_clock::time_point t2 = high_resolution_clock::now(); duration processingTime_micro = t2 - t1; cout << endl << endl; cout << "Processing time (microseconds, recursive): " << processingTime_micro.count() << endl; cout << "node with max. data: " << binaryTree.getMaxDataNodeID() << endl; cout << "actual max. data: " << binaryTree.getMaxData() << endl; cout << endl << endl; t1 = high_resolution_clock::now(); binaryTree.IterativePreOrderTraversalUsingStack(); t2 = high_resolution_clock::now(); processingTime_micro = t2 - t1; cout << "Processing time (microseconds, iterative): " << processingTime_micro.count() << endl; cout << "node with max. data: " << binaryTree.getMaxDataNodeID() << endl; cout << "actual max. data: " << binaryTree.getMaxData() << endl; system("pause"); return 0; } (Binary Tree)Text File 0 : 1, 2 1 : 3, 4 2 : 5, 6 3 : 7, 8 4 : 9, 10 5 : 11, 12 6 : 13, 14 7 : 15, 16 8 : 17, 18 9 : 19, 20 10 : 21, 22 11 : 23, 24 12 : 25, 26 13 : 27, 28 14 : 29, 30 15 : 31, 32 16 : 33, 34 17 : 35, 36 18 : 37, 38 19 : 39, 40 20 : 41, 42 21 : 43, 44 22 : 45, 46 23 : 47, 48 24 : 49, 50 25 : 51, 52 26 : 53, 54 27 : 55, 56 28 : 57, 58 29 : 59, 60 30 : 61, 62 31 : 63, 64 32 : 65, 66 33 : 67, 68 34 : 69, 70 35 : 71, 72 36 : 73, 74 37 : 75, 76 38 : 77, 78 39 : 79, 80 40 : 81, 82 41 : 83, 84 42 : 85, 86 43 : 87, 88 44 : 89, 90 45 : 91, 92 46 : 93, 94 47 : 95, 96 48 : 97, 98 49 : 99, 100 Data text file 0 14480 1 19643 2 11283 3 2799 4 18017 5 24558 6 29645 7 2572 8 14183 9 28162 10 8544 11 2089 12 32212 13 22706 14 9899 15 10867 16 31148 17 20801 18 15349 19 9198 20 15993 21 22370 22 29497 23 19314 24 24897 25 8022 26 5568 27 21235 28 25269 29 9044 30 32757 31 1029