Can someone please help me with this assignment. The details are listed below St
ID: 3831283 • Letter: C
Question
Can someone please help me with this assignment. The details are listed below
Start with the binaryTree class provided in lesson 23 and make the following changes. Don't make any changes other than the additions listed here. Do not add the big-3 yet. We'll work on that next week. (Adding private helper functions is also ok.)
mSize: Add a data member to store the size of the tree. Call it "mSize" to distinguish it from the "size()" function. You'll need to update this new data member in all of the appropriate places in the class implementation. Change the size() function so that it returns this data member instead of calculating the size.
numPrimes(): Add a "numPrimes()" function to the class that returns the number of nodes in the tree that contain prime integers. Good decomposition dictates that you will want a helper function that determines whether its parameter is prime. Don't worry about making this efficient. Just test all of the numbers less than the parameter and if any of them divide evenly into the parameter, then it's not prime.
toLL(): Add a "toLL()" function to the class that converts the calling binary tree object into an LL object. The items in the LL object should be in increasing order. The created LL object should be returned. Here's a sample client to illustrate how this function might be used:
Explanation / Answer
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <cstdlib> // for size_t
//implementation
#include <iostream>
// #include "binarytree.h"
using namespace std;
const // this is a const object...
class {
public:
template<class T> // convertible to any type
operator T*() const // of null non-member
{ return 0; } // pointer...
template<class C, class T> // or any type of null
operator T C::*() const // member pointer...
{ return 0; }
private:
void operator&() const; // whose address can't be taken
} nullptr = {};
class binarytree {
public:
typedef std::size_t size_type;
binarytree();
void insert(int item);
void print() const;
int numPrimes() const;
size_type size() const;
int find(int target, bool& found) const;
void del(int target, bool& found);
private:
struct treenode {
int data;
treenode* left;
treenode* right;
};
treenode* root;
friend void insert_aux(treenode*& root, int item);
friend void print_aux(treenode* root);
friend size_type size_aux(treenode* root);
friend int find_aux(treenode* root, int target, bool& found);
friend void del_aux(treenode*& root, int target, bool& found);
friend void remove_max(treenode*& root, int& max);
friend int num_primes_aux(treenode* root);
friend bool is_prime(int n);
};
#endif
binarytree::binarytree() {
root = nullptr;
}
void binarytree::print() const {
print_aux(root);
}
void binarytree::insert(int item) {
insert_aux(root, item);
}
binarytree::size_type binarytree::size() const {
return size_aux(root);
}
int binarytree::find(int target, bool& found) const {
return find_aux(root, target, found);
}
void binarytree::del(int target, bool& found) {
del_aux(root, target, found);
}
void del_aux(binarytree::treenode*& root,
int target,
bool& found) {
if (root == nullptr) {
found = false;
}
else if (target < root->data) {
del_aux(root->left, target, found);
}
else if (target > root->data) {
del_aux(root->right, target, found);
}
else if (root->left == nullptr) {
binarytree::treenode* tempptr = root;
root = root->right;
delete tempptr;
found = true;
}
else {
int max;
remove_max(root->left, max);
root->data = max;
found = true;
}
}
// pre: root != nullptr
void remove_max(binarytree::treenode*& root, int& max) {
if (root->right == nullptr) {
max = root->data;
binarytree::treenode* tempptr = root;
root = root->left;
delete tempptr;
}
else {
remove_max(root->right, max);
}
}
int find_aux(binarytree::treenode* root,
int target,
bool& found) {
if (root == nullptr) {
found = false;
return 0;
}
else if (target == root->data) {
found = true;
return root->data;
}
else if (target < root->data) {
return find_aux(root->left, target, found);
}
else {
return find_aux(root->right, target, found);
}
}
binarytree::size_type size_aux(binarytree::treenode* root) {
if (root == nullptr) {
return 0;
}
else {
return size_aux(root->left)
+ size_aux(root->right)
+ 1;
}
}
void insert_aux(binarytree::treenode*& root, int item) {
if (root == nullptr) {
// root = new treenode(item, nullptr, nullptr);
root = new binarytree::treenode;
root->data = item;
root->left = nullptr;
root->right = nullptr;
}
else if (item <= root->data) {
insert_aux(root->left, item);
}
else {
insert_aux(root->right, item);
}
}
void print_aux(binarytree::treenode* root) {
if (root != nullptr) {
print_aux(root->left);
cout << root->data << " ";
print_aux(root->right);
}
}
bool is_prime(int n){
for(int i=2;i<n;i++){
if(n%i == 0) return false;
}
return true;
}
// Sample usage : cout << "Number of primes = "<<tree.numPrimes() << endl;
int binarytree::numPrimes() const{
return num_primes_aux(root);
}
int num_primes_aux(binarytree::treenode* root){
int count = 0;
if (root != nullptr) {
count += num_primes_aux(root->left);
// cout << root->data << " ";
if(is_prime(root->data)){
count++;
}
count+= num_primes_aux(root->right);
}
return count;
}
//Sample test from main
#include <iostream>
// #include "LL.h"
#include "binarytree.h"
using namespace std;
int main() {
binarytree t;
for (int i = 0; i < 20; i++) {
t.insert(rand() % 50);
}
cout << "The binary tree: ";
t.print();
cout << endl;
cout << "Number of primes = "<<t.numPrimes() << endl;
// LL<int> l;
// l = t.toLL();
// cout << "The linked list: ";
// for (LL<int>::iterator i = l.begin(); i != l.end(); i++) {
// cout << *i << " ";
// }
cout << endl;
cout << endl;
}