我正在尝试编写迭代器的实现，以便我可以在我的 BST 类中的 iterator() 方法下调用它。
我的解决方案（不确定它是否能正常工作）是使用堆栈或队列来存储 BST 的节点。麻烦的是，当我将“根”节点传递给它的构造函数时，我的迭代器实现类无法识别我的 BST 节点。
为了您的想象，这是我的 BST 实现，它适用于其他方法，包括添加、删除等。但我目前卡在该iterator()方法上。因为我不知道如何开始和做什么。
public class DictionaryImp<E extends Comparable<E>> implements Dictionary<E> {
public class DictNode {
public DictNode left;
public DictNode right;
public String position;
public E value;
public DictNode(E value, DictNode left, DictNode right, String position) {
this.left = left;
this.right = right;
this.position = position;
this.value = value;
}
}
public DictNode root;
//... more code
public Iterator<E> iterator() {
// provides a fail fast iterator for the Dictionary
// starting at the least element greater than or equal to start
Iterable<E> itr = new DictionaryItr<E>(root);
Iterator<E> it = itr.iterator();
return it;
}
}
这是我为 Iterator 实现写的
public class DictionaryItr<E> implements Iterable<E> {
public DictionaryItr(DictNode root) {
first = null;
this.inOrderTraversial(root);
}
public void inOrderTraversial(DictNode node) {
if (node != null) {
inOrderTraversial(node.left);
first.push(node.value);
inOrderTraversial(node.right);
}
}
// more code: push, peek, pop
public Iterator<E> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<E> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public E next() {
if (!hasNext()) throw new NoSuchElementException();
E item = current.item;
current = current.next;
return item;
}
}
}