Question: modify GolfApp2 by writing a client method that returns a reference to the information in the node with the smallest value in a binary search
modify GolfApp2 by writing a client method that returns a reference to the information in the node with the "smallest" value in a binary search tree. The signature of the method is
Golfer min(BinarySearchTree tree)
//---------------------------------------------------------------------
// GolfApp2.java by Dale/Joyce/Weems Chapter 8
//
// Allows user to enter golfer name and score information.
// Displays information ordered by score.
//----------------------------------------------------------------------
import java.util.Scanner;
import ch08.trees.*;
import support.*; // Golfer
public class GolfApp2
{
public static void main(String[] args)
{
Scanner conIn = new Scanner(System.in);
String name; // golfer's name
int score; // golfer's score
BSTInterface golfers = new BinarySearchTree();
Golfer golfer;
int numGolfers;
String skip; // Used to skip rest of input line after reading integer
System.out.print("Golfer name (press Enter to end): ");
name = conIn.nextLine();
while (!name.equals(""))
{
System.out.print("Score: ");
score = conIn.nextInt();
skip = conIn.nextLine();
golfer = new Golfer(name, score);
golfers.add(golfer);
System.out.print("Golfer name (press Enter to end): ");
name = conIn.nextLine();
}
System.out.println();
System.out.println("The final results are");
numGolfers = golfers.reset(BinarySearchTree.INORDER);
for (int count = 1; count <= numGolfers; count++)
{
System.out.println(golfers.getNext(BinarySearchTree.INORDER));
}
}
}
BinarySearchTree.java
//----------------------------------------------------------------------------
// BinarySearchTree.java by Dale/Joyce/Weems Chapter 8
//
// Defines all constructs for a reference-based BST
//----------------------------------------------------------------------------
package ch08.trees;
import ch05.queues.*;
import ch03.stacks.*;
import support.BSTNode;
public class BinarySearchTree
implements BSTInterface
{
protected BSTNode
boolean found; // used by remove
// for traversals
protected LinkedUnbndQueue
protected LinkedUnbndQueue
protected LinkedUnbndQueue
public BinarySearchTree()
// Creates an empty BST object.
{
root = null;
}
public boolean isEmpty()
// Returns true if this BST is empty; otherwise, returns false.
{
return (root == null);
}
private int recSize(BSTNode
// Returns the number of elements in tree.
{
if (tree == null)
return 0;
else
return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
}
public int size()
// Returns the number of elements in this BST.
{
return recSize(root);
}
public int size2()
// Returns the number of elements in this BST.
{
int count = 0;
if (root != null)
{
LinkedStack
BSTNode
hold.push(root);
while (!hold.isEmpty())
{
currNode = hold.top();
hold.pop();
count++;
if (currNode.getLeft() != null)
hold.push(currNode.getLeft());
if (currNode.getRight() != null)
hold.push(currNode.getRight());
}
}
return count;
}
private boolean recContains(T element, BSTNode
// Returns true if tree contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
{
if (tree == null)
return false; // element is not found
else if (element.compareTo(tree.getInfo()) < 0)
return recContains(element, tree.getLeft()); // Search left subtree
else if (element.compareTo(tree.getInfo()) > 0)
return recContains(element, tree.getRight()); // Search right subtree
else
return true; // element is found
}
public boolean contains (T element)
// Returns true if this BST contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
{
return recContains(element, root);
}
private T recGet(T element, BSTNode
// Returns an element e from tree such that e.compareTo(element) == 0;
// if no such element exists, returns null.
{
if (tree == null)
return null; // element is not found
else if (element.compareTo(tree.getInfo()) < 0)
return recGet(element, tree.getLeft()); // get from left subtree
else
if (element.compareTo(tree.getInfo()) > 0)
return recGet(element, tree.getRight()); // get from right subtree
else
return tree.getInfo(); // element is found
}
public T get(T element)
// Returns an element e from this BST such that e.compareTo(element) == 0;
// if no such element exists, returns null.
{
return recGet(element, root);
}
private BSTNode
// Adds element to tree; tree retains its BST property.
{
if (tree == null)
// Addition place found
tree = new BSTNode
else if (element.compareTo(tree.getInfo()) <= 0)
tree.setLeft(recAdd(element, tree.getLeft())); // Add in left subtree
else
tree.setRight(recAdd(element, tree.getRight())); // Add in right subtree
return tree;
}
public void add (T element)
// Adds element to this BST. The tree retains its BST property.
{
root = recAdd(element, root);
}
private T getPredecessor(BSTNode
// Returns the information held in the rightmost node in tree
{
while (tree.getRight() != null)
tree = tree.getRight();
return tree.getInfo();
}
private BSTNode
// Removes the information at the node referenced by tree.
// The user's data in the node referenced by tree is no
// longer in the tree. If tree is a leaf node or has only
// a non-null child pointer, the node pointed to by tree is
// removed; otherwise, the user's data is replaced by its
// logical predecessor and the predecessor's node is removed.
{
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 BSTNode
// Removes an element e from tree such that e.compareTo(element) == 0
// and returns true; if no such element exists, returns false.
{
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;
}
public boolean remove (T element)
// Removes an element e from this BST such that e.compareTo(element) == 0
// and returns true; if no such element exists, returns false.
{
root = recRemove(element, root);
return found;
}
private void inOrder(BSTNode
// Initializes inOrderQueue with tree elements in inOrder order.
{
if (tree != null)
{
inOrder(tree.getLeft());
inOrderQueue.enqueue(tree.getInfo());
inOrder(tree.getRight());
}
}
private void preOrder(BSTNode
// Initializes preOrderQueue with tree elements in preOrder order.
{
if (tree != null)
{
preOrderQueue.enqueue(tree.getInfo());
preOrder(tree.getLeft());
preOrder(tree.getRight());
}
}
private void postOrder(BSTNode
// Initializes postOrderQueue with tree elements in postOrder order.
{
if (tree != null)
{
postOrder(tree.getLeft());
postOrder(tree.getRight());
postOrderQueue.enqueue(tree.getInfo());
}
}
public int reset(int orderType)
// Initializes current position for an iteration through this BST
// in orderType order. Returns current number of nodes in the BST.
{
int numNodes = size();
if (orderType == INORDER)
{
inOrderQueue = new LinkedUnbndQueue
inOrder(root);
}
else
if (orderType == PREORDER)
{
preOrderQueue = new LinkedUnbndQueue
preOrder(root);
}
if (orderType == POSTORDER)
{
postOrderQueue = new LinkedUnbndQueue
postOrder(root);
}
return numNodes;
}
public T getNext (int orderType)
// Preconditions: The BST is not empty
// The BST has been reset for orderType
// The BST has not been modified since the most recent reset
// The end of orderType iteration has not been reached
//
// Returns the element at the current position on this BST for orderType
// and advances the value of the current position based on the orderType.
{
if (orderType == INORDER)
return inOrderQueue.dequeue();
else
if (orderType == PREORDER)
return preOrderQueue.dequeue();
else
if (orderType == POSTORDER)
return postOrderQueue.dequeue();
else return null;
}
}
BSTInterface.java
//----------------------------------------------------------------------------
// BSTInterface.java by Dale/Joyce/Weems Chapter 8
//
// Interface for a class that implements a binary search tree (BST).
//
// The trees are unbounded and allow duplicate elements, but do not allow null
// elements. As a general precondition, null elements are not passed as
// arguments to any of the methods.
//
// The tree supports iteration through its elements in INORDER, PREORDER,
// and POSTORDER.
//----------------------------------------------------------------------------
package ch08.trees;
public interface BSTInterface
{
// used to specify traversal order
static final int INORDER = 1;
static final int PREORDER = 2;
static final int POSTORDER = 3;
boolean isEmpty();
// Returns true if this BST is empty; otherwise, returns false.
int size();
// Returns the number of elements in this BST.
boolean contains (T element);
// Returns true if this BST contains an element e such that
// e.compareTo(element) == 0; otherwise, returns false.
boolean remove (T element);
// Removes an element e from this BST such that e.compareTo(element) == 0
// and returns true; if no such element exists, returns false.
T get(T element);
// Returns an element e from this BST such that e.compareTo(element) == 0;
// if no such element exists, returns null.
void add (T element);
// Adds element to this BST. The tree retains its BST property.
int reset(int orderType);
// Initializes current position for an iteration through this BST
// in orderType order. Returns current number of nodes in the BST.
T getNext (int orderType);
// Preconditions: The BST is not empty
// The BST has been reset for orderType
// The BST has not been modified since the most recent reset
// The end of orderType iteration has not been reached
//
// Returns the element at the current position on this BST for orderType
// and advances the value of the current position based on the orderType.
}
Golfer.java
//----------------------------------------------------------------------
// Golfer.java by Dale/Joyce/Weems Chapter 6
//
// Supports golfer objects having a name and a score.
// Allows golfers to be compared based on their scores.
//----------------------------------------------------------------------
package support;
public class Golfer implements Comparable
{
protected String name;
protected int score;
public Golfer(String name, int score)
{
this.name = name;
this.score = score;
}
public String getName()
{
return name;
}
public int getScore()
{
return score;
}
public int compareTo(Golfer other)
{
if (this.score < other.score)
return -1;
else
if (this.score == other.score)
return 0;
else
return +1;
}
public String toString()
{
return (score + ": " + name);
}
}
Thank you. please add the code where it is needed
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help