Two problems here. When I try to traverse this home-grown binary tree using a "recursive iterator" (an iterator that traverses the tree recursively, puts the elements into a queue, and then removes the elements from the front of the queue). The iterator tends to iterate backwards (greatest to least) instead of inorder (least to greatest). Also, when I try to read user input from a Scanner using nextInt(), the program goes into an infinite loop. I'm trying to catch the InputMismatchException when the user inputs an invalid number.
In the below code segment, I'm catching the InputMismatchException when the user doesn't input a number so that the program continues normally.
Testing file:
package assignments.unit9;
import java.util.*;
import static java.lang.System.*;
import java.io.*;
public class BinaryTreeTest
{
private static BinaryTree<Item> tree;
static Scanner user;
public static void main(String... args)
{
user = new Scanner(System.in);
int choice;
do
{
out.println("1. Read data from disk");
out.println("2. Print the tree in order");
out.println("3. Search the tree");
out.println("4. Delete from the tree");
out.println("5. Count the nodes in the tree");
out.print("0. Quit\n>");
try
{
choice = user.nextInt();
}
catch(InputMismatchException e)
{
choice = -1;
}
switch(choice)
{
case 0:
exit(0);
case 1:
try
{
readFromDisk();
}
catch(FileNotFoundException e)
{
err.println("Sorry, but the file could not be opened: " + e.getMessage());
}
break;
case 2:
if(tree == null)
{
err.println("Must read file first");
break;
}
printTree();
break;
case 3:
if(tree == null)
{
err.println("Must read file first");
break;
}
searchTree();
break;
case 4:
if(tree == null)
{
err.println("Must read file first");
break;
}
// deleteFromTree();
break;
case 5:
if(tree == null)
{
err.println("Must read file first");
break;
}
countNodes();
break;
default:
err.println("Invalid choice. The available choices are:");
break;
}
}
while(choice != 0);
}
public static void readFromDisk() throws FileNotFoundException
{
Scanner file = new Scanner(new File("file20.txt"));
tree = new BinaryTree<Item>();
if(file.hasNextInt())
file.nextInt(); //skip the first integer
while(file.hasNextInt())
{
tree.add(new Item(file.nextInt(), file.nextInt()));
}
}
public static void printTree()
{
tree.inorder();
}
public static void searchTree()
{
out.println("Enter ID value to search for (-1 to return)");
int search;
Item searched;
while((search = user.nextInt()) != -1)
{
out.println(searched = tree.find(new Item(search, 0)));
if(searched == null)
out.println("\b\b\b\b\bNo such part in stock");
}
}
public static void countNodes()
{
out.println(tree.countNodes());
}
}
Here, in the BinaryTree class, I try to traverse it recursively (see iterator() and asQueue()):
package assignments.unit9;
import java.util.*;
public class BinaryTree<E extends Comparable<E>> implements Iterable<E>
{
private TreeNode<E> root;
public void add(E value)
{
if(root == null)
{
root = new TreeNode<E>(value);
}
else
{
TreeNode<E> temp = root, upFrom = null;
boolean goesOnLeft = false;
while(true)
{
if(temp == null)
{
if(goesOnLeft)
upFrom.setLeft(new TreeNode<E>(value));
else
upFrom.setRight(new TreeNode<E>(value));
break;
}
else if(temp.getValue().compareTo(value) < 0) //goes on left
{
upFrom = temp;
temp = upFrom.getLeft();
goesOnLeft = true;
continue;
}
else //goes on right
{
upFrom = temp;
temp = upFrom.getRight();
goesOnLeft = false;
continue;
}
}
}
}
public void inorder()
{
try
{
inorder(root);
}
catch(StackOverflowError e)
{
System.err.println("Increase stack size to print remaining elements");
}
}
private void inorder(TreeNode<E> t)
{
if(t == null)
return;
inorder(t.getLeft());
System.out.println(t.getValue());
inorder(t.getRight());
}
private ArrayDeque<E> asQueue(TreeNode<E> t, ArrayDeque<E> toAdd)
{
try
{
if(toAdd == null)
toAdd = new ArrayDeque<E>();
if(t == null)
return toAdd;
asQueue(t.getLeft(), toAdd);
toAdd.addLast(t.getValue());
asQueue(t.getRight(), toAdd);
ret:
return toAdd;
}
catch(StackOverflowError e)
{
throw new InternalError();
}
}
public Iterator<E> iterator()
{
return new Iterator<E>()
{
private ArrayDeque<E> d = asQueue(root, null);
public E next()
{
return d.pop();
}
public boolean hasNext()
{
return !d.isEmpty();
}
public void remove()
{
throw new UnsupportedOperationException();
}
};
}
public int countNodes()
{
int toReturn = 0;
for(E elem : this)
++toReturn;
return toReturn;
}
public E find(E toFind)
{
for(E elem : this)
{
if(elem.equals(toFind))
return elem;
}
return null;
}
}
TreeNode class:
package assignments.unit9;
import java.util.Objects;
public class TreeNode<T>
{
private T value;
private TreeNode<T> left, right;
/**
* Constructs a new TreeNode value with the left and right pointers {@code null}.
*
* @param value the item to be referenced
*
* @throws NullPointerException if {@code value} is {@code null}.
*/
public TreeNode(T value)
{
this.value = Objects.requireNonNull(value);
}
/**
* Constructs a new TreeNode value with the specified left and right pointers.
*
* @param value the item to be referenced
* @param left the TreeNode value to the left.
* @param right the TreeNode value to the right.
*
* @throws NullPointerException if {@code value} is {@code null}.
*/
public TreeNode(T value, TreeNode<T> left, TreeNode<T> right)
{
this.value = Objects.requireNonNull(value);
this.left = left;
this.right = right;
}
public T getValue()
{
return value;
}
public TreeNode<T> getLeft()
{
return left;
}
public TreeNode<T> getRight()
{
return right;
}
public void setValue(T value)
{
this.value = Objects.requireNonNull(value);
}
public void setLeft(TreeNode<T> left)
{
this.left = left;
}
public void setRight(TreeNode<T> right)
{
this.right = right;
}
}
Data type (Item):
package assignments.unit9;
import java.util.*;
public class Item implements Comparable<Item>
{
private int myID;
private int myInv;
//Comparators
public static class IDComparator implements Comparator<Item>
{
public int compare(Item i1, Item i2)
{
return i1.getID() - i2.getID();
}
@Override
public boolean equals(Object obj)
{
return obj instanceof IDComparator;
}
}
public static class InvComparator implements Comparator<Item>
{
public int compare(Item i1, Item i2)
{
return i1.getInv() - i2.getInv();
}
@Override
public boolean equals(Object obj)
{
return obj instanceof InvComparator;
}
}
public Item(int id, int inv)
{
myID = id;
myInv = inv;
}
public int getID()
{
return myID;
}
public int getInv()
{
return myInv;
}
public int compareTo(Item i)
{
if(i == null)
throw new NullPointerException();
return this.myID - i.myID;
}
@Override
public boolean equals(Object otherObject)
{
Item i;
try
{
i = (Item) otherObject;
return myID == i.myID;
}
catch(ClassCastException ex)
{
return false;
}
}
public String toString()
{
return "ID: " + myID + "\tInventory number: " + myInv + "\n";
}
@Override
public int hashCode()
{
return Objects.hash(myID, myInv);
}
}
And here's the input file. Sorry if that's a lot:
20
196 60
18618 64
2370 65
18410 56
18465 27
19967 45
17911 96
184 14
18871 69
14088 92
18061 3
206 31
13066 8
12705 14
15917 51
15814 60
15320 82
8303 90
7282 73
12328 63
Okay, problem solved. The thing is, I had typed a < when I needed a > and so I was ending up with the larger values on the left and the smaller values on the right, so my inorder traversal was backwards. Second, the infinite loop caused by catching InputMismatchException was a bug in the Scanner class:
in.nextInt() in
the try block. InputMismatchException, which diverts flow to the
catch block, which sets choice to -1 which causes the invalid
text block to be shown.nextInt() is called, it immediately throws an
exception instead of getting input, which can be seen if a print
statement is added to the catch block.
Thanks everyone who helped me on this.