implement a binary search tree

Question Description

those are the files that are supposed to be completed.

main.cpp

	#include <iostream>
	#include <cstring> // strcmp
	#include <stdlib.h> // srand, rand
	#include <time.h> // time
	#include <math.h> // pow (for exponents)

	#include "BST.h" //BST implementation

	using namespace std;

	void test_copy_constructor() {
	cout << " [t] Testing copy constructor" << endl;
	BST<int> * bstsrc = new BST<int>({4,2,1,3,6,5,7,9,8});
	BST<int> * bstcopy = new BST<int>(*bstsrc); // Invoke copy constructor
	cout << "Should produce: t1 2 3 4 5 6 7 8 9" << endl;
	cout << "BST src (in order): t"; bstsrc->printInOrder(); cout << endl;
	cout << "BST copy (in order): t"; bstcopy->printInOrder(); cout << endl;
	if( bstsrc->getRoot() == NULL \|\| bstcopy->getRoot() == NULL )
	cout << " FAIL: one of trees is NULL " << endl;
	else if( bstsrc->getRoot() != bstcopy->getRoot() )
	cout << " PASS: Did a deep copy of tree since copy has diff root than src" << endl;
	else
	cout << " FAIL: Did a shallow copy of tree since they both point to same root" << endl;
	cout << endl;
	}

	void test_move_constructor() {
	cout << " [t] Testing move constructor" << endl;
	BST<int> bstsrc = BST<int>({4,2,1,3,6,5,7,9,8});
	BST<int> bstmove = std::move( bstsrc ); // Invoke move constructor
	cout << "Should produce: <nothing, it's been moved.> " << endl;
	cout << "BST src (pre order): t"; bstsrc.printPreOrder(); cout << endl;
	cout << "Should produce: t4 2 1 3 6 5 7 9 8" << endl;
	cout << "BST move (pre order):t"; bstmove.printPreOrder(); cout << endl;
	if( bstsrc.getRoot() == NULL && bstmove.getRoot() != NULL )
	cout << " PASS: src is NULL and move is != NULL " << endl;
	else
	cout << " FAIL: someone is NULL or != NULL improperly" << endl;
	cout << endl;
	}


	void test_copy_assignment_operator() {
	cout << " [t] Testing copy= constructor" << endl;
	BST<int> bstsrc = BST<int>({4,2,1,3,6,5,7,9,8});
	BST<int> bstcopy = BST<int>({5,6,7});
	cout << " BST to copy over starts: t"; bstcopy.printLevelOrder(); cout << endl;
	cout << " Invoking copy assingment operator." << endl;

	bstcopy = bstsrc; // Invoke copy= constructor

	cout << "Should produce: t1 3 2 5 8 9 7 6 4" << endl;
	cout << "BST src (post order): t"; bstsrc.printPostOrder(); cout << endl;
	cout << "BST copy (post order): t"; bstcopy.printPostOrder(); cout << endl;
	if( bstsrc.getRoot() == NULL \|\| bstcopy.getRoot() == NULL )
	cout << " FAIL: one of trees is NULL " << endl;
	else if( bstsrc.getRoot() != bstcopy.getRoot() )
	cout << " PASS: Did a deep copy of tree since copy has diff root than src" << endl;
	else
	cout << " FAIL: Did a shallow copy of tree since they both point to same root" << endl;
	cout << endl;
	}

	void test_move_assignment_operator() {
	cout << " [t] Testing move assignment operator" << endl;
	BST<int> bstsrc = BST<int>({4,2,1,3,6,5,7,9,8});
	BST<int> bstmove = BST<int>({5,6,7});
	bstmove = std::move( bstsrc ); // Invoke move assignment op
	cout << "Should product: <nothing, it's been moved> " << endl;
	cout << "BST src (in order): t"; bstsrc.printInOrder(); cout << endl;
	cout << "Should produce: t1 2 3 4 5 6 7 8 9" << endl;
	cout << "BST move (in order): t"; bstmove.printInOrder(); cout << endl;
	if( bstsrc.getRoot() == NULL && bstmove.getRoot() != NULL )
	cout << " PASS: src is NULL and move is != NULL " << endl;
	else
	cout << " FAIL: someone is NULL or != NULL improperly" << endl;
	cout << endl;
	}

	/* Testing in,pre,post,level order tree traversals */
	void test_tree_traversal_ordering() {
	cout << " [t] Executing tree traversal tests. " << endl;
	BST<int> * bst = new BST<int>({4,2,1,3,6,5,7,9,8});

	cout << "Should produce:t1 2 3 4 5 6 7 8 9" << endl;
	cout << "Inorder: t";
	bst->printInOrder();
	cout << endl << endl;

	cout << "Should produce:t1 3 2 5 8 9 7 6 4" << endl;
	cout << "Postorder: t";
	bst->printPostOrder();
	cout << endl << endl;

	cout << "Should produce:t4 2 1 3 6 5 7 9 8" << endl;
	cout << "Preorder: t";
	bst->printPreOrder();
	cout << endl << endl;

	cout << "Should produce:t4 2 6 1 3 5 7 9 8" << endl;
	cout << "Levelorder: t";
	bst->printLevelOrder();
	cout << endl << endl;

	vector<int> testLvL{4,2,6,1,3,5,7,9,8};
	vector<int> & retLvL = bst->returnLevelOrder();
	if( testLvL == retLvL ) {
	cout << " PASS: returnLevelOrder returned proper vector." << endl;
	} else {
	cout << " FAIL: did not return proper level order vector." << endl;
	}
	cout << endl;

	return;
	}

	void test_tree_features() {
	cout << " [t] Testing features of the BST. " << endl;
	BST<int> * bst = new BST<int>({4,2,1,3,6,5,7,9,8});
	cout << "Contains (7): t";
	(bst->contains(7)) ? cout << " True – [PASS] " : cout << " False – [FAIL]";
	cout << endl;
	cout << "Contains (10): ";
	(bst->contains(10)) ? cout << " True – [FAIL] " : cout << " False – [PASS]";
	cout << endl;
	cout << "Nodes count (9): " << bst->nodesCount();
	if( bst->nodesCount() == 9 )
	cout << "t[PASS]";
	else
	cout << "t[FAIL]";
	cout << endl;
	cout << "Height (5): " << bst->height();
	if( bst->height() == 5 )
	cout << "tt[PASS]";
	else
	cout << "tt[FAIL]";
	cout << endl;
	cout << "Max path: ";
	bst->printMaxPath();
	cout << endl;
	cout << "Should be: 4 6 7 9 8";
	cout << endl << endl;
	}

	/*
	* run_tests – Execute tests to evaluate BST
	*/
	void run_tests() {
	cout << " [t] Starting tests." << endl;

	test_tree_features();
	test_copy_constructor();
	test_move_constructor();
	test_copy_assignment_operator();
	test_move_assignment_operator();
	test_tree_traversal_ordering();

	cout << " [t] ending tests." << endl;
	return;
	}

	/*
	* run big test – LOTS of data in your tree!
	*/
	void run_big_test() {
	cout << " [t] Beginning BIG tree test! " << endl;
	srand (time(NULL)); // Initialize random seed
	BST<int> bst = BST<int>();
	int tree_size = pow(2.0, 20.0);
	cout << endl << " [t] Testing tree of size (2^20): " << tree_size << endl;
	cout << "Node # / Of #'s (% done) : Value Inserted " << endl;
	for( int i = 1; i < tree_size + 1; i++ ) {
	int val = rand() % tree_size + 1;
	cout << "r" << i << " / " << tree_size << " (" << 100.0*i / tree_size << "%)" << " : " << val;
	bst.add(val);
	}

	cout << endl << endl;
	cout << "Nodes count (" << tree_size << "): " << bst.nodesCount();
	if( bst.nodesCount() == tree_size )
	cout << "t[PASS]";
	else
	cout << "t[FAIL]";
	cout << endl;
	cout << "Height: " << bst.height() << endl;
	cout << "Max path: ";
	bst.printMaxPath();
	cout << endl << endl;

	cout << " [t] BIG tree test done!" << endl;
	return;
	}


	/*
	* Main function – includes enabling test mode
	*/
	int main( int argc, char* argv[] ) {
	bool is_test_mode = false;
	bool is_BIG_test_mode = false;
	for( int i = 0; i < argc; i++ ) {
	if( !strcmp(argv[i], "–test" ) ) {
	cout << " [t] Enabling test mode. " << endl;
	is_test_mode = true;
	} else if ( !strcmp(argv[i], "–bigtest" ) ) {
	cout << " [t] Enabling BIG test mode. " << endl;
	is_BIG_test_mode = true;
	}
	}

	if( is_test_mode \|\| is_BIG_test_mode ) {
	run_tests();
	if( is_BIG_test_mode )
	run_big_test();
	}else{
	cout << " [x] Running main program – nothing to do!" << endl;
	cout << " Since it's quiet, here's a flower…" << endl << endl;
	cout << ""
	" __/)n"
	" .-(__(=:n"
	" \|\ \| \)n"
	"ejm97 \ \|\|n"
	" \\|\|n"
	" \\|n"
	" \|n"
	" n";
	}

	return 0;
	}

BST.h

#ifndef __BST_H
	#define __BST_H

	#include <iostream>
	#include <cstring> // strcmp
	#include <vector>
	#include <queue>
	#include <initializer_list>

	using namespace std;

	/*
	* Node data structure for single tree node
	*/
	template <class T>
	struct Node {
	T value;
	Node *left;
	Node *right;

	Node(T val) {
	this->value = val;
	this->left = NULL;
	this->right = NULL;
	}

	Node(T val, Node<T> * left, Node<T> * right) {
	this->value = val;
	this->left = left;
	this->right = right;
	}
	};

	/*
	* Binary Search Tree (BST) class implementation
	*/
	template <class T>
	class BST {

	private:
	Node<T> *root;

	/* clone a passed in tree, returns pointer to new tree */
	Node<T> * cloneTree(Node<T> *t) {
	if( t == NULL )
	return NULL;
	else
	return new Node<T>( t->value,
	cloneTree( t->left ),
	cloneTree( t->right ) );
	}

	/* Recursively delete the tree nodes */
	void makeEmptyHelper(Node<T> *t) {
	if( t != NULL ) {
	makeEmptyHelper( t->left );
	makeEmptyHelper( t->right );
	delete t;
	}
	}

	/* Add new T val to the tree */
	void addHelper(Node<T> *root, T val) {
	if (root->value > val) {
	if (!root->left) {
	root->left = new Node<T>(val);
	} else {
	addHelper(root->left, val);
	}
	} else {
	if (!root->right) {
	root->right = new Node<T>(val);
	} else {
	addHelper(root->right, val);
	}
	}
	}

	/* Print tree out in inorder (A + B) */
	void printInOrderHelper(Node<T> *root) {
	if (!root) return;
	printInOrderHelper(root->left);
	cout << root->value << ' ';
	printInOrderHelper(root->right);
	}

	/* Print tree out in post order (A B +) */
	void printPostOrderHelper(Node<T> *root) {
	if (!root) return;
	printPostOrderHelper(root->left);
	printPostOrderHelper(root->right);
	cout << root->value << ' ';
	}

	/* Print tree out in pre order (+ A B) */
	void printPreOrderHelper(Node<T> *root) {
	if (!root) return;
	cout << root->value << ' ';
	printPreOrderHelper(root->left);
	printPreOrderHelper(root->right);
	}

	/* Print tree out in level order */
	/* MA TODO: Implement */
	void printLevelOrderHelper(Node<T> *root) {
	if (!root) return;
	/*
	MA TODO:
	*/
	cout << endl;
	cout << "printLevelOrderHelper UNIMPLEMENTED AT THIS TIME — REPLACE!" << endl;
	cout << " ** Required to use the STL queue class (that's a huge hint)!" << endl;
	cout << " ** Doing this with a loop will be easier than recursion." << endl;
	}

	/* Generate vector of tree values to return */
	/* MA TODO: Implement */
	vector<T> & returnLevelOrderHelper(Node<T> *root) {
	vector<T> * ret = new vector<T>{};
	if (!root) return( *ret );
	/*
	MA TODO:
	*/
	cout << endl;
	cout << " returnLevelOrderHelper UNIMPLEMENTED AT THIS TIME — REPLACE!" << endl;
	cout << " ** Required to use the STL queue class (that's a huge hint)!" << endl;
	cout << " ** Doing this with a loop will be easier than recursion." << endl;
	return( *ret );
	}

	/* Return number of nodes in tree */
	int nodesCountHelper(Node<T> *root) {
	if (!root) return 0;
	else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right);
	}

	/* Return height of tree (root == NULL -> 0) */
	int heightHelper(Node<T> *root) {
	if (!root) return 0;
	else return 1 + max(heightHelper(root->left), heightHelper(root->right));
	}

	/* Print out longest path from root to a leaf */
	void printMaxPathHelper(Node<T> *root) {
	if (!root) return;
	cout<<root->value<<' ';
	if (heightHelper(root->left) > heightHelper(root->right)) {
	printMaxPathHelper(root->left);
	} else {
	printMaxPathHelper(root->right);
	}
	}

	/* Delete a given T value from tree */
	bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
	if (!current) return false;
	if (current->value == value) {
	if (current->left == NULL \|\| current->right == NULL) {
	Node<T>* temp = current->left;
	if (current->right) temp = current->right;
	if (parent) {
	if (parent->left == current) {
	parent->left = temp;
	} else {
	parent->right = temp;
	}
	} else {
	this->root = temp;
	}
	} else {
	Node<T>* validSubs = current->right;
	while (validSubs->left) {
	validSubs = validSubs->left;
	}
	T temp = current->value;
	current->value = validSubs->value;
	validSubs->value = temp;
	return deleteValueHelper(current, current->right, temp);
	}
	delete current;
	return true;
	}
	return deleteValueHelper(current, current->left, value) \|\|
	deleteValueHelper(current, current->right, value);
	}

	bool containsHelper(Node<T> * root, T val) {
	if( root == NULL )
	return( false );
	else if( root->value == val )
	return( true );
	else if( root->value > val ) // Search left
	return( containsHelper(root->left, val) );
	else
	return( containsHelper(root->right, val) );
	}


	public:

	BST( ) : root( NULL ) { } // Basic initialization constructor

	BST( initializer_list<T> vals ) : root( NULL ) { // Vector-based initializer
	for( auto val : vals )
	this->add(val);
	}

	~BST( ) { // Destructor – free all nodes
	cout << " [d] Destructor called." << endl;
	cout << " TODO: Implement destructor to free whole tree. " << endl;
	}

	/* Copy constructor */
	/* MA TODO: Implement */
	BST( const BST &other ) : root( NULL ) {
	cout << " [d] Copy constructor called. " << endl;
	cout << " TODO: Implement copy constructor. " << endl;
	}

	/* Move constructor */
	/* MA TODO: Implement */
	BST ( BST && other ) : root( NULL ) {
	cout << " [d] Move constructor called " << endl;
	cout << " TODO: Implement move constructor. " << endl;
	}

	/* Copy assignment operator */
	/* MA TODO: Implement */
	BST& operator=(BST & other) {
	cout << " [d] Copy assignment operator called. " << endl;
	cout << " TODO: Implement copy assignment operator. " << endl;

	return *this;
	}

	/* Move assignment operator */
	/* MA TODO: Implement */
	BST& operator=(BST && other) {
	cout << " [d] Move assignment operator called. " << endl;
	cout << " TODO: Implement move assignment operator. " << endl;

	return *this;
	}

	/* Public API */
	void makeEmpty( ) {
	if (root)
	this->makeEmptyHelper(root);
	}

	void add(T val) {
	if (root) {
	this->addHelper(root, val);
	} else {
	root = new Node<T>(val);
	}
	}

	bool empty() {
	return( root != NULL );
	}

	void print() {
	printInOrderHelper(this->root);
	}

	void printInOrder() {
	printInOrderHelper(this->root);
	}

	void printPostOrder() {
	printPostOrderHelper(this->root);
	}

	void printPreOrder() {
	printPreOrderHelper(this->root);
	}

	void printLevelOrder() {
	printLevelOrderHelper(this->root);
	}

	vector<T> & returnLevelOrder() {
	return returnLevelOrderHelper(this->root);
	}

	int nodesCount() {
	return nodesCountHelper(root);
	}

	int height() {
	return heightHelper(this->root);
	}

	void printMaxPath() {
	printMaxPathHelper(this->root);
	}

	bool deleteValue(T value) {
	return this->deleteValueHelper(NULL, this->root, value);
	}

	bool contains( T value ) {
	return containsHelper(this->root, value);
	}

	Node<T> * getRoot() { return(root); } // Gives out our root pointer for testing
	};


	#endif

Makefile

# Variables
	GPP = g++
	CFLAGS = -g -std=c++11 -Wall #-static
	RM = rm -f
	BINNAME = levelsort

	# Shell gives make a full user environment
	# Adding this to PATH will find the newer g++ compiler on the old EECS servers.
	SHELL := /bin/bash
	PATH := /opt/rh/devtoolset-3/root/usr/bin/:$(PATH)


	# Default is what happenes when you call make with no options
	# In this case, it requires that 'all' is completed
	default: all

	# All is the normal default for most Makefiles
	# In this case, it requires that build is completed
	all: build

	# build depends upon main.cpp, then runs the command:
	# g++ -g -std=c++11 -o levelsort
	build: main.cpp
	$(GPP) $(CFLAGS) -o $(BINNAME) main.cpp

	run: build
	./$(BINNAME)

	test: build
	./$(BINNAME) –test

	bigtest: build
	./$(BINNAME) –bigtest

	# If you call "make clean" it will remove the built program
	# rm -f levelsort
	clean veryclean:
	$(RM) $(BINNAME)

	# If you call "make starwars" it'll give you Star Wars!"
	starwars:
	telnet towel.blinkenlights.nl

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.

Do you need an answer to this or any other questions?

About Writedemy

We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.

How It Works

To make an Order you only need to click on “Place Order” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.

Are there Discounts?

All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.

Question Description

About Writedemy

We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.

How It Works

Are there Discounts?

Hire a tutor today CLICK HERE to make your first order

Wridemy

Study Help

About Us