1.Write a class For implementing a simple binary search tree capable of storing
ID: 3714351 • Letter: 1
Question
1.Write a class For implementing a simple binary search tree capable of storing numbers. The class should have member functions: void insert (double x) bool search(double x) void inorder (vector & v ) The insert function should not use recursion directly, or indirectly by calling a recursive function. The search function should work by calling a private recursive member function bool search (double x, BtreeNode *t) The inorder function is passed an initially empty vector v: it fills v with the inorder list of numbers stored in the binary search tree. Demonstrate the operation of the class using a suitable driver program
2. Modify the binary search tree to add a member function int size() that returns the number of items (nodes ) stored in the tree. Demonstrate the correctness of the new member function with a suitable driver program
PLEASE WRITE THEM BOTH AS SEPERATE CODES, I need the original as well as after it has been modified. Thank you so much in advance!
Explanation / Answer
Below is your part 1 of question
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <vector>
using namespace std;
class BinaryTree
{
private:
// The BtreeNode class is used to build the tree
class BtreeNode
{
friend class BinaryTree;
double value;
BtreeNode *left;
BtreeNode *right;
BtreeNode(double value1, BtreeNode *left1 = NULL, BtreeNode *right1 = NULL)
{
value = value1;
left = left1;
right = right1;
}
};
BtreeNode *root; // Pointer to the root of the tree
// Various helper functions.
void insert(BtreeNode *&, double);
bool search(double, BtreeNode *);
void fillInorder(vector <double> & v, BtreeNode *);
public:
// Constructor
BinaryTree(){ root = NULL; }
// Member functions.
void insert(double x)
{insert(root, x);}
bool search(double x)
{return search(x, root);}
void inorder(vector <double> & v)
{fillInorder(v, root);}
};
#endif
BinaryTree.cpp
#include <iostream>
#include <vector>
#include "BinaryTree.h"
using namespace std;
//*****************************************************************************
// insert Function inserts a number into a given subtree of the main binary *
// search tree. *
//*****************************************************************************
void BinaryTree::insert(BtreeNode * &tree, double x)
{
// If the tree is empty, make a new node and make it
// the root of the tree.
if (!tree)
{
tree = new BtreeNode(x);
return;
}
// If num is already in tree: return.
if (tree->value == x)
return;
// The tree is not empty: insert the new node into the
// left or right subtree.
if (x < tree->value)
insert(tree->left, x);
else
insert(tree->right, x);
}
//*****************************************************************************
// Function search determines if a value is present in the tree. If so, the *
// function returns true. Otherwise, it returns false. *
//*****************************************************************************
bool BinaryTree::search(double x, BtreeNode *t)
{
while (t)
{
if (t->value == x)
return true;
else if (x < t->value)
return search(x, t->left);
else
return search(x, t->right);
}
return false;
}
//*****************************************************************************
// Function inorder is passed an initially empty vector v: it fills v with *
// the inorder list of number stored in the binary search tree. *
//*****************************************************************************
void BinaryTree::fillInorder(vector <double> & v, BtreeNode *tree)
{
if (tree)
{
fillInorder(v, tree->left);
v.push_back(tree->value);
fillInorder(v, tree->right);
}
}
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
main.cpp
#include <iostream>
#include "BinaryTree.h"
#include <vector>
using namespace std;
int main()
{
BinaryTree tree;
vector<double> treeValues;
tree.insert(5.2);
tree.insert(8.6);
tree.insert(3.1);
tree.insert(12.9);
tree.insert(9.7);
if (tree.search(3))
cout << "3 was found in tree. ";
else
cout << "3 was not found in tree. ";
tree.inorder(treeValues);
for (int i = 0; i < treeValues.size(); i++)
{
cout << treeValues[i] << " ";
}
cout << endl;
return 0;
}
Output
3 was not found in tree.
3.1 5.2 8.6 9.7 12.9
Below is your code for part 2
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <vector>
using namespace std;
class BinaryTree
{
private:
// The BtreeNode class is used to build the tree
class BtreeNode
{
friend class BinaryTree;
double value;
BtreeNode *left;
BtreeNode *right;
BtreeNode(double value1, BtreeNode *left1 = NULL, BtreeNode *right1 = NULL)
{
value = value1;
left = left1;
right = right1;
}
};
BtreeNode *root; // Pointer to the root of the tree
// Various helper functions.
void insert(BtreeNode *&, double);
bool search(double, BtreeNode *);
void fillInorder(vector <double> & v, BtreeNode *);
int calSize(BtreeNode *);
public:
// Constructor
BinaryTree(){ root = NULL; }
// Member functions.
void insert(double x)
{insert(root, x);}
bool search(double x)
{return search(x, root);}
void inorder(vector <double> & v)
{fillInorder(v, root);}
int size() {
return calSize(root);
}
};
#endif
BinaryTree.cpp
#include <iostream>
#include <vector>
#include "BinaryTree.h"
using namespace std;
//*****************************************************************************
// insert Function inserts a number into a given subtree of the main binary *
// search tree. *
//*****************************************************************************
void BinaryTree::insert(BtreeNode * &tree, double x)
{
// If the tree is empty, make a new node and make it
// the root of the tree.
if (!tree)
{
tree = new BtreeNode(x);
return;
}
// If num is already in tree: return.
if (tree->value == x)
return;
// The tree is not empty: insert the new node into the
// left or right subtree.
if (x < tree->value)
insert(tree->left, x);
else
insert(tree->right, x);
}
//*****************************************************************************
// Function search determines if a value is present in the tree. If so, the *
// function returns true. Otherwise, it returns false. *
//*****************************************************************************
bool BinaryTree::search(double x, BtreeNode *t)
{
while (t)
{
if (t->value == x)
return true;
else if (x < t->value)
return search(x, t->left);
else
return search(x, t->right);
}
return false;
}
//*****************************************************************************
// Function inorder is passed an initially empty vector v: it fills v with *
// the inorder list of number stored in the binary search tree. *
//*****************************************************************************
void BinaryTree::fillInorder(vector <double> & v, BtreeNode *tree)
{
if (tree)
{
fillInorder(v, tree->left);
v.push_back(tree->value);
fillInorder(v, tree->right);
}
}
//*****************************************************************************
//Function to calculate size of Binary tree
//*****************************************************************************
int BinaryTree::calSize(BtreeNode *tree)
{
if (tree==NULL)
return 0;
else
return(calSize(tree->left) + 1 + calSize(tree->right));
}
main.cpp
#include <iostream>
#include "BinaryTree.h"
#include <vector>
using namespace std;
int main()
{
BinaryTree tree;
vector<double> treeValues;
tree.insert(5.2);
tree.insert(8.6);
tree.insert(3.1);
tree.insert(12.9);
tree.insert(9.7);
if (tree.search(3))
cout << "3 was found in tree. ";
else
cout << "3 was not found in tree. ";
tree.inorder(treeValues);
for (int i = 0; i < treeValues.size(); i++)
{
cout << treeValues[i] << " ";
}
cout << endl;
cout << "Size of the tree : "<<tree.size()<<endl;
return 0;
}
Output
3 was not found in tree.
3.1 5.2 8.6 9.7 12.9
Size of the tree : 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.