file link to work on: https://drive.google.com/open?id=0B4V1J8L8aCbtUWN3Y0s5LW1z

Question

file link to work on: https://drive.google.com/open?id=0B4V1J8L8aCbtUWN3Y0s5LW1zd0k

In this lab you will implement a binary tree and some basic operations on it. The lab kit includes a main function that will be used to run your implementation of the data structure (in this case the binary tree) You will have to fill in the necessary code in function body marked as IMPLEMENT MEO. You should com- ment out or delete the line containing IMPLEMENT ME) macros after you are done implementing the function Please use the Makefile given along with the lab kit to compile and test your code. The sample test data will be read from the file data.txt. You may not use any standard template libraries. Please use the principles of object oriented programming to design your program. You may not store the data being read from the file in an array/vector. You should dynamically build the binary tree as you read the data from the data.txt 3 Operations on Binary Tree 1. addElem: signature void BinaryTree: :addElem (int elem); lhis function adds an element to binary tree in a levelorder fashion. Every new element should be added in the last position. Consider a constructed binary tree from the given data.txt file. The binary tree should look like fig. Dand adding an element (say 15) will change the structure of the binary tree to fig.2 2. deleteElem: signature void BinaryTree: :deleteElem (); This function deletes the element that occurs at the last position according to level order traversal in the binary tree and returns the value that it has deleted. The function if called on a tree shown in fig. 2should alter the state of the tree to fi. and should return 15

Explanation / Answer

binary.cpp

#include "binary-tree.hpp"
#include "util.hpp"

BinaryTree::BinaryTree(){
IMPLEMENT_ME();
}

BinaryTree::~BinaryTree() {
IMPLEMENT_ME();
}

void BinaryTree::addElem(int elem) {
IMPLEMENT_ME();
}

int BinaryTree::deleteElem() {
IMPLEMENT_ME();
return 0;
}

bool BinaryTree::exists(int elem) {
IMPLEMENT_ME();
return false;
}

int BinaryTree::inorderTraverse(int identity, int (*operation)(int, int)){
IMPLEMENT_ME();
return 0;
}

int BinaryTree::preorderTraverse(int identity, int (*operation)(int, int)){
IMPLEMENT_ME();
return 0;
}

int BinaryTree::postorderTraverse(int identity, int (*operation)(int, int)){
IMPLEMENT_ME();
return 0;
}

int BinaryTree::sum(){
IMPLEMENT_ME();
return 0;
}

void BinaryTree::print(int printType) {
if(printType == 1){
std::cout << "inorder traversal: " << std::endl;
IMPLEMENT_ME();
}
else if(printType == 2){
std::cout << "preorder traversal: " << std::endl;
IMPLEMENT_ME();
} else if(printType == 3){
std::cout << "postorder traversal: " << std::endl;
IMPLEMENT_ME();
} else {
std::cout << "Error invalid print type. Please choose a correct option."
<< std::endl;
}
}

binary.hpp

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

/**
* Binary tree is tree like structure but with a special property
* for each node - there are only 2 children. The left node and the
* right node and it holds a data point with in the node.
*
* In our current implementation of binary tree we will use
* to store our data as integers.
*/
class BinaryTree {

private:
//Member fields
//IMPLEMENT ME

//Member functions
//IMPLEMENT ME

public:
//Member functions
/**
* Constructor to construct the BinaryTree.
*/
BinaryTree();

/**
* Destructor to destroy the BinaryTree
* Make sure you deallocate everything that you allocate on heap.
*/
~BinaryTree();

/**
* add and element to BinaryTree in last position of level order addition
*/
void addElem(int elem);

/**
* Deletes the element that occurs at the "last position" according to
* level order in the binary tree and returns the value that it has deleted
*/
int deleteElem();

/**
* Should return true if the element exists otherwise return false
*/
bool exists(int elem);

/**
* this function performs an in-order traversal over the existing
* binary tree.
*
* The first argument to the function is the identity element or the base case
* that can be used by the function (*operation) -- the second argument --
* to start computation. eg. to multiply all the elements of
* the tree identity = 1 and *operation = multiply(int a, int b){return a*b;}
*
*/
int inorderTraverse(int identity, int (*operation)(int, int));

/**
* this function performs an pre-order traversal over the existing
* binary tree.
*
* The first argument to the function is the identity element or the base case
* that can be used by the function (*operation) -- the second argument --
* for computation.
*
*/
int preorderTraverse(int identity, int(*operation)(int, int));

/**
* this function performs an post-order traversal over the existing
* binary tree.
*
* The first argument to the function is the identity element or the base case
* that can be used by the function (*operation) -- the second argument --
* for computation.
*
*/
int postorderTraverse(int identity, int(*operation)(int, int));

/**
* returns the sum of all the nodes in the binary tree
* HINT: can you make use of the traversal functions that you have implemented?
*/
int sum();

/**
* Prints all the elements of the list with delimited with space
* takes an argument printType that decides with type of traversal print
* the function should run
* HINT: Can you make use the traversal functions you have already implemented?
*/
void print(int printType);
};

#endif //BINARY_TREE_H defined

main.cpp

#include <iostream>
#include <fstream>

#include "util.hpp"
#include "binary-tree.hpp"

using namespace std;

void printMenu();
void printTreeMenu();
void initialize(BinaryTree* &myBinaryTree, int argCount, char** args);
void cleanUp(BinaryTree* &myBinaryTree);
/**
* This is the main entry point for the application
* if you want to use your own custom datafile you'd have to pass that
* as an argument to the function.
* i.e. ./main mytest.txt
*/
int main(int argCount, char** args){

int option;
int printType;
int elem;
BinaryTree* myBinaryTree = new BinaryTree();

//read from the file and initialize the BinaryTree
initialize(myBinaryTree, argCount, args);
printMenu();
cin >> option;
while(option != 7){
switch(option){
case 1:
cout << "Enter element to be added: ";
int newElement;
cin >> newElement;
myBinaryTree->addElem(newElement);
cout << endl;
break;
case 2:
// 2: deletes the last element
cout << "deleting last element: " << myBinaryTree->deleteElem();
break;
case 3:
//3: exists
cout << "Enter element to be searched for: ";
cin >> elem;
(myBinaryTree->exists(elem) == true)
? cout << "Element found"
: cout << "Could not find element";
cout << endl;
break;
case 4:
//4: sum
cout << "Sum: " << myBinaryTree->sum();
break;
case 6:
//4: print
printTreeMenu();
cin >> printType;
myBinaryTree->print(printType);
break;
default:
cout << "Invalid argument." << endl;
break;
}
printMenu();
cin >> option;
}

cleanUp(myBinaryTree);
return 0;
}

/**
* Prints the menu of choices to the user
*/
void printMenu(){
cout << "Please choose one of the following commands:" << endl;
cout << "1: addElem" << endl;
cout << "2: deleteElem" << endl;
cout << "3: exists" << endl;
cout << "4: sum all elements" << endl;
cout << "6: print" << endl;
cout << "7: exit" << endl;
cout << ">> ";
}

void printTreeMenu(){
cout << "Which traversal? " << endl;
cout << "1: inorder traversal " << endl;
cout << "2: preorder traversal " << endl;
cout << "3: postorder traversal " << endl;
cout << ">> ";
}

/**
* Initializes the data structures and program environment
*/
void initialize(BinaryTree* &myBinaryTree, int argCount, char** args){
fstream inputData;
if(argCount < 2){
cout << "No input file given, using default data.txt" << endl;
inputData.open("data.txt", ifstream::in);
} else {
cout << "Using data from " << args[1] << endl;
inputData.open(args[1], ifstream::in);
}
while(!inputData.eof()){
int newElement;
inputData >> newElement;
if(inputData.good()){
myBinaryTree->addElem(newElement);
}
}
cout << "Done reading the file!" << endl;
inputData.close();
}

/**
* clean up all the space allocated on heap and environment variables if any
*/
void cleanUp(BinaryTree* &myBinaryTree){
//IMPLEMENT ME
delete myBinaryTree;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.