Write in C++ ONLY Binary search tree I would really appreciate it . THANK YOU Co
ID: 3814494 • Letter: W
Question
Write in C++ ONLY
Binary search tree
I would really appreciate it . THANK YOU
Concepts overview the following section on reference printer in case you not re det We can Pointers and references do not have to be mutually exclusive have a to a point be useful parlimrter to By making a parameter a reference all changes to the formal parameter are cted in the parameter. This enables creating a parameter That to an thai may point to a different element by the end of a function cas. ary Search Tree ADT Data Items a binary search tree are of generic DataType. Each data item has data items in uniquely identifies item. (of lude additional data. The data ems must provide a function caled get usually data item's key. Any used for KeyType must the six basic returns relational operators Structure The data items form a binary tree. For each data item D in the tree. all the data items subtree have keys that are less than key and all the data items in Ds subtree have keys that are greater than D's key. Operations BSTree Requirements. None Results: an empty binary search tree. Default constructor. Creates ssTree const BSTree DataType KeyType 6 other Requirements: None Results: tree to be equivalent to the other copy constructor. Initializes the binary search BSTree object parameter.Explanation / Answer
//main.cpp
#include <iostream>
using namespace std;
#include "BSTree.cpp"
#include "config.h"
void print_help();
//--------------------------------------------------------------------
// Declaration for the binary search tree data item class
//--------------------------------------------------------------------
class TestData
{
public:
void setKey ( int newKey )
{ keyField = newKey; } // Set the key
int getKey () const
{ return keyField; } // Returns the key
private:
int keyField; // Key for the data item
};
int main()
{
BSTree<TestData,int> testTree; // Test binary search tree
TestData testData; // Binary search tree data item
int inputKey; // User input key
char cmd; // Input command
print_help();
do
{
testTree.showStructure(); // Output tree
cout << endl << "Command: "; // Read command
cin >> cmd;
if ( cmd == '+' || cmd == '?' ||
cmd == '-' || cmd == '<' )
cin >> inputKey;
switch ( cmd )
{
case 'P' : case 'p' :
print_help();
break;
case '+' : // insert
testData.setKey(inputKey);
cout << "Insert : key = " << testData.getKey()
<< endl;
testTree.insert(testData);
break;
case '?' : // retrieve
if ( testTree.retrieve(inputKey,testData) )
cout << "Retrieved : getKey = "
<< testData.getKey() << endl;
else
cout << "Not found" << endl;
break;
case '-' : // remove
if ( testTree.remove(inputKey) )
cout << "Removed data item" << endl;
else
cout << "Not found" << endl;
break;
case 'K' : case 'k' : // writeKeys
cout << "Keys:" << endl;
testTree.writeKeys();
break;
case 'C' : case 'c' : // clear
cout << "Clear the tree" << endl;
testTree.clear();
break;
case 'E' : case 'e' : // empty
if ( testTree.isEmpty() )
cout << "Tree is empty" << endl;
else
cout << "Tree is NOT empty" << endl;
break;
#if LAB9_TEST1
case 'G' : case 'g' : // Programming Exercise 2
cout << "Tree nodes count = " << testTree.getCount() << endl;
break;
#endif // LAB9_TEST1
#if LAB9_TEST2
case 'H' : case 'h' : // Programming Exercise 2
cout << "Tree height = " << testTree.getHeight() << endl;
break;
#endif // LAB9_TEST2
#if LAB9_TEST3
case '<' : // Programming Exercise 3
cout << "Keys < " << inputKey << " : " << endl;
testTree.writeLessThan(inputKey);
cout << endl;
break;
#endif // LAB9_TEST3
case 'Q' : case 'q' : // Quit test program
break;
default : // Invalid command
cout << "Inactive or invalid command. 'P' prints help." << endl;
}
}
while ( cin && ( cmd != 'Q' ) && ( cmd != 'q' ) );
if ( !cin ) {
cerr << "Error in console input. Exiting." << endl;
}
return 0;
}
//--------------------------------------------------------------------
void print_help() {
cout << endl << "Commands:" << endl;
cout << " P : [P]rint Help (displays this message)" << endl;
cout << " +key : Insert (or update) data item (use integers)" << endl;
cout << " ?key : Retrieve data item" << endl;
cout << " -key : Remove data item" << endl;
cout << " K : Write keys in ascending order" << endl;
cout << " C : Clear the tree" << endl;
cout << " E : Empty tree?" << endl;
cout << " G : Get count of nodes "
#if LAB9_TEST1
<< "(Active : "
#else
<< "(Inactive : "
#endif
<< "In-lab Exercise 2)" << endl;
cout << " H : Height "
#if LAB9_TEST2
<< "(Active : "
#else
<< "(Inactive : "
#endif
<< "In-lab Exercise 2)" << endl;
cout << " <key : Write keys that are < key "
#if LAB9_TEST3
<< "(Active : "
#else
<< "(Inactive : "
#endif
<< "In-lab Exercise 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
=======================================================================
//BSTree.cpp
#include "BSTree.h"
#include <iostream>
#include <algorithm>
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
{
this->dataItem = nodeDataItem;
this->left = leftPtr;
this->right = rightPtr;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
root = NULL;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
root = NULL;
*this = other;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{
if (this != &source)
{
clear();
if (other.root != NULL)
{
copyHelper(root, other.root);
}
}
return *this;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::copyHelper(BSTreeNode*& p, BSTreeNode* otherCurrent)
{
p = new BSTreeNode(otherCurrent->dataItem, NULL, NULL);
if (otherCurrent->left != NULL)
{
copyHelper(p->left, otherCurrent->left);
}
if (otherCurrent->right != NULL)
{
copyHelper(p->right, otherCurrent->right);
}
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{
this->clear();
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{
insertHelper(this->root, newDataItem);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insertHelper(BSTreeNode *&p,const DataType& newDataItem)
{
if (p == 0) // insert
{
p = new BSTreeNode(newDataItem, 0, 0);
}
else if (p->dataItem.getKey() >= newDataItem.getKey()) // search left
{
insertHelper(p->left, newDataItem);
}
else if (p->dataItem.getKey() < newDataItem.getKey()) // search right
{
insertHelper(p->right, newDataItem);
}
else // update
p->dataItem = newDataItem;
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve(const KeyType& searchKey, DataType& searchDataItem) const
{
return (retrieveHelper(root, searchKey, searchDataItem));
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieveHelper(BSTreeNode *p, const KeyType& searchKey, DataType& searchDataItem) const
{
bool result;
if (p == 0)
result = false;
else if (searchKey < p->dataItem.getKey())
result = retrieveHelper(p->left, searchKey, searchDataItem);
else if (searchKey > p->dataItem.getKey())
result = retrieveHelper(p->right, searchKey, searchDataItem);
else
{
result = true;
searchDataItem = p->dataItem;
}
return result;
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
return removeHelper(deleteKey, root);
}
template <typename DataType, class KeyType>
bool BSTree<DataType, KeyType>::removeHelper(const KeyType& deleteKey, BSTreeNode *&p) {
if (p == NULL)
return false; // not found
if (p != NULL)
{
if (deleteKey < p->dataItem.getKey())
removeHelper(deleteKey, p->left); // traverse left if the inputted key is less than the current node.
else if (deleteKey > p->dataItem.getKey()) // traverse right if the inputted key is less than the current node.
removeHelper(deleteKey, p->right);
else
{
BSTreeNode *deleteNode = p;
if (p->left == NULL) // No left child
{
p = p->right;
delete deleteNode;
}
else if (p->right == NULL) // No right child
{
p = p->left;
delete deleteNode;
}
else if ((p->left != NULL) && (p->right != NULL)) // if the node has both right and left children.
{
BSTreeNode *tempNode = p->right;
while (tempNode->left != NULL)
tempNode = tempNode->left;
p->dataItem = tempNode->dataItem;
removeHelper(tempNode->dataItem.getKey(), p->right);
}
return true;
}
}
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{
writeKeysHelper(root);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeysHelper(BSTreeNode *p) const
{
if (p == NULL)
return;
else {
writeKeysHelper(p->left);
cout << p->dataItem.getKey() << " ";
writeKeysHelper(p->right);
}
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{
clearHelper(root);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clearHelper(BSTreeNode*& p)
{
if (p != NULL)
{
if (p->right != NULL)
clearHelper(p->right);
if (p->left != NULL)
clearHelper(p->left);
delete p;
p = NULL;
}
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
return (root == 0);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
return getHeightHelper(root) - 1;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeightHelper(BSTreeNode *p) const
{
if (p == NULL)
return 0;
else {
int leftheight = getHeightHelper(p->left) + 1;
int rightheight = getHeightHelper(p->right) + 1;
return max(rightheight, leftheight);
}
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
if (root == NULL)
return 0;
else
return getCountHelper(this->root);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCountHelper(BSTreeNode *p) const
{
int count = 1;
if (p->left != NULL)
count = count + getCountHelper(p->left);
if (p->right != NULL)
count = count + getCountHelper(p->right);
return count;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
writeLessThanHelper(root, searchKey);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThanHelper(BSTreeNode *p, const KeyType& searchKey) const
{
if (p == NULL)
return;
else {
writeLessThanHelper(p->left, searchKey);
if (p->dataItem.getKey() < searchKey)
{
cout << p->dataItem.getKey() << " ";
writeLessThanHelper(p->right, searchKey);
}
}
}
#include "show9.cpp"
=======================================================================
//config.h
/**
* BSTree class (Lab 9) configuration file.
* Activate test 'N' by defining the corresponding LAB9_TESTN to have the value 1.
* Deactive test 'N' by setting the value to 0.
*/
#define LAB9_TEST1 1 // Programming Exercise 2: getCount
#define LAB9_TEST2 1 // Programming Exercise 2: getHeight
#define LAB9_TEST3 1 // Programming Exercise 3: writeLessThan
====================================================================
//show9.cpp
#include "BSTree.h"
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showStructure () const
// Outputs the keys in a binary search tree. The tree is output
// rotated counterclockwise 90 degrees from its conventional
// orientation using a "reverse" inorder traversal. This operation is
// intended for testing and debugging purposes only.
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showHelper ( BSTreeNode *p,
int level ) const
// Recursive helper for showStructure.
// Outputs the subtree whose root node is pointed to by p.
// Parameter level is the level of this node within the tree.
{
int j; // Loop counter
if ( p != 0 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem.getKey(); // Output key
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
==================================================================
//BSTree.h
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template < typename DataType, class KeyType > // DataType : tree data item
class BSTree // KeyType : key field
{
public:
// Constructor
BSTree (); // Default constructor
BSTree ( const BSTree<DataType,KeyType>& other ); // Copy constructor
BSTree& operator= ( const BSTree<DataType,KeyType>& other );
// Overloaded assignment operator
// Destructor
~BSTree ();
// Binary search tree manipulation operations
void insert ( const DataType& newDataItem ); // Insert data item
bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;
// Retrieve data item
bool remove ( const KeyType& deleteKey ); // Remove data item
void writeKeys () const; // Output keys
void clear (); // Clear tree
// Binary search tree status operations
bool isEmpty () const; // Tree is empty
// !! isFull() has been retired. Not very useful in a linked structure.
// Output the tree structure -- used in testing/debugging
void showStructure () const;
// In-lab operations
int getHeight () const; // Height of tree
int getCount () const; // Number of nodes in tree
void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey
protected:
class BSTreeNode // Inner class: facilitator for the BSTree class
{
public:
// Constructor
BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );
// Data members
DataType dataItem; // Binary search tree data item
BSTreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
};
void insertHelper(BSTreeNode *&p, const DataType& newDataItem);
bool retrieveHelper(BSTreeNode *p, const KeyType& searchKey, DataType& searchDataItem) const;
void writeKeysHelper(BSTreeNode *p) const;
int getHeightHelper(BSTreeNode *p) const;
int getCountHelper(BSTreeNode *p) const;
bool removeHelper(const KeyType &deleteKey, BSTreeNode *&p);
void clearHelper(BSTreeNode*& p);
void copyHelper(BSTreeNode*& p, BSTreeNode* otherCurrent);
void writeLessThanHelper(BSTreeNode *p, const KeyType& searchKey) const;
// Recursive helpers for the public member functions -- insert
// prototypes of these functions here.
void showHelper ( BSTreeNode *p, int level ) const;
// Data member
BSTreeNode *root; // Pointer to the root node
};
#endif // define BSTREE_H
==========================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.