實作Iterator<T>的DFS類

我想用我自己的節點為我自己的通用樹實作 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新手

uj5u.com熱心網友回復：

正如@Rogue在評論中所說，您的 Tree 應該實作 interface Iterable，即它需要覆寫iterator()方法，這意味著提供遍歷這棵樹的方法。

DFSAlgorithm反過來應該是一個Iterator，即MyTree.iterator()會回傳一個新的實體DFSAlgorithm。并且DFSAlgorithm需要Iterator通過重寫方法next()和實作介面的契約hasNext()。

有幾點需要注意：

• DFS()不需要方法。深度優先搜索演算法的邏輯應該體現在 and 的實作中next()（hasNext()順便說一下，方法名DFS()不符合 Java 命名約定）。

• 在 DFS 演算法中用作遍歷平均值的堆疊應該是迭代器實作的實體變數（無需像您所做的那樣創建堆疊的另一個實體并將其存盤在區域變數中）。在實體化迭代器時，應使用 Tree的根節點填充 Stack 。

• 欄位List<Node<T>> listOfChildren是多余的，在經典的 DFS 實作中不需要它，在這種情況下也是如此。只有一個堆疊就足以執行樹的遍歷。

• 類java.util.Stack是遺留的，不建議使用。相反，當您需要 Stack 資料結構的實作時，建議使用Deque介面的實作。

• 方法remove()有一個默認實作，它會拋出（這在語意上比在您的代碼中可以觀察到的UnsupportedOperationException更合適）。ConcurrentModificationException如果您不打算通過迭代器實作洗掉節點的功能，則無需重寫此方法。

• ConcurrentModificationException旨在防止在迭代程序中發生的結構修改（即影響資料結構大小的修改），這可能導致迭代不知道資料結構的實際狀態的情況。通常的做法是引入幾個修改計數器，并在呼叫開始時比較它們的值Iterator.next()。如果您想知道它是如何實作的，請查看來自 JDK 的標準集合。

這就是實作的樣子：

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

標籤：爪哇算法仿制药树迭代器

上一篇：使用推斷型別（有效的鍵型別）作為計算介面中的屬性名稱

下一篇：應根據輸入引數回傳不同型別的工廠