Please code in C++ and include screnshots. Please make it copyable! For Q2, draw
ID: 3600961 • Letter: P
Question
Please code in C++ and include screnshots. Please make it copyable!
For Q2, draw the two binary search trees (along with their node ids and data) that you have come up with, include the text files (the edges and data files for the corresponding two binary trees) that are input to the program and the complete C++ or Java code to test your program as well as the screenshots of the outputs.
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // 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 BinaryTree{
private:
int numNodes;
BTNode* arrayOfBTNodes;
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);
}
}
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 checkBST(){
// check for each internal node, the data for the node is greater than or equal to its left child
// and lower than or equal to its right child
}
};
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.checkBST())
cout << "The binary tree is a Binary Search Tree" << endl;
else
cout << "The binary tree is not a binary search tree" << endl;
return 0;
}
Q2 - 50 pts) A binary search tree (BST) is a binary tree in which the data for an internal node is greater than or equal to the data of its left child node and lower than or equal to the data of its right child node nary tree given to you for this question. Add code in the blank space provided Consider the code for the bi for the member function checkBST) in the BinaryTree class. This member function should check whether the binary tree input by the user (in the form of the edge and data information stored in two separate files) is a binary search tree. le of two files that constitute the edges and data for a binary tree that is also a You are provided a binary search tree. 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 checkBSTO function and test its working through files that represent the edges and data for a binary tree. samp To test your code, come up with two binary tree of at least 12 nodes as follows (i) A binary tree that is also a BST with the data of the nodes setup in such a way that the data for an internal node is greater than or equal to its left child and lower than or equal to its right child. (ii) In the binary tree that you came up with for (i), change the data of the nodes in such a way that for at least one internal node, the BST requirement is violated so that the binary tree is not a BST Prepare the input files (edges and data files) for the two scenarios above and test your code with these files.Explanation / Answer
Below is the updated code of BinaryTree.cpp for verifying whether a tree is binary search tree or not:
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // 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 BinaryTree {
private:
int numNodes;
BTNode* arrayOfBTNodes;
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);
}
}
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 checkBSTNode(int nodeid){
if(nodeid==-1){
return true;
}
data = arrayOfBTNodes[nodeid].getData();
int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist
int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist
if(leftChildID!=-1 && arrayOfBTNodes[leftChildID].getData()>data){
return false;
}else if(rightChildID!=-1 && arrayOfBTNodes[rightChildID].getData()<data){
return false;
}
if(!checkBSTNode(leftChildID) || !checkBSTNode(rightChildID)){
return false;
}
return true;
}
bool checkBST() {
// check for each internal node, the data for the node is greater than or equal to its left child
// and lower than or equal to its right child
int nodeid = 0;
int data = 0;
int leftData = 0;
int rightData = 0;
while(true){
data = arrayOfBTNodes[nodeid].getData();
int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist
int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist
if(leftChildID!=-1 && arrayOfBTNodes[leftChildID].getData()>data){
return false;
}else if(rightChildID!=-1 && arrayOfBTNodes[rightChildID].getData()<data){
return false;
}
nodeid++;
}
return true;
}
};