我想用自己的节点为自己的通用树实现DFS。节点具有此字段
private T value;
private final List<Node<T>> listOfChildren;
Tree.class只有Node根字段。我的DFS实现工作得很好，但这是我第一次使用迭代器，我不明白应该如何@Override方法。
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;
}
}
我的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);
}
}
我不明白我应该在哪里写Node，在哪里写Iterable。我应该为DFS中的堆栈或Tree编写此方法吗？你能解释一下吗，我是java 的新手
正如@Rogue在评论中所说，您的树应该实现接口Iterable，即它需要覆盖iterator()方法，该方法旨在提供遍历该树的方法。
DFSAlgorithm反过来应该是Iterator，即MyTree.iterator()将返回DFSAlgorithm的新实例。DFSAlgorithm需要通过重写方法next()和hasNext()来实现Iterator接口的契约。
有几件事需要注意：
-
不需要方法
DFS()。深度优先搜索算法的逻辑应该反映在next()和hasNext()的实现中(顺便说一句，方法名称DFS()与Java命名约定不一致(。 -
Stack是DFS算法中的遍历手段，它应该是迭代器实现的实例变量(不需要像您所做的那样创建另一个堆栈实例并将其存储在本地变量中(。在实例化迭代器时，Stack应该填充Tree的根节点。
-
字段
List<Node<T>> listOfChildren是多余的，它在经典的DFS实现中是不需要的，在这种情况下也是如此。只有一个Stack就足以执行树的遍历。 -
java.util.Stack类是遗留的，不建议使用。相反，当您需要Stack数据结构的实现时，建议使用Deque接口的实现。 -
方法
remove()有一个默认实现，它抛出UnsupportedOperationException(在语义上比代码中可以观察到的ConcurrentModificationException更合适(。如果您不打算通过迭代器来实现删除节点的功能，则无需重写此方法。 -
ConcurrentModificationException旨在防止迭代过程中发生的结构修改(即影响数据结构大小的修改(，这可能导致迭代不知道数据结构的实际状态。通常的做法是引入几个修改计数器，并在调用Iterator.next()的一开始比较它们的值。如果您想知道它是如何实现的，请查看JDK中的标准Collections。
这就是实现的样子：
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
}
}