Code to determine the depth (level numbers) of the vertices in a binary tree. Add a member function getLevelNumber(int 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 of node identified by its id. In the main function, first call the assignLevelNumbers( ) function on the object of class Binary Search Tree before determining the number of comparisons for successful 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 getLevelNumber(int nodeid) 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.

#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 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 assignLevelNumbers(){

Queue queue;

queue.enqueue(rootNodeID);

arrayOfBTNodes[rootNodeID].setLevelNum(0);

while (!queue.isEmpty()){

int firstNodeInQueue = queue.dequeue();

int leftChildID = arrayOfBTNodes[firstNodeInQueue].getLeftChildID();

if (leftChildID != -1){

queue.enqueue(leftChildID);

arrayOfBTNodes[leftChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);

}

int rightChildID = arrayOfBTNodes[firstNodeInQueue].getRightChildID();

if (rightChildID != -1){

queue.enqueue(rightChildID);

arrayOfBTNodes[rightChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);

}

}

}

int getDepth(int nodeid){

return arrayOfBTNodes[nodeid].getLevelNum();

}

};

int main(){

string filename;

cout << "Enter a file name: ";

cin >> filename;

int numNodes;

cout << "Enter number of nodes: ";

cin >> numNodes;

BinaryTree binaryTree(numNodes);

ifstream fileReader(filename);

if (!fileReader){

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

return 0;

}

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 < numNodes; id++)

cout << "Depth of Node " << id << " : " << binaryTree.getDepth(id) << endl;

return 0;

}