Screen Shot 2018-07-29 at 3.18.30 PM Objective: To create a node for a binary se
ID: 3918990 • Letter: S
Question
Screen Shot 2018-07-29 at 3.18.30 PM Objective: To create a node for a binary search tree (BSTNodecE>) and to create a binary search tree of comparable objects (Tree) BSTNode might need: public class BSTNodecE extends ComparablecE>> BSTNodecE> -data:E -left: BSTNode +BSTNode (newData:E, newLeft: BSTNode newRight: BSTNode) +getData()E +getLeft():BSTNodecE +getRight(:BSTNodecE> +getRightMostDatal):E +inorderPrint:void +removeRightmost(): BSTNodecE> needed for remove algorithm covered in class +setData(newData:E):void +setLeft(newleft: BSTNode):void +setRight(newRight: BSTNode):void ? needed for remove algorithm covered in class 1 code for these two methods are in the book 2 code for this method is on the slides Tree public class TreecE extends Comparable Tree E> -root: BSTNodecE> numltems:int +Tree) +add(element:E):void +remove(element:E):boolean +size():int +printTree0:void ' Pseudo code for this method is on the slides - instructor wrote this on the board and the recursive add method in BSTNode 4 You could implement a "stub" for remove() and then run the testers to test the add. public boolean remove(E target ) return false; s will do a root.inorderPrint() if root is not nullExplanation / Answer
//BSTNode.java
package com.src;
import com.src.Tree;;
public class BSTNode<E extends Comparable<E>> implements Comparable<E> {
private E data;
private BSTNode<E> left;
private BSTNode<E> right;
public BSTNode(E data, BSTNode<E> left, BSTNode<E> right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
public E getData() {
return data;
}
public BSTNode<E> getLeft() {
return left;
}
public BSTNode<E> getRight() {
return right;
}
public void setData(E data) {
this.data = data;
}
public void setLeft(BSTNode<E> left) {
this.left = left;
}
public void setRight(BSTNode<E> right) {
this.right = right;
}
public E getRightMostData() {
BSTNode<E> curr = this;
if(curr == null)
return null;
while(curr.right != null) {
curr = curr.right;
}
return curr.data;
}
private void printInorder(BSTNode<E> node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
public void inorderPrint() {
printInorder(this);
}
BSTNode<E> deleteKey(E e)
{
return deleteRec(this, e);
}
@Override
public int compareTo(E o) {
return this.compareTo(o);
}
/* A recursive function to insert a new key in BST */
BSTNode<E> deleteRec(BSTNode<E> root, E key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key.compareTo(root.data) > 0)
root.left = deleteRec(root.left, key);
else if (key.compareTo(root.data) < 0 )
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.data = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.data);
}
return root;
}
E minValue(BSTNode<E> root)
{
E minv = root.data;
while (root.left != null)
{
minv = root.left.data;
root = root.left;
}
return minv;
}
public BSTNode<E> removeRightMost(){
return deleteKey(getRightMostData());
}
}
//Tree.java
package com.src;
public class Tree<E extends Comparable<E>> {
private BSTNode<E> root;
private int numItems;
public Tree() {
root = null;
numItems=0;
}
public void add(E element) {
root = insertRec(root, element);
}
BSTNode<E> insertRec(BSTNode<E> root, E key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new BSTNode<E>(key, null, null);
return root;
}
/* Otherwise, recur down the tree */
if (key.compareTo(root.getData()) > 0)
root.setLeft(insertRec(root.getLeft(), key));
else if (key.compareTo(root.getData()) < 0 )
root.setRight(insertRec(root.getRight(), key));
return root;
}
public boolean remove(E element) {
return false;
}
public int size() {
return numItems;
}
public void printTree() {
if(root != null)
root.inorderPrint();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.