CODEWITHSUNDEEP
javadata-structuresiteratorbinary-search-tree
Mountain
Mountain

Reputation: 61

Java - Binary Search Tree has a iterator() method, difficulty with implementing

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;
        }
    }
}

Upvotes: 1

Views: 3415

Answers (1)

Stephen C
Stephen C

Reputation: 718946

The DictNode class is an inner class. When you use it in another class, the inner class name must be qualified (with the name of the outer class) or imported.

Upvotes: 3

Related Questions