Q1 50 pts) A binary tree is a complete binary tree if all the internal nodes (in
ID: 3732106 • Letter: Q
Question
Q1 50 pts) A binary tree is a complete binary tree if all the internal nodes (including the root node) have exactly two child nodes and all the leaf nodes are at level 'h' corresponding to the height of the tree. Consider the code for the binary tree given to you for this question. Add code in the blank space provided for the member function checkCompleteBinaryTree) in the BinaryTree class. This member function should check whether the binary tree input by the user (in the form of the edge information stored in a file) is a complete binary tree. To test your code, come up with two binary trees of at least 12 vertices: one, a complete binary tree and another, a binary tree that is not a complete tree. Prepare the input file for the two binary trees and input them to the code for this question. Capture the screenshots of the outputs.Explanation / Answer
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
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 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 isEssentiallyCompleteUtil(int nodeid, int index){
if (nodeid == -1)
return true;
if (index >= numNodes)
return (false);
return (isEssentiallyCompleteUtil(arrayOfBTNodes[nodeid].getLeftChildID(), 2*index + 1) &&isEssentiallyCompleteUtil(arrayOfBTNodes[nodeid].getRightChildID(), 2*index + 2));
}
bool checkCompleteBinaryTree(){
return isEssentiallyCompleteUtil(0,0);
}
};
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.checkCompleteBinaryTree()){
cout << "The binary tree is complete<< endl;
}
else{
cout << "The binary tree is NOT complete" << endl;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.