0
这里有两个问题。当我尝试使用“递归迭代器”（递归遍历树的迭代器，将元素放入队列中，然后从队列前端移除元素）来遍历这个自制的二叉树时。迭代器倾向于向后迭代（最大到最小）而不是inorder（从最小到最大）。另外，当我尝试使用nextInt()从Scanner读取用户输入时，程序进入无限循环。当用户输入一个无效的号码时，我试图抓住InputMismatchException。
在下面的代码段中，当用户没有输入数字以便程序正常继续时，我正在捕获InputMismatchException。
测试文件：从循环中的扫描仪读取时，会进入无限循环
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());
}
}
这里，在二叉树类，我尝试递归遍历（参见迭代器（）和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;
}
}
树节点类：
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;
}
}
数据类型（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);
}
}
这里是输入文件。很抱歉，如果这是一个很大：
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
当您输入'0'作为输入时，您的程序是否退出？ – 2013-03-11 18:09:33