The language is C++ visual studio express Write a class that implements a simple

Question

The language is C++ visual studio express

Write a class that implements a simple binary search tree the is capable of storing numbers. The class should have these 3 member functions, void insert(double x), bool search(double x), void inorder(vector <double> & 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 initially passed an empty vector :v it fills v the inorder list of numbers stored in the binary search tree.

Demonstrate the class using a driver program.

Explanation / Answer

Given below is the code for the question. Please don't forget to rate the answer if it helped. Thank you.

compile: g++ Btree.cpp main.cpp

Btree.h

#ifndef Btree_h
#define Btree_h
#include <vector>
using std::vector;
struct BtreeNode
{
double value;
struct BtreeNode *left;
struct BtreeNode *right;
};

class Btree
{
private:
struct BtreeNode* root;
bool search(double x, BtreeNode *n);
void inorder(vector<double> &v, BtreeNode *n);
void deleteAll(BtreeNode* n); //use by destructor to delete all nodes in the subtree root at n
public:
Btree();
void insert(double x);
bool search(double x);
void inorder(vector<double> &v);
~Btree();
  
};
#endif /* Btree_h */

Btree.cpp

#include "Btree.h"
Btree::Btree()
{
root = NULL;
}

Btree::~Btree()
{
deleteAll(root);
}
void Btree::deleteAll(BtreeNode* n)
{
if(n == NULL)
return;
deleteAll(n->left);
deleteAll(n->right);
delete n;

}
bool Btree::search(double x, BtreeNode *n)
{
if(n == NULL)
return false;
else if(x == n->value)
return true;
else if(x < n->value)
return search(x, n->left);
else
return search(x, n->right);
}
void Btree::inorder(vector<double> &v, BtreeNode *n)
{
if(n == NULL)
return;
inorder(v, n->left);
v.push_back(n->value);
inorder(v, n->right);

}
void Btree::insert(double x)
{
BtreeNode* n = new BtreeNode();
n->value =x;
n->left = NULL;
n->right = NULL;
if(root == NULL)
root = n;
else
{
BtreeNode* curr = root;
while(curr != NULL)
{
if(x < curr->value)
{
if(curr->left == NULL)
{
curr->left = n;

break;
}
else
curr = curr->left;
}
else
{
if(curr->right == NULL)
{
curr->right = n;
break;
}
else
curr = curr->right;
}
}
}

}
bool Btree::search(double x)
{
return search(x, root);
}
void Btree::inorder(vector<double> &v)
{
inorder(v, root);
}

main.cpp

#include "Btree.h"
#include <iostream>
using namespace std;

int main()
{
double numbers[10] = {5, 3, 9, 1, 7, 2, 4, 0, 6, 8};
double search[5] = { 3, 15, 9, 5, 100};
  
Btree tree;
for(int i = 0; i < 10; i++)
{
cout << "inserting " << numbers[i] << endl;
tree.insert(numbers[i]);
}
cout << endl << endl;
vector<double> v;
tree.inorder(v);
cout << "Inorder traversal of tree is ";
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
  
cout << endl << endl;
  
for(int i = 0; i < 5; i++)
{
cout << "Searching " << search[i] << ": " ;
if(tree.search(search[i]))
cout << "Found" << endl;
else
cout << "Not found" << endl;
}
}

output

inserting 5
inserting 3
inserting 9
inserting 1
inserting 7
inserting 2
inserting 4
inserting 0
inserting 6
inserting 8

Inorder traversal of tree is 0 1 2 3 4 5 6 7 8 9

Searching 3: Found
Searching 15: Not found
Searching 9: Found
Searching 5: Found
Searching 100: Not found
Program ended with exit code: 0

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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