Homework IN C++ Implement a(n) (unbalanced) binary search tree nonstd::MultiSet

Question

Homework IN C++

Implement a(n) (unbalanced) binary search tree nonstd::MultiSet class which behaves similarly to std::multiset (Links to an external site.)Links to an external site.. Note that you will not have to implement iterators, which is why insert is void.

Any members or methods in the private sections can be modified however you like, as long as it's still in the spirit of the assignment. For example, you may use regular pointers instead of std::unique_ptr but don't use an std::multiset as part of your implementation.

Note that in a more realistic implementation, you might not have getters and setters for the MultiSet::Node's left and right children but I have them in this assignment so I can more easily grade your code without needing to care whether you use regular pointers or something else.

multiset.h

Submission

Submit on gradeoven.com 04. nonstd MultiSet (Links to an external site.)Links to an external site.

Explanation / Answer

code:-

#include <iostream>
#include <math.h>
using namespace std;

template <class T>
struct node {
T value;
node *left;
node *right;

node(T val) {
this->value = val;
}

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

template <class T>
class Binary_Search_Tree {

private:
node<T> *root;

void add(node<T> *root, T val) {
if (root->value > val) {
if (!root->left) {
root->left = new node<T>(val);
} else {
add(root->left, val);
}
} else {
if (!root->right) {
root->right = new node<T>(val);
} else {
add(root->right, val);
}
}
}

void print(node<T> *root) {
if (!root) return;
print(root->left);
cout<<root->value<<' ';
print(root->right);
}

int Count_node(node<T> *root) {
if (!root) return 0;
else return 1 + Count_node(root->left) + Count_node(root->right);
}

int height_tree(node<T> *root) {
if (!root) return 0;
else return 1 + max(height_tree(root->left), height_tree(root->right));
}

void Max_node_print(node<T> *root) {
if (!root) return;
cout<<root->value<<' ';
if (height_tree(root->left) > height_tree(root->right)) {
Max_node_print(root->left);
} else {
Max_node_print(root->right);
}
}

bool Value_delete(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 Value_delete(current, current->right, temp);
}
delete current;
return true;
}
return Value_delete(current, current->left, value) ||
Value_delete(current, current->right, value);
}

public:
void add(T val) {
if (root) {
this->add(root, val);
} else {
root = new node<T>(val);
}
}

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

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

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

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

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

int main() {
Binary_Search_Tree<int> *bst = new Binary_Search_Tree<int>();
bst->add(11);
bst->add(1);
bst->add(6);
bst->add(-1);
bst->add(-10);
bst->add(100);
bst->print();
cout<<endl;
cout<<"Nodes count: "<<bst->nodesCount();
cout<<endl;
cout<<"Height: "<<bst->height();
cout<<endl;
cout<<"Max path: ";
bst->printMaxPath();
cout<<endl;
bst->deleteValue(11);
cout<<"11 removed: ";
bst->print();
cout<<endl;
cout<<"1 removed: ";
bst->deleteValue(1);
bst->print();
cout<<endl;
cout<<"-1 removed: ";
bst->deleteValue(-1);
bst->print();
cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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