#include <iostream> #include <fstream> #include <string> #include <cstring> // f
ID: 3735578 • Letter: #
Question
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // max function
#include <cmath> // to use abs 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 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
int heightOfLeftChild = getNodeHeight(leftChildID);
int heightOfRightChild = getNodeHeight(rightChildID);
return max(heightOfLeftChild, heightOfRightChild) + 1;
}
int getTreeHeight(){
return getNodeHeight(0);
}
bool checkHeightBalancedTree(){
// Implement this function to determine whether for each internal node, the absolute difference
// between the height of the left child and the right child is at most 1. If it is true for each internal ndoe, the
// binary tree is said to be height-balanced. Even if one internal node is not height-balanced, the
// whole binary tree is considered not height-balanced.
}
};
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, ' ');
}
cout << "Tree Height: " << binaryTree.getTreeHeight() << endl;
if (binaryTree.checkHeightBalancedTree())
cout << "The tree is height balanced.." << endl;
else
cout << "The tree is not height balanced.." << endl;
return 0;
}
In this quiz, you will determine whether a binary tree input by the user (in the form of an edge file, as discussed in the slides/class) is height-balanced or not. A binary tree is said to be height-balanced if each internal node (including the root) in the tree is height-balanced. A node is said to be height-balanced if the absolute difference in the heights of its left sub tree and right sub tree is at most 1. The binary tree (a) below is not height-balanced (as nodes 1 and 2 are not balanced), whereas the binary tree (b) below is height-balanced. Note that the height of a leaf node is 0 and the height of a non-existing tree (or sub tree) is -1 Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced YES NO YES YES YES -1 (a) A Binary Tree that is "not" Height-Balanced Node Height of Height of Abs. Height Left subtree Right subtree Diff. Balanced YES YES YES YES YES (b) A Binary Tree that is Height-Balanced You are given the code for the binary tree implementation discussed in class. You could first find the height of each node in the tree and then test for each internal node: whether the difference in the height of its left child and right child is at most 1. If this property is true for every internal node, then we exit the program by printing the binary tree is indeed height-balanced. Come up with files for storing the edge information of the two binary trees (a) and (b), and demonstrate the execution of your code to determine whether a tree is height-balanced or not. Add any member variable (an array) to keep track of the height of the individual nodes in the tree as well as use the information in this array to determine whether the binary tree is height-balanced or not. Submission (through Canvas as a single word document): (1) Complete code of the binary tree program, extended to determine if the tree is height-balanced or not (2) Screenshot of the outputs when the program is run for the above two binary trees (a) and (b)Explanation / Answer
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // max function
#include <cmath> // to use abs 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 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)
return -1;
if (isLeafNode(nodeid))
return 0;
int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist
int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist
int heightOfLeftChild = getNodeHeight(leftChildID);
int heightOfRightChild = getNodeHeight(rightChildID);
return max(heightOfLeftChild, heightOfRightChild) + 1;
}
int getTreeHeight() {
return getNodeHeight(0);
}
bool checkHeightBalancedTree() {
for (int id = 0; id < numNodes; id++) {
if (abs(getNodeHeight(arrayOfBTNodes[id].getLeftChildID()) - getNodeHeight(arrayOfBTNodes[id].getRightChildID())) > 1) {
return false; // if any node if the height difference between it's left and right children is greater than 5 return false
}
}
return true;
}
};
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, ' ');
}
cout << "Tree Height: " << binaryTree.getTreeHeight() << endl;
if (binaryTree.checkHeightBalancedTree())
cout << "The tree is height balanced.." << endl;
else
cout << "The tree is not height balanced.." << endl;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.