Implement the tree$-$balancing algorithm discussed in the lecture.

package BST;

import interfaces.BSTInterface;

import nodes.BSTNode;

import queues.$*$;

public class BinarySearchTree$>$

implements BSTInterface $\{$

protected BSTNode root;

boolean found;

protected LinkedQueue inOrderQueue;

protected LinkedQueue preOrderQueue;

protected LinkedQueue postOrderQueue;

public BinarySearchTree$()\{$

root $=$ null;

$\}$

public boolean isEmpty$()\{$

return$($root $==$ null$)$;

$\}$

@Override

public int size$()\{$

return recSize$($root$)$;

$\}$

private int recSize$($BSTNode tree$)\{$

if $($tree $==$ null$)$

return $0$;

else

return recSize$($tree$.$getLeft$())+$ recSize$($tree$.$getRight$())+1$;

$\}$

@Override

public boolean contains$($T element$)\{$

return recContains$($element$,$ root$)$;

$\}$

private boolean recContains$($T element, BSTNode tree$)\{$

if $($tree $==$ null$)$

return false;

else if $($element$.$compareTo$($tree$.$getInfo$())<0)$

return recContains$($element$,$ tree.getLeft$())$;

else if $($element$.$compareTo$($tree$.$getInfo$())>0)$

return recContains$($element$,$ tree.getRight$())$;

else

return true;

$\}$

private T recGet$($T element, BSTNode tree$)\{$

if $($tree $==$ null$)$

return null;

else if $($element$.$compareTo$($tree$.$getInfo$())<0)$

return recGet$($element$,$ tree.getLeft$())$;

else if $($element$.$compareTo$($tree$.$getInfo$())>0)$

return recGet$($element$,$ tree.getRight$())$;

else

return tree.getInfo$()$;

$\}$

public T get$($T element$)\{$

return recGet$($element$,$ root$)$;

$\}$

private BSTNode recAdd$($T element, BSTNode tree$)\{$

if $($tree $==$ null$)$

tree $=$ new BSTNode$($element$)$;

else if $($element$.$compareTo$($tree$.$getInfo$())<=0)$

tree.setLeft$($recAdd$($element$,$ tree.getLeft$()))$;

else

tree.setRight$($recAdd$($element$,$ tree.getRight$()))$;

return tree;

$\}$

public void add$($T element$)\{$

root $=$ recAdd$($element$,$ root$)$;

$\}$

public boolean remove$($T element$)\{$

root $=$ recRemove$($element$,$ root$)$;

return found;

$\}$

private BSTNode recRemove$($T element, BSTNode tree$)\{$

if $($tree $==$ null$)$

found $=$ false;

else if $($element$.$compareTo$($tree$.$getInfo$())<0)$

tree.setLeft$($recRemove$($element$,$ tree.getLeft$()))$;

else if $($element$.$compareTo$($tree$.$getInfo$())>0)$

tree.setRight$($recRemove$($element$,$ tree.getRight$()))$;

else $\{$

tree $=$ removeNode$($tree$)$;

found $=$ true;

$\}$

return tree;

$\}$

private BSTNode removeNode$($BSTNode tree$)\{$

T data;

if $($tree$.$getLeft$()==$ null$)$

return tree.getRight$()$;

else if $($tree$.$getRight$()==$ null$)$

return tree.getLeft$()$;

else $\{$

data $=$ getPredecessor$($tree$.$getLeft$())$;

tree.setInfo$($data$)$;

tree.setLeft$($recRemove$($data$,$ tree.getLeft$()))$;

return tree;

$\}$

$\}$

private T getPredecessor$($BSTNode tree$)\{$

while $($tree$.$getRight$()!=$ null$)$

tree $=$ tree.getRight$()$;

return tree.getInfo$()$;

$\}$

public int reset$($int orderType$)\{$

int numNodes $=$ size$()$;

if $($orderType $==$ INORDER$)\{$

inOrderQueue $=$ new LinkedQueue$()$;

inOrder$($root$)$;

$\}$

else if $($orderType $==$ PREORDER$)\{$

preOrderQueue $=$ new LinkedQueue$()$;

preOrder$($root$)$;

$\}$

if $($orderType $==$ POSTORDER$)\{$

postOrderQueue $=$ new LinkedQueue$()$;

postOrder$($root$)$;

$\}$

return numNodes;

$\}$

public T getNext$($int orderType$)\{$

if $($orderType $==$ INORDER$)$

return inOrderQueue.dequeue$()$;

else if $($orderType $==$ PREORDER$)$

return preOrderQueue.dequeue$()$;

else if $($orderType $==$ POSTORDER$)$

return postOrderQueue.dequeue$()$;

else

return null;

$\}$

private void inOrder$($BSTNode tree$)\{$

if $($tree $!=$ null$)\{$

inOrder$($tree$.$getLeft$())$;

inOrderQueue.enqueue$($tree$.$getInfo$())$;

inOrder$($tree$.$getRight$())$;

$\}$

$\}$

private void preOrder$($BSTNode tree$)\{$

if $($tree $!=$ null$)\{$

preOrderQueue.enqueue$($tree$.$getInfo$())$;

preOrder$($tree$.$getLeft$())$;

preOrder$($tree$.$getRight$())$;

$\}$

$\}$

private void postOrder$($BSTNode tree$)\{$

if $($tree $!=$ null$)\{$

postOrder$($tree$.$getLeft$())$;

postOrder$($tree$.$getRight$())$;

postOrderQueue.enqueue$($tree$.$getInfo$())$;

$\}$

$\}$

$\}$

package nodes;

public class BSTNode$>\{$

private T info;

private BSTNode left;

private BSTNode right;

public BSTNode$($T info$)\{$

this.info $=$ info;

left $=$ null;

right $=$ null;

$\}$

public void setInfo$($T info$)\{$

this.info $=$ info;

$\}$

public T getInfo$()\{$

return info;

$\}$

public void setLeft$($BSTNode link$)\{$

left $=$ link;

$\}$

public void setRight$($BSTNode link$)\{$

right $=$ link;

$\}$

public BSTNode getLeft$()\{$

return left;

$\}$

public BSTNode getRight$()\{$

return right;

$\}$

$\}$

package interfaces;

public interface BSTInterface$>\{$

static final int INORDER $=1$;

static final int PREORDER $=2$;

static final int POSTORDER $=3$;

boolean isEmpty$()$;

int size$()$;

boolean contains$($T element$)$;

boolean remove$($T element$)$;

T get$($T element$)$;

void add$($T element$)$;

int reset$($int orderType$)$;

T getNext

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

Below are questions with the answers attatched. Can you please put the answers(code) in the classes and spots it is supposed to be in, and I would like to know if the programs execute properly and it...

Q:

Extend the Binary Search Tree ADT to include a basic public method getRoot that returns a reference to the root of the tree. If the tree is empty, the method should return null. I am sure you will...

Q:

Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. please add the code in appropriate areas. Thank you...

Q:

Extend the Binary Search Tree ADT to include a public method singleParentCount that returns the number of nodes in the tree that have only one child. Please add the code in appropriate areas. Thank...

Q:

1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. 2) Extend the Binary Search Tree ADT to include a public method...

Q:

(In Java please) 1) modify BinarySearchTree to: a) Extend the Binary Search Tree ADT to include a basic public method getRoot that returns a reference to the root of the tree. If the tree is empty,...

Q:

HELP ASAP PLEASE Extend the Binary Search Tree ADT to include a basic public method getRoot that returns a reference to the root of the tree. if the tree is empty, the method should return null. be...

Q:

The Binary Search Tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are the same. (The nodes do...

Q:

The Binary Search Tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are the same. (The nodes do...

Q:

I need to finish a Binary Search Tree class in java.(Just need to finish some methods inside.) The name of the class is BinarySearchTree.java . I also have a BSTNode.java which creates the node in...

Q:

The temperature is maintained in the places near the sea and it is due to {fill_regular).

Q:

After its restructuring, ABC will be financed with 30% debt and 70% common equity. The return on assets is 10% and the return on debt is 8%. What is the cost of equity for the firm?

Q:

In this question, we will study Renee's incentives when it comes to reporting unobserved income to the tax authority. Renee works as a dance teacher. Some of her students pay her in cash at the end...

Q:

Which is a characteristic of a small group? It consists of three or more persons. Once formed, it is permanent. Its members have nothing in common. Its members have independent goals for the group to

Previous Question Next Question