Answered: Code those parts only in c++ where it…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Code those parts only in c++ where it says "code here"

1. Implement the minimum method for binary search trees.

2. Implement the maximum method for binary search trees.

3. Implement the delete method for binary search trees. In the case where the node to be removed has two children, search the right subtree for a replacement value. Do not forget to update the size of the tree when appropriate (including for insertion).

4. Implement the in-order traversal method for binary search trees.

5. Implement the post-order traversal method for binary search trees.

Code is here BST.cpp

#include<iostream>

#include <vector>

#include <limits.h>

#include "BST.h"

using namespace std;

BST::BST()

{

***********code here**********

}

BST::~BST()

{

***********code here**********

}

//returns the address of the target node (if found)

Node* BST::search(int target)

{

returnsearch(root,target);

}

//method to search for target value in BST

//If node is not present we will return null

Node* BST::search(Node* n, int target)

{

//Tree is empty or value is not found

if (n == nullptr) //if root node is null just return null value

{

returnnullptr;

}

// Value is found

elseif (n->value == target)

{

returnn;

}

//If given valuen is not larger, traverse left.

elseif (n->value > target)

{

returnsearch(n->left, target);

}

//given value larger than current value, traverse right

elseif (n->value < target)

{

returnsearch(n->right, target);

}

//else if target is equal to root node just return the root node i.e n.

returnn;

}

Node* BST::minimum()

{

***********code here**********

}

Node* BST::minimum(Node* n)

{

***********code here**********

}

Node* BST::maximum()

{

***********code here**********

}

Node* BST::maximum(Node* n)

{

***********code here**********

}

Node* BST::insertValue(Node* n, int val)

{

//if root node is null

if (n == NULL) {

returnnewNode(val);

}

//if val<root's data insert in left half

if( n->value ==val) {

returnn;

}

//if val>root's data insert in right half

elseif (val > n->value) {

n->right = insertValue(n->right, val);

}

//if root's data is equal to val

elseif (val < n->value) {

n->left = insertValue(n->left, val);

}

//return the root node

returnn;

}

void BST::deleteValue(int val)

{

***********code here**********

}

Node* BST::deleteValue(Node* n, int val)

{

***********code here**********

}

//this function uses isBST(root,low,high) as helper function

//to check for binary search tree.

bool BST::isBST(Node* n){

//These low and high are the min. and max. permitted values

//for a particular node

returnisBST(n, INT_MIN, INT_MAX);

}

//Pass low as INT_MIN and high as INT_MAX because

//root of the tree can take any value.

bool BST::isBST(Node* n, int low, int high){

// if n is null , then it is tree

if (n == NULL)

returntrue;

// left child value greater then its root

// then it is not BST

if (n->left != NULL && n->left->value > n->value)

returnfalse;

// rightt child value less then its root

// then it is not BST

if (n->right != NULL && n->right->value < n->value)

returnfalse;

// recursive calling

return (isBST(n->left,low,high) || isBST(n->right, low, high));

}

//preOrder traversal method

void BST::preOrder(Node* n, vector<Node*> &order){

if (n)

{

// Root l R

order.push_back(n); // push node's address

preOrder(n->left, order); // Call on node->left i.e left subtree

preOrder(n->right, order); // Call on node->right i.e right subtree

}

void BST::inOrder(Node* n, vector<Node*> &order)

{

***********code here**********

}

void BST::postOrder(Node* n, vector<Node*> &order)

{

***********code here**********

}

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions