ANSWER
As per the given question,
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // max function
#include <stdlib.h>
#include <time.h>
using namespace std;
// Extend the code here as needed
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;
int rootNodeID;
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;
}
void PrintNodeData(){
for (int nodeid = 0; nodeid < numNodes; nodeid++)
cout << nodeid << " " << arrayOfBTNodes[nodeid].getData() << endl;
}
void InOrderTraversal(int nodeid, int *dataArray){
if (nodeid == -1)
return;
InOrderTraversal(arrayOfBTNodes[nodeid].getLeftChildID(), dataArray);
cout << arrayOfBTNodes[nodeid].getData() << " ";
InOrderTraversal(arrayOfBTNodes[nodeid].getRightChildID(), dataArray);
}
void constructBSTree(int *array){
int leftIndex = 0;
int rightIndex = numNodes-1;
int middleIndex = (leftIndex + rightIndex)/2;
rootNodeID = middleIndex;
arrayOfBTNodes[middleIndex].setData(array[middleIndex]);
ChainNodes(array, middleIndex, leftIndex, rightIndex);
}
void ChainNodes(int* array, int middleIndex, int leftIndex, int rightIndex){
if (leftIndex < middleIndex){
int rootIDLeftSubtree = (leftIndex + middleIndex-1)/2;
setLeftLink(middleIndex, rootIDLeftSubtree);
arrayOfBTNodes[rootIDLeftSubtree].setData(array[rootIDLeftSubtree]);
ChainNodes(array, rootIDLeftSubtree, leftIndex, middleIndex-1);
}
if (rightIndex > middleIndex){
int rootIDRightSubtree = (rightIndex + middleIndex + 1)/2;
setRightLink(middleIndex, rootIDRightSubtree);
arrayOfBTNodes[rootIDRightSubtree].setData(array[rootIDRightSubtree]);
ChainNodes(array, rootIDRightSubtree, middleIndex+1, rightIndex);
}
}
void PrintInOrderTraversal(int *dataArray){
// Extend the code for this function here as needed
constructBSTree(dataArray);
InOrderTraversal(rootNodeID, dataArray);
cout << endl;
}
};
void SelectionSort(int *array, int arraySize){
for (int iterationNum = 0; iterationNum < arraySize-1; iterationNum++){
int minIndex = iterationNum;
for (int j = iterationNum+1; j < arraySize; j++){
if (array[j] < array[minIndex])
minIndex = j;
}
// swap array[minIndex] with array[iterationNum]
int temp = array[minIndex];
array[minIndex] = array[iterationNum];
array[iterationNum] = temp;
}
}
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, '\n');
// '\n' 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, '\n');
}
// Generating the data array
int *dataArray = new int[numNodes];
int maxValue;
cout << "Enter the maximum value for an element: ";
cin >> maxValue;
srand(time(NULL));
cout << "Data array generated: ";
for (int index = 0; index < numNodes; index++){
dataArray[index] = 1 + rand() % maxValue;
cout << dataArray[index] << " ";
}
cout << endl;
SelectionSort(dataArray, numNodes);
cout << "Inorder traversal: " << endl;
binaryTree.PrintInOrderTraversal(dataArray);
cout << "Node(ID) Data " << endl;
binaryTree.PrintNodeData();
system("pause");
return 0;
}
===============================================
SEE OUTPUT
PLEASE COMMENT if there is any concern.
=========================================
Thank you for the question....kindly rate ...it helps me a lot
in c++ please program for this code #include <iostream> #include <fstream> #include <string> #include <cstring> //...
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...
#include <iostream> #include <string> #include <cstring> using namespace std; class Node{ private: int data; Node* nextNodePtr; public: Node(){} void setData(int d){ data = d; } int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } ...
moviestruct.cpp #include <iostream> #include <fstream> #include <cstdlib> #include <ostream> #include <fstream> #include <cstdlib> #include <cstring> using namespace std; typedef struct{ int id; char title[250]; int year; char rating[6]; int totalCopies; int rentedCopies; }movie; int loadData(ifstream &infile, movie movies[]); void printAll(movie movies[], int count); void printRated(movie movies[], int count); void printTitled(movie movies[], int count); void addMovie(movie movies[],int &count); void returnMovie(movie movies[],int count); void rentMovie(movie movies[],int count); void saveToFile(movie movies[], int count, char *filename); void printMovie(movie &m); int find(movie movies[], int...
Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {} void insertNode( const NODETYPE &value ) { insertNodeHelper( &rootPtr, value ); } void preOrderTraversal() const { preOrderHelper( rootPtr ); } void inOrderTraversal() const { inOrderHelper( rootPtr ); } private: TreeNode< NODETYPE > *rootPtr; void insertNodeHelper( TreeNode< NODETYPE > **ptr, const NODETYPE &value ) { if ( *ptr == nullptr ) * ptr = new...
C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please help me figure out. Thanks. C++ BST implementation (using a struct) Enter the code below, and then compile and run the program. After the program runs successfully, add the following functions: postorder() This function is similar to the inorder() and preorder() functions, but demonstrates postorder tree traversal. displayParentsWithTwo() This function is similar to the displayParents WithOne() function, but displays nodes having only two children....
Can you take a look at my code that why the maxDepth function is not working? public class BinaryTree { class Node{ int key; Node left,right; public Node(int item) { key = item; left = right = null; } } Node root; public void BinaryTree(){ root = null; } void...
PLEASE CODE IN C++ AND MAKE IT COPYABLE! In this project, you will design and implement an algorithm to determine the next greater element of an element in an array in Θ(n) time, where 'n' is the number of elements in the array. You could use the Stack ADT for this purpose. The next greater element (NGE) for an element at index i in an array A is the element that occurs at index j (i < j) such that...
fully comments for my program, thank you will thumb up #include <iostream> #include <fstream> #include <string> #include <iomanip> using namespace std; struct book { int ISBN; string Author; string Title; string publisher; int Quantity; double price; }; void choice1(book books[], int& size, int MAX_SIZE) { ifstream inFile; inFile.open("inventory.txt"); if (inFile.fail()) cout <<"file could not open"<<endl; string str; while(inFile && size < MAX_SIZE) { getline(inFile, str); books[size].ISBN = atoi(str.c_str()); getline(inFile, books[size].Title); getline(inFile, books[size].Author); getline(inFile, books[size].publisher); getline(inFile,...
I need help of how to include the merge sort code into this counter code found below: #include<iostream> using namespace std; int bubble_counter=0,selection_counter=0; // variables global void bubble_sort(int [], int); void show_array(int [],int); void selectionsort(int [], int ); int main() { int a[7]={4,1,7,2,9,0,3}; show_array(a,7); //bubble_sort(a,7); selectionsort(a,7); show_array(a,7); cout<<"Bubble counter = "<<bubble_counter<<endl; cout<<"Selection Counter = "<<selection_counter<<endl; return 0; } void show_array(int array[],int size) { for( int i=0 ; i<size; i++) { cout<<array[i]<< " "; } cout<<endl; } void bubble_sort( int array[],...
3. (Gaddis Exercises 20.4) Tree Height Write a recursive member function for the BinaryTree class that returns the height of the tree. The height of the tree is the number of levels it contains. Demonstrate the function in a driver program. CPP FILE CODE: #include "BinaryTree.h" #include <iostream> using namespace std; BinaryTree::BinaryTree() { root = NULL; } BinaryTree::~BinaryTree() { destroy(root); } bool BinaryTree::search(int data) { return search(data, root); } void BinaryTree::insert(int data) { insert(data, root); } void BinaryTree::traverseInOrder() { traverseInOrder(root);...