//Code1

#include #include #include 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 BinarySearchTree{ private: int numNodes; BTNode* arrayOfBTNodes; int rootNodeID; public: BinarySearchTree(int n){ numNodes = n; arrayOfBTNodes = new BTNode[numNodes]; for (int index = 0; index middleIndex){ int rootIDRightSubtree = (rightIndex + middleIndex + 1)/2; setRightLink(middleIndex, rootIDRightSubtree); arrayOfBTNodes[rootIDRightSubtree].setData(array[rootIDRightSubtree]); ChainNodes(array, rootIDRightSubtree, middleIndex+1, rightIndex); } } void printLeafNodes(){ for (int id = 0; id

void PrintInOrderTraversal(){ InOrderTraversal(rootNodeID); cout

void selectionSort(int *array, int arraySize){ for (int iterationNum = 0; iterationNum > numElements;

int *array = new int[numElements]; int maxValue; cout > maxValue; srand(time(NULL)); cout

//Code 2

#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

int main(){ string filename; cout > filename; int numNodes; cout > numNodes; BinaryTree binaryTree(numNodes); ifstream fileReader(filename); if (!fileReader){ cout

int numCharsPerLine = 10; char *line = new char[numCharsPerLine]; // '10' is the maximum number of characters per line fileReader.getline(line, numCharsPerLine, ' '); // ' ' is the delimiting character to stop reading the line while (fileReader){ 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++; } fileReader.getline(line, numCharsPerLine, ' '); } binaryTree.assignLevelNumbers(); for (int id = 0; id CSC 228 Data Structures and Algorithms Project 8: Binary Search Tree: Average Number of Comparisons for a Successful Search You are given the following code: (1) Code to construct a binary search tree using a sorted randomly generated array of integers (2) Code to determine the depth (level numbers) of the vertices in a binary tree Add a member function assignexelNumbers to the Binary Search Tree class to determine the level numbers of the vertices in a binary search tree (start Breadth First Search with the rgatNedeR. which is considered to be at level 0) Add a member function get exelNumberint nodeid) in the Binary Search Tree class that in turn calls the getlevelNum() function on the BST node object corresponding to the 'nodeid' and returns the level number ofnode identified by its id. In the main function, first call the assigthexeNumbet:L function on the object of class Binary Search Tree before det erminin g the number of comparisons Ior successfl search Successful search: During the lecture, we saw that the number of comparisons for the successful search of a key in a binary search tree (BST) is one more than the level number of the vertex representing the key in the BST. In the main function, write a for loop that will go through the individual vertices and extract their level numbers using the ngdeid) function called on an object of the class Binary Search Tree. Use these level numbers of the vertices to calculate the average number of comparisons for a successful search and print the same Test your code with the following values for the number of elements in the array. 10, 100, 1000, 10000 The maximum value for an element in each case is 2500. As part of the output, you need not print the contents of the array. Just print the average number of comparisons for a successful search for each of the above four values for the number of elements in the array What to submit: Include both (a) and (b) in a single word document and submit: (a) The complete code for the binary search tree class (including the implementation of the assigexe Number) and get.exe Numbe in) functions) and the associated classes as well as the extended main function that determines the average number of comparisons for a successful search. With a screenshot of the output (b) Tabulate the values for the number of elements vs. the average number of comparisons for a successful search. Why is that the average number of comparisons increases very slowly with increase in the number of elements