I have erros that need to be fixed: Thank you. I really appreciate it!!! Descrip
ID: 3825701 • Letter: I
Question
I have erros that need to be fixed:
Thank you. I really appreciate it!!!
Description Resource Path Location Type
The operator < is undefined for the argument type(s) support.Golfer, support.Golfer GolfApp2.java /project5/ch08 line 60 Java Problem - happens twice
Description Resource Path Location Type
The field BinarySearchTree.root is not visible GolfApp2.java /project5/ch08 line 32 Java Problem - happens 4 times
Description Resource Path Location Type
The operator && is undefined for the argument type(s) BSTNode, boolean BinarySearchTree.java /project5/ch08/trees line 155 Java Problem
What it is supposed to do:
modify GolfApp2
1st modifications
Write a client method that returns a count of the number of nodes in a binary search tree that contain a value less than or equal to the argument value. The signature of the method is
int countLess ( BinarySearchTree tree, Golfer maxValue )
answer:
int countLess ( BinarySearchTree tree, Golfer maxValue )
{
BSTNode maxNode = tree.root;
BSTNode minNode = tree.root;
int count = 0;
//Traverse Right Sub tree
while(maxNode!=null)
{
if( maxNode.getInfo() < maxValue){
count ++;
}
maxNode = maxNode.getRight();
}
//Traverse Left subtree
while(minNode!=null)
{
if( minNode.getInfo() < maxValue){
count ++;
}
minNode = minNode.getLeft();
}
return count;
}
2nd modification
Write 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 )
Answer:
Golfer min(BinarySearchTree tree) {
BSTNode minNode = tree.root;
if (minNode == null) {
return null;
}
while (minNode.getLeft() != null) {
minNode = minNode.getLeft();
}
return minNode.getInfo();
}
Write a client method that returns a reference to the information in the node with the “largest” value in a binary search tree. The signature of the method is
Golfer max( BinarySearchTree tree )
Answer:
Golfer min(BinarySearchTree tree) {
BSTNode maxNode = tree.root;
if (maxNode == null) {
return null;
}
while (maxNode.getRight() != null) {
maxNode = maxNode.getRight();
}
return maxNode.getInfo();
}
BinarySearchTree modifications
1st modification
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.
answer:
public BSTNode getRoot(){
if (root!=null){
return root;
}else{
return null;
}
}
2nd modification
Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree.
answer:
public int leafCount (BSTNode tree)
// Initializes preOrderQueue with tree elements in preOrder order.
{
// if current node is not null
if (tree != null) {
// if node is on leaf
if(tree.getLeft()==null && tree.getRight() == null) {
return 1;
} else {
// try to get count from the sub trees
return leafCount(tree.getLeft()) + leafCount(tree.getRight());
}
} else {
// for null node, count is 0
return 0;
}
}
3rd modification
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.
answer:
public int singleParentCount(BSTNode tree) {
if(tree == null)
return 0;
else {
if(tree.getLeft() != null && tree.getRight() == null) {
return 1 + singleParentCount(tree.getLeft());
}
if(tree.getLeft() == null && tree.getRight() != null) {
return 1 + singleParentCount(tree.getRight());
}
}
return 0;
}
4th modification
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 not have to contain the same values, but each node must have the same number of children.)
a) Write the declaration of the similarTrees method. Include adequate comments.
b) Write the body of the similarTrees method.
answer:
ADT : The functions takes two trees as input parameters and returns true if they are equal
private boolean similarTrees(BSTNode tree1, BSTNode tree2)
The code is as follows:
private boolean similarTrees(BSTNode tree1, BSTNode tree2)
{
while(tree1 != null && tree2 != null)
{
if(tree1.getInfo() != tree2.getInfo())
return false;
return similarTrees(tree1.getLeft(), tree2.getLeft() && similarTrees(tree1.getRight(), tree2.getRight()));
}
return tree1 == null && tree2 == null;
}
The code:
File Name: GolfApp2.java
//---------------------------------------------------------------------
// 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
{
//CountLess() method
public static int countLess ( BinarySearchTree tree, Golfer maxValue )
{
BSTNode maxNode = tree.root;
BSTNode minNode = tree.root;
int count = 0;
//Traverse Right Sub tree
while(maxNode!=null)
{
if( maxNode.getInfo() < maxValue)
{
count ++;
}
maxNode = maxNode.getRight();
}
//Traverse Left subtree
while(minNode!=null)
{
if( minNode.getInfo() < maxValue)
{
count ++;
}
minNode = minNode.getLeft();
}
return count;
}
//min() method
public static Golfer min(BinarySearchTree tree)
{
BSTNode minNode = tree.root;
if (minNode == null)
{
return null;
}
while (minNode.getLeft() != null)
{
minNode = minNode.getLeft();
}
return minNode.getInfo();
}
//max() method
public static Golfer max(BinarySearchTree tree)
{
BSTNode maxNode = tree.root;
if (maxNode == null)
{
return null;
}
while (maxNode.getRight() != null)
{
maxNode = maxNode.getRight();
}
return maxNode.getInfo();
}
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));
}
}
}
File Name: 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 root; // reference to the root of this BST
boolean found; // used by remove
// for traversals
protected LinkedUnbndQueue inOrderQueue; // queue of info
protected LinkedUnbndQueue preOrderQueue; // queue of info
protected LinkedUnbndQueue postOrderQueue; // queue of info
public BinarySearchTree()
// Creates an empty BST object.
{
root = null;
}
public BSTNode getRoot()
{
if (root!=null)
{
return root;
}
return null;
}
public int leafCount (BSTNode tree)
// Initializes preOrderQueue with tree elements in preOrder order.
{
// if current node is not null
if (tree != null)
{
// if node is on leaf
if(tree.getLeft()==null && tree.getRight() == null)
{
return 1;
}
else
{
// try to get count from the sub trees
return leafCount(tree.getLeft()) + leafCount(tree.getRight());
}
}
else
{
// for null node, count is 0
return 0;
}
}
public int singleParentCount(BSTNode tree)
{
if(tree == null)
return 0;
else
{
if(tree.getLeft() != null && tree.getRight() == null)
{
return 1 + singleParentCount(tree.getLeft());
}
if(tree.getLeft() == null && tree.getRight() != null)
{
return 1 + singleParentCount(tree.getRight());
}
}
return 0;
}
private boolean similarTrees(BSTNode tree1, BSTNode tree2)
{
while(tree1 != null && tree2 != null)
{
if(tree1.getInfo() != tree2.getInfo())
return false;
return similarTrees(tree1.getLeft(), tree2.getLeft() && similarTrees(tree1.getRight(), tree2.getRight()));
}
return tree1 == null && tree2 == null;
}
public boolean isEmpty()
// Returns true if this BST is empty; otherwise, returns false.
{
return (root == null);
}
private int recSize(BSTNode tree)
// 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> hold = new LinkedStack>();
BSTNode currNode;
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 tree)
// 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 tree)
// 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 recAdd(T element, BSTNode tree)
// Adds element to tree; tree retains its BST property.
{
if (tree == null)
// Addition place found
tree = new BSTNode(element);
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 tree)
// Returns the information held in the rightmost node in tree
{
while (tree.getRight() != null)
tree = tree.getRight();
return tree.getInfo();
}
private BSTNode removeNode(BSTNode tree)
// 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 recRemove(T element, BSTNode tree)
// 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 tree)
// 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 tree)
// 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 tree)
// 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;
}
}
Explanation / Answer
You are keeping Golfer objects in the Tree.. For that, your Golfer objects must be comparable.. They are not primitive datatype like integer or float, to which you can compare using < or > signs.. For object comparison, you need to implement comparator interface in your Golfer class.. then they will be comparable...
GolfApp2.java:
//---------------------------------------------------------------------
// GolfApp2.java by Dale/Joyce/Weems Chapter 8
import java.util.LinkedList;
import java.util.Queue;
//
// Allows user to enter golfer name and score information.
// Displays information ordered by score.
//----------------------------------------------------------------------
import java.util.Scanner;
public class GolfApp2 {
// CountLess() method
public static int countLess(BinarySearchTree<BSTNode> tree, Golfer maxValue) {
int count = 0;
BSTNode node;
Queue<BSTNode> nodeList = new LinkedList<BSTNode>();
nodeList.add(tree.root);
while(!nodeList.isEmpty()) {
node = nodeList.poll();
// check if current node is less
if(node.getInfo().compareTo(maxValue) <= 0) {
count++;
// if current node's value is less.. we may find something in right subtree also
if(node.getRight() != null) {
nodeList.add(node.getRight());
}
}
// traverse to check if something is possible in left subtree
if(node.getLeft() != null) {
nodeList.add(node.getLeft());
}
}
return count;
}
// min() method
public static Golfer min(BinarySearchTree<BSTNode> tree) {
BSTNode minNode = tree.root;
if (minNode == null) {
return null;
}
while (minNode.getLeft() != null) {
minNode = minNode.getLeft();
}
return minNode.getInfo();
}
// max() method
public static Golfer max(BinarySearchTree tree) {
BSTNode maxNode = tree.root;
if (maxNode == null) {
return null;
}
while (maxNode.getRight() != null) {
maxNode = maxNode.getRight();
}
return maxNode.getInfo();
}
public static void main(String[] args) {
Scanner conIn = new Scanner(System.in);
String name; // golfer's name
int score; // golfer's score
BinarySearchTree 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));
}
}
}
I have used the compareTo method, which comes from the comparable interface... Golfer class can be similar to below... I am just giving a very basic outstructure.. feel free to add functionality..
public class Golfer implements Comparable<Golfer>{
public Golfer(String name, int score) {
// TODO Auto-generated constructor stub
}
@Override
public int compareTo(Golfer other) {
// TODO Compare this golfer to the other golfer on
// basis of whatever parameter you have in the class
// like you may compare both on basis of their performance.
return 0;
}
}
Also, i have made some changes to your min() method.. Please check that.. i have used breadth first search to count.. In your method, you were counting the root node twice... Hope it helps!!>
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.