Help filling in the code below for Binary Search Tree. #include <iostream> #incl
ID: 3585322 • Letter: H
Question
Help filling in the code below for Binary Search Tree.
#include <iostream>
#include <string>
#include "BST.h"
using namespace std;
/****************************************************************
* CONSTRUCTOR
* Creates an empty binary tree
****************************************************************/
BST::BST() {
}
/****************************************************************
* DESTRUCTOR
* Free all memory used by current tree
****************************************************************/
BST::~BST()
{
// Write code to remove and deallocate all nodes in the tree
}
void BST::Insert(int toInsert)
{
// Write your code here
}
void BST::Delete(int toDelete){
// Write your code here
}
void BST::Transplant(Node *u, Node *v) {
// Write your code here
}
Node *BST::Successor(Node *x) {
// Write your code here
}
Node *BST::Minimum(Node *x) {
// Write your code here
}
Node *BST::Maximum(Node *x) {
// Write your code here
}
Node *BST::Search(int key) {
// Write your code here
}
void BST::Print(TraversalOrder Order)
{
if(Order==InOrderTrav)
InOrder(root);
else if(Order==PreOrderTrav)
PreOrder(root);
else if(Order==PostOrderTrav)
PostOrder(root);
}
void BST::PreOrder(Node *x) {
// Write your code here
}
void BST::InOrder(Node *x) {
// Write your code here
}
void BST::PostOrder(Node *x) {
// Write your code here
}
1 2 3 #include #include #include "BST . h" 5 using namespace std; 6 7 9 CONSTRUCTOR 10 Creates an empty binary tree 12-BST : :BST ( ) 13L} 14 { 16 DESTRUCTOR 17 18 19 BST:: BST () 20 2 // Write code to remove and deallocate all nodes in the tree *Free all memory used by current tree 23 24 25 26 void BST: :Insert (int toInsert) 27 28 29 L 1 30 31 void BST: :Delete (int toDelete) 32 33 // write your code here 34 L 35 36. void BST : : Transplant (Node u, Node *v) { 37 // write your code here 38 L 39 40 = Node *BST : : Successor (Node *x ) { 41 // write your code here 42 43 // Write your code here 44 H Node BST: :Minimum (Node( 45 Write your code here 46 L 47 48 Node *BST : :Maximum (Node *x) { 49 50L} Write your code here 51 52 Node BST: :Search (Node root, int key) 53 54 Write your code here 56Explanation / Answer
Below is your implementation: -
#include <iostream>
#include <string>
#include "BST.h"
using namespace std;
/****************************************************************
* CONSTRUCTOR #1
* Creates an binary tree
****************************************************************/
BST::BST() {
root = NULL;
}
/****************************************************************
* DECONSTRUCTOR
* Empty constructor
****************************************************************/
BST::~BST() {
}
void BST::Insert(int toInsert) {
Node* y = NULL;
Node* x = root;
Node* z = new Node();
z-> val = toInsert;
z->left = NULL;
z->right = NULL;
z->parent = NULL;
while(x != NULL) {
y = x;
if(toInsert < (x->val)) {
x = (x->left);
} else {
x = (x->right);
}
}
z->parent = y;
if(y == NULL) {
root = z;
}
else if(toInsert < (y->val)) {
y->left = z;
} else {
y->right = z;
}
}
void BST::Delete(int toDelete) {
Node* z = Search(toDelete);
Node* y;
if(z->left == NULL) {
Transplant(z, z->right);
}
else if (z->right == NULL) {
Transplant(z, z->left);
} else {
y = Minimum(z->right);
if(y->parent != z) {
Transplant(y,y->right);
y->right = z->right;
y->right->parent = y;
}
Transplant(z,y);
y->left = z->left;
y->left->parent = y;
}
}
void BST::Transplant(Node *u, Node *v) {
Node* z = root;
if(u->parent == NULL) {
root = v;
}
else if(u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
if(v != NULL) {
v->parent=u->parent;
}
}
Node *BST::Successor(Node *x) {
Node* y;
if(x->right == NULL) {
return Minimum(x->right);
}
y = x->parent;
while(y != NULL && x == (y->right)) {
x = y;
y = y->parent;
}
return y;
}
Node *BST::Minimum(Node *x) {
while(x->left != NULL) {
x = x->left;
}
return x;
}
Node *BST::Maximum(Node *x) {
while(x->right == NULL) {
x = x->right;
}
return x;
}
Node *BST::Search(int toFind) {
Node* temp = root;
while(temp != NULL && toFind != temp->val) {
if(temp->val > toFind) {
temp = temp->left;
} else {
temp = temp->right;
}
}
return temp;
}
void BST::Print(TraversalOrder Order)
{
if(Order==InOrderTrav)
InOrder(root);
else if(Order==PreOrderTrav)
PreOrder(root);
else if(Order==PostOrderTrav)
PostOrder(root);
}
void BST::PreOrder(Node *x) {
if(x != NULL) {
cout << x->val <<endl;
PreOrder(x->left);
PreOrder(x->right);
}
}
void BST::InOrder(Node *x) {
if(x != NULL) {
InOrder(x->left);
cout << x->val <<endl;
InOrder(x->right);
}
}
void BST::PostOrder(Node *x) {
if(x!= NULL) {
PostOrder(x->left);
PostOrder(x->right);
cout << x->val <<endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.