Hi I am getting errors on my homework assignment BinarySearchTree.java:373: erro
ID: 3806103 • Letter: H
Question
Hi I am getting errors on my homework assignment
BinarySearchTree.java:373: error: incompatible types: Object cannot be converted to BinaryNode
BinaryNode temp=que.poll();
^
BinarySearchTree.java:388: error: bad operand types for binary operator '<'
if (k1 < t.element) {
^
first type: int
second type: AnyType
where AnyType is a type-variable:
AnyType extends Comparable<? super AnyType> declared in class BinarySearchTree
BinarySearchTree.java:392: error: bad operand types for binary operator '<='
if (k1 <= t.element && k2 >= t.element) {
^
first type: int
second type: AnyType
where AnyType is a type-variable:
AnyType extends Comparable<? super AnyType> declared in class BinarySearchTree
BinarySearchTree.java:392: error: bad operand types for binary operator '>='
if (k1 <= t.element && k2 >= t.element) {
^
first type: int
second type: AnyType
where AnyType is a type-variable:
AnyType extends Comparable<? super AnyType> declared in class BinarySearchTree
BinarySearchTree.java:396: error: cannot find symbol
if (k2 > t.data) {
^
symbol: variable data
location: variable t of type BinaryNode<AnyType>
where AnyType is a type-variable:
AnyType extends Comparable<? super AnyType> declared in class BinarySearchTree
Note: BinarySearchTree.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
5 errors
Can anyone help me resolve them?
// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException("");
return findMin( root ).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new UnderflowException("");
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<>( x, null, null );
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}
/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}
BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}
/** The tree root. */
private BinaryNode<AnyType> root;
// Test program
/***************************************************
* Program Title: BinarySearchTree *
* Author: Arrash Parvanehgohar *
* Class: CSCI3320, Spring 2017 *
* Assignment #2 *
****************************************************/
public static void main( String [ ] args )
{
BinarySearchTree<Integer> t = new BinarySearchTree<>( );
Scanner in = new Scanner(System.in);
// Create the array of Strings containing the main menu options (Quit - option 8)
// Create the mainMenu object
String opts[] = {"Exit program", "Construct a tree","Print tree in a descending order", "Print number of leaves in tree", "Print the number of nodes in T that contain only one child ",
"Print the number of nodes in T that contain only two children", "Print the level order traversal of the tree", "Print all elements in the tree between k1 and k2 ", };
Menu mainMenu = new Menu(opts);
int opt = 0;
do {
opt = mainMenu.runMenu();
switch (opt) {
case 1:
System.out.print ("How many numeric values do you want to enter? ");
int num = in.nextInt();
System.out.print ("Enter initial elements: ");
for (int i = 1; i <= num; i++){
t.insert (in.nextInt());
}
break;
case 2:
System.out.print(" Print in Descending order: ");
t.printTree();
System.out.println();
break;
case 3:
int leaves = t.numLeaves(t.root);
System.out.println("Number of leaves: " + leaves);
break;
case 4:
System.out.println("Number of nodes with one child: " + t.numOneChildNodes(t.root));
break;
case 5:
System.out.println("Number of nodes with two children: " + t.numTwoChildrenNodes(t.root));
break;
case 6:
System.out.print(" Print in level order: ");
t.levelOrder(t.root);
System.out.println();
break;
case 7:
System.out.print ("Enter two key numbers ");
int k1 = in.nextInt();
int k2 = in.nextInt();
System.out.printf(" Print between %d and %d: ", k1, k2);
t.printBetween(t.root, k1, k2);
System.out.println();
default:
System.out.println ("Thank you - Have a nice day!");
}
} while (opt != 0);
}
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
public void printTree(BinaryNode<AnyType> t) {
if (t==null) return;
printTree(t.right);
System.out.print (t.element + " ");
printTree(t.left);
}
public int numLeaves( BinaryNode<AnyType> t){
if (t==null)
return 0;
if (t.left == null && t.right == null)
return 1;
else
return numLeaves(t.left) + numLeaves(t.right);
}
public int numOneChildNodes( BinaryNode<AnyType> t){
if (t==null)
return 0;
int num = 0;
if ( onlyOneNull(t.left, t.right) ) {
num = 1;
}
return numOneChildNodes(t.left) + numOneChildNodes(t.right) + num;
}
private boolean onlyOneNull(BinaryNode<AnyType> node1, BinaryNode<AnyType> node2) {
return (node1 != null && node2 == null)
|| (node1 == null && node2 != null);
}
public int numTwoChildrenNodes ( BinaryNode<AnyType> t){
if (t==null)
return 0;
int Isfull = 0;
if (t.left != null && t.right != null)
Isfull = 1;
return Isfull + numTwoChildrenNodes(t.left) + numTwoChildrenNodes(t.right);
}
public void levelOrder(BinaryNode<AnyType> t){
Queue que =new LinkedList();
que.add(t);
while(!que.isEmpty())
{
BinaryNode temp=que.poll();
System.out.printf("%d ",temp.element);
if(temp.left!=null)
que.add(temp.left);
if(temp.right!=null)
que.add(temp.right);
}
}
public void printBetween(BinaryNode<AnyType> t, int k1, int k2) {
if (t == null) {
return;
}
if (k1 < t.element) {
printBetween(t.left, k1, k2);
}
if (k1 <= t.element && k2 >= t.element) {
System.out.print(t.element + " ");
}
if (k2 > t.data) {
printBetween(t.right, k1, k2);
}
}
}
Explanation / Answer
BinarySearchTree.java (I have addded my dummy implementation for Menu and UnderflowException to compile this)
// BinarySearchTree class
// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
* @throws UnderflowException
*/
public AnyType findMin( ) throws UnderflowException
{
if( isEmpty( ) )
throw new UnderflowException("");
return findMin( root ).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
* @throws UnderflowException
*/
public AnyType findMax( ) throws UnderflowException
{
if( isEmpty( ) )
throw new UnderflowException("");
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<>( x, null, null );
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}
/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}
BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}
/** The tree root. */
private BinaryNode<AnyType> root;
// Test program
/***************************************************
* Program Title: BinarySearchTree *
* Author: Arrash Parvanehgohar *
* Class: CSCI3320, Spring 2017 *
* Assignment #2 *
****************************************************/
public static void main( String [ ] args )
{
BinarySearchTree<Integer> t = new BinarySearchTree<>( );
Scanner in = new Scanner(System.in);
// Create the array of Strings containing the main menu options (Quit - option 8)
// Create the mainMenu object
String opts[] = {"Exit program", "Construct a tree","Print tree in a descending order", "Print number of leaves in tree", "Print the number of nodes in T that contain only one child ",
"Print the number of nodes in T that contain only two children", "Print the level order traversal of the tree", "Print all elements in the tree between k1 and k2 ", };
Menu mainMenu = new Menu(opts);
int opt = 0;
do {
opt = mainMenu.runMenu();
switch (opt) {
case 1:
System.out.print ("How many numeric values do you want to enter? ");
int num = in.nextInt();
System.out.print ("Enter initial elements: ");
for (int i = 1; i <= num; i++){
t.insert (in.nextInt());
}
break;
case 2:
System.out.print(" Print in Descending order: ");
t.printTree();
System.out.println();
break;
case 3:
int leaves = t.numLeaves(t.root);
System.out.println("Number of leaves: " + leaves);
break;
case 4:
System.out.println("Number of nodes with one child: " + t.numOneChildNodes(t.root));
break;
case 5:
System.out.println("Number of nodes with two children: " + t.numTwoChildrenNodes(t.root));
break;
case 6:
System.out.print(" Print in level order: ");
t.levelOrder(t.root);
System.out.println();
break;
case 7:
System.out.print ("Enter two key numbers ");
Integer k1 = in.nextInt();
Integer k2 = in.nextInt();
System.out.printf(" Print between %d and %d: ", k1, k2);
t.printBetween(t.root, k1, k2);
System.out.println();
default:
System.out.println ("Thank you - Have a nice day!");
}
} while (opt != 0);
}
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
public void printTree(BinaryNode<AnyType> t) {
if (t==null) return;
printTree(t.right);
System.out.print (t.element + " ");
printTree(t.left);
}
public int numLeaves( BinaryNode<AnyType> t){
if (t==null)
return 0;
if (t.left == null && t.right == null)
return 1;
else
return numLeaves(t.left) + numLeaves(t.right);
}
public int numOneChildNodes( BinaryNode<AnyType> t){
if (t==null)
return 0;
int num = 0;
if ( onlyOneNull(t.left, t.right) ) {
num = 1;
}
return numOneChildNodes(t.left) + numOneChildNodes(t.right) + num;
}
private boolean onlyOneNull(BinaryNode<AnyType> node1, BinaryNode<AnyType> node2) {
return (node1 != null && node2 == null)
|| (node1 == null && node2 != null);
}
public int numTwoChildrenNodes ( BinaryNode<AnyType> t){
if (t==null)
return 0;
int Isfull = 0;
if (t.left != null && t.right != null)
Isfull = 1;
return Isfull + numTwoChildrenNodes(t.left) + numTwoChildrenNodes(t.right);
}
public void levelOrder(BinaryNode<AnyType> t){
Queue que =new LinkedList();
que.add(t);
while(!que.isEmpty())
{
BinaryNode temp=(BinaryNode) que.poll();
System.out.printf("%d ",temp.element);
if(temp.left!=null)
que.add(temp.left);
if(temp.right!=null)
que.add(temp.right);
}
}
public void printBetween(BinaryNode<Integer> t, Integer k1, Integer k2) {
if (t == null) {
return;
}
if (k1 < t.element) {
printBetween(t.left, k1, k2);
}
if (k1 <= t.element && k2 >= t.element) {
System.out.print(t.element + " ");
}
if (k2 > (int)t.element) {
printBetween(t.right, k1, k2);
}
}
}
UnderflowException.java
public class UnderflowException extends Exception {
public UnderflowException(String message) {
super(message);
}
}
Menu.java
import java.util.Scanner;
public class Menu {
String[] opts;
Menu(String []opts)
{
this.opts = opts;
}
public int runMenu()
{
Scanner in = new Scanner(System.in);
for(int i = 0; i < opts.length; i++)
{
System.out.print("Enter " + i + " " + opts[i]);
}
return in.nextInt();
}
}