Java Tree Struct & Breadth-first-search

Question

I created a simple parameterized tree structure, based on a root Node. Each node holds a arraylist of its childnotes and a link to its parent. Thats simple.

Now a problem that I'm not able to solve (in near future):

I want to write a breadth-first search over this tree. I want to implement this feature with the help of a (implemented) iterator interface. But I'm really unable to bring this to work: Problem is the also iterable List-structure. I don't know how to implement the hasNext(), next() and remove() functions :/

Do you have any idea?

Greetings

Code:

public class Tree<T> implements Iterator<T>{

private Node<T> root;

/**
 * Default constructor.
 */
public Tree() {
    super();        
}

/**
 * Return the root Node of the tree.
 * @return the root element.
 */    
public Node<T> getRoot() {
    return this.root;
}

/**
 * Set the root Element for the tree.
 * @param Root the root element to set.
 */
public void setRoot(Node<T> Root) {
    this.root = Root;
}
...

and

public class Node {

public List<Node<T>> children;
public Node<T> parent;
public T data;

/**
 * Default constructor.
 */
public Node() {
    super();
}

/**
 * Create a Node<T> with an instance of T.
 * @param data an instance of T.
 */
public Node(T nodeData) {
    this();
    setData(nodeData);        
}

/**
 * Create a Node<T> with an instance of T.
 * @param data an instance of T.
 */
public Node(T nodeData, Node<T> parentNode) {
    this();       

    setData(nodeData);
    setParent(parentNode); 

}
...

The tree should not implement Iterator<T>, it should implement Iterable<T>. The iterator then should be a separate class, an instance of which is returned by the Iterable.iterator() method. — Andreas Baus
– Andreas Baus, Commented Feb 8, 2012 at 14:17

amit · Accepted Answer · 2012-02-08 14:16:52Z

1

Your iterator() method will create an Iterator<Node<T>>, which will be initialized with a Queue<Node<T>> containing only the root.

Iterator.next() will take the first element from the stack, insert to the stack all its children and return it. [Don't forget to pop it as well]

Iterator.remove() will remove the last element from its parent's list of children [you can access the parent using your parent field.

Also note, syntactically, you should implement Iterable<T> and not Iterator<T>. The iterator you'll create [as described above] will implement Iterator<T>

answered Feb 8, 2012 at 14:16

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Robert Over a year ago

After the removal of a Node the Iterator might want to remove its children from the Queue though. But you cannot remove elements from the end of a Queue. You would either have to change Queue to Deque or use a second Queue to remember which Nodes you have to ignore.

user130076 · Accepted Answer · 2012-02-08 14:26:59Z

0

Your Node class needs to implement the Iterable interface and not the `Iterator' interface.

The Iterable interface essentially says 'this class can return an iterator and be iterated over', whereas the Iterator interface says 'I can iterate over something and return those items'. The Iterable interface requires an implementation of Iterator in order to work.

Here's a quick, contrived, example (not tested, but you should get the gist).

public class MyList implements Iterable<Integer> {

    public List<Integer> x;

    public Iterator<Integer> iterator() {
        return new MyListIterator(this);
    }

}

Here would be a simple iterator for that class:

public class MyListIterator implements Iterator<Integer> {

    private List<Integer> list;
    private int index;

    public MyListIterator(MyList list) {
        this.list = list;
        this.index = 0;
    }

    public boolean hasNext() {
        return this.index < this.list.x.size()
    }

    public Integer next() {
       Integer i = this.list.x.get(this.index);
       this.index += 1;
       return i;
    }

    public void remove() {
      //Not implemented
    }

}

It may help you to see how you would use an iterator explicitly:

MyList list = new MyList();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

answered Feb 8, 2012 at 14:26

user130076

2 Comments

John Rumpel Over a year ago

First, thanks a lot for the fast feedbacks and explanations! In my implementation wouldn't it be better to implement iterable over nodes instead of the tree? I am a little confused ...

user130076 Over a year ago

Yes, certainly. This example was meant to show how these interfaces work together, and not how you should implement them yourself. @amit describes the algorithm you need in your Iterator.

Collectives™ on Stack Overflow

Java Tree Struct & Breadth-first-search

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related