I'm trying to write an implementation of iterator so that I can call it within my BST class, under iterator() method.
My solution (not sure if it would work correctly) is to use a stack or a queue to store the nodes of the BST. Trouble is, my Iterator Implementation class can't recognise my BST nodes when I pass the "root" node into its constructor.
For your ease of imagination, this is my BST implementation, it works fine for other methods including add, delete, etc. But I'm currently stuck at the iterator() method. Since I have no idea how to start and what to do.
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;
}
}
This is what I wrote for the Iterator implementation
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;
}
}
}
DictNode rootTreeSet