Implement the simplified heap class for integers in c refer


1. Implement the Binary Search Tree (BST) in C++, using the Node class template provided below. Please read the provided helper methods in class BST, especially for deleteValue(), make sure you get a fully understanding of the recursive algorithm, by comparing it with Algorithms 3.4.15 and 3.4.16 from page 128 to 130. Are they equivalent?

template
class Node {
public:
T value;
Node *left;
Node *right;

Node(T val) {
value = val;
left = NULL;
right = NULL;
}

Node(T val, Node left, Node right) {
value = val;
left = left;
right = right;
}
};

template
class BST {

private:
Node *root;
intheightHelper(Node *root) {
if (!root) return 0;
else return 1 + max(heightHelper(root->left), heightHelper(root->right));
}
bool deleteValueHelper(Node* parent, Node* current, T value) {
if (!current) return false;
if (current->value == value) {
if (current->left == NULL || current->right == NULL) {
Node* 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* validSubs = current->right;
while (validSubs->left) {
validSubs = validSubs->left;
}
T temp = current->value;
current->value = validSubs->value;
validSubs->value = temp;
return deleteValueHelper(current, current->right, temp);
}
delete current;
return true;
}
return deleteValueHelper(current, current->left, value) ||
deleteValueHelper(current, current->right, value);
}


public:
void add(T val) {
}

// print items in ascending order
void print() {
}

intnodesCount() {

}

intheight() {
return heightHelper(this->root);
}

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

Then test it with the following list of last names in our class:
intmain() {
constsize_tarraySize{17};
array names{"Taylor", "Tian", "Wheeler",
"Wilmot", "Hoffmann", "Fall", "Kline", "Aparicio",
"Li", "Hess", "Stenseng", "Weiss", "Hood", "Christiansen",
"Dale", "Seward", "Han"};

BST *bst = new BST();

for(size_ti{0}; ibst->add(names[i]);
bst->print();
cout<cout<<"Nodes count: "<nodesCount();
cout<cout<<"Height: "<height();
cout<

bst->deleteValue("Tian");
cout<<"Tian removed: ";
bst->print();
cout<

bst->deleteValue("Kline");
cout<<"Kline removed: ";
bst->print();
cout<

return 0;
}

2. Implement the simplified Heap class for integers, in C++. Refer to the algorithms in the textbook.

The required methods are:
- Siftdown (algorithm 3.5.7)
- heapify (algorithm 3.5.12)
- print (to print the array of integers)
Test your heap's heapify method,using the following sequence of integers as initial status of the array.Display the before and after status.
42, 58, 11, 33, 81, 65, 32, 19, 24, 57, 13, 47, 66, 41, 95

Solution Preview :

Prepared by a verified Expert
C/C++ Programming: Implement the simplified heap class for integers in c refer
Reference No:- TGS02929674

Now Priced at $25 (50% Discount)

Recommended (92%)

Rated (4.4/5)

2015 ┬ęTutorsGlobe All rights reserved. TutorsGlobe Rated 4.8/5 based on 34139 reviews.