C++ Program for binary search For this assignment, you have been given the inter

Question

C++ Program for binary search

For this assignment, you have been given the interface for a templated binary search tree class, and you must write the implementation. A binary search tree consists of a **root** node, which can have two children a*Left* and a *right* child. By convention, a binary search tree will uphold the **invariant** property that, for any node, all descendents of that node that are **less** than it will appear in its **left** branch, while all descendents that are **greater** than it will appear in its **right** branch. Thus, *binary search* can use this property to conduct search quickly (specifically, in $0(log n)$ time). Algorithmically, this should be easier than Assignment 4; the new challenge will be dealing with **pointers** and writing code that follows chains of pointers You will also be writing a **templated class** In theory, it should support any type In practice, I will test your templated BST class by creating binary search trees containing the following data types int double std::string DNA.

Explanation / Answer

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

template <class T>
struct Node {
T data;
Node *left;
Node *right;

Node(T val) {
this->data = val;
}

Node(T val, Node<T> left, Node<T> right) {
this->data = val;
this->left = left;
this->right = right;
}
};

template <class T>
class BST {

private:
Node<T> *root;

void addHelper(Node<T> *root, T val) {
if (root->data > val) {
if (!root->left) {
root->left = new Node<T>(val);
} else {
addHelper(root->left, val);
}
} else {
if (!root->right) {
root->right = new Node<T>(val);
} else {
addHelper(root->right, val);
}
}
}

void printHelper(Node<T> *root) {
if (!root) return;
printHelper(root->left);
cout<<root->data<<' ';
printHelper(root->right);
}

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

bool deleteValueHelper(Node<T>* parent, Node<T>* current, T data) {
if (!current) return false;
if (current->data == data) {
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->data;
current->data = validSubs->data;
validSubs->data = temp;
return deleteValueHelper(current, current->right, temp);
}
delete current;
return true;
}
return deleteValueHelper(current, current->left, data) ||
deleteValueHelper(current, current->right, data);
}

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

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

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

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

int main() {
BST<int> *bst = new BST<int>();
bst->add(11);
bst->add(2);
bst->add(5);
bst->add(-12);
  
cout << "The tree indorder is : " ;
bst->print();

cout << endl << "Deleting node with value (11) ";
bst->deleteValue(5);
cout << endl << "The tree inorder is : " ;
bst->print();
cout <<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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