I want to realize DFS for my own generic tree with my own nodes. Nodes have this fields

private T value;
private final List<Node<T>> listOfChildren;

And Tree.class has only Node root field. My DFS realization is working fine, but it's my first work with iterator and I don't understand how I should @Override methods.

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class DFSAlgorithm<T> implements Iterator<T> {
    private final Stack<Iterator<T>> stack = new Stack<>();

    private List<Node<T>> listOfChildren;

    public void DFS(Node<T> vertex) {
        System.out.println("DFS start");
        Stack<Node<T>> stack = new Stack<>();
        stack.push(vertex);
        while (!stack.isEmpty()) {
            Node<T> node = stack.pop();
            System.out.println(node.getValue());
            for (Node<T> tNode : node.getListOfChildren()) {
                stack.push(tNode);
            }
        }
    }

    @Override
    public void remove() {
        throw new ConcurrentModificationException();
    }

    @Override
    public boolean hasNext() {
        return this.listOfChildren != null;
    }

    @Override
    public T next() {
        return null;
    }


}

My Node.class

import java.util.ArrayList;
import java.util.List;

public class Node<T> {
    private T value;
    private final List<Node<T>> listOfChildren;

    public Node(){
        super();
        listOfChildren = new ArrayList<Node<T>>();
    }

    public Node(T value){
        this();
        setValue(value);
    }

    public T getValue() {
        return value;
    }

    public List<Node<T>> getListOfChildren() {
        return listOfChildren;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public int getNumberOfChildren() {
        return listOfChildren.size();
    }

    public void addChildren(Node<T> child) {
        listOfChildren.add(child);
    }
}

I don't understand where I should write Node and where I should write Iterable. Should I write this methods for stack in DFS or for Tree? Can you explain this, please, I'm new in java

CodePudding user response：

As @Rogue has said in the comments, your Tree should implement interface Iterable, i.e. it needs to override iterator() method, which is meant to provide a mean of traversal over this tree.

DFSAlgorithm in turn should be an Iterator, i.e. MyTree.iterator() would return a new instance of DFSAlgorithm. And DFSAlgorithm needs to implement the contract of the Iterator interface by overriding methods next() and hasNext().

There's a few things to note:

• Method DFS() is not needed. The logic of Depth first search algorithm should be reflected in the implementations of next() and hasNext() (by the way, method name DFS() is not aligned with Java naming conventions).

• A Stack, which is used a mean of traversal in DFS algorithm, should be an instance variable of the iterator implementation (no need to create another instantiate of the stack as you've done and store it in a local variable). And Stack should be populated with the root-node of the Tree while instantiating the iterator.

• Field List<Node<T>> listOfChildren is redundant, it's not required in the classic DFS implementation and in this case as well. Having only a Stack is sufficient to perform traversal of a Tree.

• Class java.util.Stack is legacy and not recommenced to be used. Instead, when you need an implementation of the Stack data structure, it's advisable to utilize implementations of the Deque interface.

• Method remove() has a default implementation which throws UnsupportedOperationException (which is semantically more suitable, than ConcurrentModificationException that can be observed in your code). If you're not going to implement the functionality for removing nodes by the means of iterator, there's no need to override this method.

• ConcurrentModificationException is meant to guard against structural modifications (i.e. modifications that affect the size of the data structure) that happen during the iteration process, which can lead to the situation when iteration is unaware of the actual state of the data structure. The common practice is to introduce a couple of modification counters and compare their values at the very beginning of the call Iterator.next(). If you wonder how it might be implemented, have a look at the standard Collections from JDK.

That's how the implementation might look like:

public class MyTree<T> implements Iterable<T> {
    
    private Node<T> root;
    
    // constructor of the Tree, etc.
    
    @Override
    public Iterator<T> iterator() {
        return new DFSAlgorithm<>(root);
    }
    
    public class DFSAlgorithm<T> implements Iterator<T> {
        
        private final Deque<Node<T>> stack = new ArrayDeque<>();
    
        public DFSAlgorithm(Node<T> vertex) {
            this.stack.push(vertex);
        }
        
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }
        
        @Override
        public T next() {
            Node<T> next = stack.pop();
            
            for (Node<T> tNode: next.getListOfChildren()) {
                stack.push(tNode);
            }
            
            return next.getValue();
        }
    }
    
    public class Node<T> {
        // you code without changes here
    }
}