(Description at the bottom)

#include

#include

#include

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

#include // max function

#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;

public:

BinaryTree(int n){

numNodes = n;

arrayOfBTNodes = new BTNode[numNodes];

for (int id = 0; 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

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

cout

}

cout

}

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

}

void preOrderTraversal(int nodeid){

if (nodeid == -1)

return;

//cout

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

cin >> treeEdgesFilename;

int numNodes;

cout

cin >> numNodes;

string treeDataFilename;

cout

cin >> treeDataFilename;

BinaryTree binaryTree(numNodes);

ifstream treeEdgeFileReader(treeEdgesFilename);

if (!treeEdgeFileReader){

cout

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

cout

cout

cout

cout

t1 = high_resolution_clock::now();

binaryTree.IterativePreOrderTraversalUsingStack();

t2 = high_resolution_clock::now();

processingTime_micro = t2 - t1;

cout

cout

cout

return 0;

}

CSC 228 Data Structures and Algorithms, Fall 2018 Instructor: Dr. Natarajan Meghanathan Project 9: Binary Tree: Design and Implementation of an Iterative Algorithm (using the Stack ADT) to do a Preorder Traversal of the Vertices Due: Nov. 6th, 59 PM (submission through Canvas) 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 has 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 cfile ontains 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 NodelD 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 (nodelD) 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 (non- recursive) that uses the Stack ADT to traverse the nodes of a binary tree in a preorder fashion and determine the vertex (nodelD) 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. What to submit (one Word or PDF file in Canvas): (a 15 pts) Pseudo code of the iterative procedure of using a Stack to do a preorder traversal of the vertices in a binary tree and show that its time complexity in terms of the number of push (or pop) operations is (n) where 'n' is the number of vertices in the graph. (b - 15 pts) Illustrate the working of your pseudo code/algorithm of (a) on a small binary tree of 10 vertices (just use the node IDs) and show the listing of the vertices visited in the preorder fashion. (c 45 pts) Code for all the classes and functions (including the code for the iterative algorithm implemented). (d- 10 pts) Screenshots of your execution of the code for five trials showing the run times of both the recursive and iterative procedures as well as the maximum data value and nodelD with the max. data. (e 15 pts) Tabulate the results of (d) and determine the average run times of the recursive and iterative procedures as well as compare the magnitude of the average run times? Which procedure (recursive or iterative) takes more time and why? CSC 228 Data Structures and Algorithms, Fall 2018 Instructor: Dr. Natarajan Meghanathan Project 9: Binary Tree: Design and Implementation of an Iterative Algorithm (using the Stack ADT) to do a Preorder Traversal of the Vertices Due: Nov. 6th, 59 PM (submission through Canvas) 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 has 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 cfile ontains 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 NodelD 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 (nodelD) 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 (non- recursive) that uses the Stack ADT to traverse the nodes of a binary tree in a preorder fashion and determine the vertex (nodelD) 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. What to submit (one Word or PDF file in Canvas): (a 15 pts) Pseudo code of the iterative procedure of using a Stack to do a preorder traversal of the vertices in a binary tree and show that its time complexity in terms of the number of push (or pop) operations is (n) where 'n' is the number of vertices in the graph. (b - 15 pts) Illustrate the working of your pseudo code/algorithm of (a) on a small binary tree of 10 vertices (just use the node IDs) and show the listing of the vertices visited in the preorder fashion. (c 45 pts) Code for all the classes and functions (including the code for the iterative algorithm implemented). (d- 10 pts) Screenshots of your execution of the code for five trials showing the run times of both the recursive and iterative procedures as well as the maximum data value and nodelD with the max. data. (e 15 pts) Tabulate the results of (d) and determine the average run times of the recursive and iterative procedures as well as compare the magnitude of the average run times? Which procedure (recursive or iterative) takes more time and why