Iterator implementation for tree with 3 children in Java

Question

for university I should implement the Interface Iterator as an inner Class of the Tree with 3 Children. My Implementation of the tree looks like this:

import java.util.*;

public class TernaerTree <E> {

    private TernaerTree left;
    private TernaerTree right;
    private TernaerTree middle;
    private E value;

    public E getValue() {
        return value;
    }

    public TernaerTree(TernaerTree left, TernaerTree middle, TernaerTree right, E value) {
        this.left = left;
        this.right = right;
        this.middle = middle;
        this.value = value;
    }

    public static void main(String [] args){

        TernaerTree <String> baum = new TernaerTree<String>(new TernaerTree<String>(null,null,null,"Hallo"),new TernaerTree<String>(null,null,null,"Welt"),new TernaerTree<String>(null,null,null,"?"),"!");
    }

    public class WalkThroughIterator implements Iterator {

        @Override
        public boolean hasNext() {
        }

        @Override
        public Object next() {
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove() is not supported.");
        }

    }

}

Now I should implement the WalkthroughIterator. It should go through the tree with this order: left, middle, right and the node itself. The Iterator should use rekursive the Iterators of the subtrees.

In the mainmethod everything should be printed on screen.

Hopefully someone can help me.

Thanks, Tobias

Answer 1

This seems to work - it uses a list of iterator to keep track of the inner trees. Once all of them are exhaused it emits the element.

public class TernaerTree<E> implements Iterable<E> {

    private TernaerTree left;
    private TernaerTree middle;
    private TernaerTree right;
    private E value;

    public E getValue() {
        return value;
    }

    public TernaerTree(TernaerTree left, TernaerTree middle, TernaerTree right, E value) {
        this.left = left;
        this.middle = middle;
        this.right = right;
        this.value = value;
    }

    @Override
    public Iterator<E> iterator() {
        return new WalkThroughIterator();
    }

    public class WalkThroughIterator implements Iterator<E> {

        // All the iterators of all of the sub-trees that weren't null.
        List<Iterator<E>> iterators = new LinkedList<>();
        // Have we delivered the element?
        private boolean deliveredElement = false;

        public WalkThroughIterator() {
            // Is there a 'left' tree?
            if (left != null) {
                iterators.add(left.iterator());
            }
            // a middle
            if (middle != null) {
                iterators.add(middle.iterator());
            }
            // a right
            if (right != null) {
                iterators.add(right.iterator());
            }
        }

        @Override
        public boolean hasNext() {
            // we've finished if we've delivered the element.
            return !deliveredElement;
        }

        @Override
        public E next() {
            // First consume the iterators.
            while (iterators.size() > 0) {
                // Grab the first one.
                Iterator<E> it = iterators.get(0);
                // Has it got an entry?
                if (it.hasNext()) {
                    // Return it's next.
                    return it.next();
                } else {
                    // It's exhaused - remove it.
                    iterators.remove(it);
                }
            }
            // We now deliver our element.
            deliveredElement = true;
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove() is not supported.");
        }

    }

}

public void test() {
    TernaerTree<String> baum = new TernaerTree<String>(new TernaerTree<String>(null, null, null, "Hallo"), new TernaerTree<String>(null, null, null, "Welt"), new TernaerTree<String>(null, null, null, "?"), "!");
    for (String s : baum) {
        System.out.println(s);
    }
}

I have a feeling you have described your requirements wrong as I would expect the element to come out before the right branch but that's fixable.

Answer 2

Simplest way (and if you don't care much about complexity / performance), You can add a constructor and build a linear AST (for example, list) of the nodes in the order you desire recursively.

public class WalkThroughIterator implements Iterator {

    private List<E> values = new ArrayList<E>();
    private int currentElement = 0;

    public WalkThroughIterator(TernaerTree<E> tree) {
        buildList(tree);
    }

    private void buildList(TernaerTree<E> node) {

        if (node == null)
            return;

        buildList(node.left); //probably be best to add a getLeft() method etc
        buildList(node.middle);
        buildList(node.right);
        values.add(node.getValue());
    }

    @Override
    public boolean hasNext() {
        return (currentElement < values.size());
    }

    @Override
    public Object next() {
        return values.get(currentElement++);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("remove() is not supported.");
    }

}

Then just add a getIterator method to your tree object as such:

public WalkThroughIterator getIterator() {
       return new WalkThroughIterator(this);
}

Or simply instantiate a new WalkThroughIterator object with the root wherever.

(Btw, Note that if you have your object implement Iterable and then implement as suggested above, you could iterate over your tree with a for-each loop.)

Answer 3

I suggest you have TernaerTree implementing iterable. That'd make it much easier. You can return the WalkThroughIterator iterator in the iterator() that you'll be implementing for iterable. Much less clutter that way.

Then you can have all the basic functions of tree as part of TernaerTree.