3

ツリーをトラバースする次のコードがあります（事前注文）：

public void traverse(Node node) {
    visit(node);
    for (Node child : node.getChildren()) {
        traverse(child);
    } 
}

段階的なトラバースを行いたいと思います。のようなものでIterator、別のアプリケーションになる可能性のあるクライアント (呼び出し元) がトラバースを制御できるようにします。(例: UI には「次へ」ボタンがあり、このボタンをクリックすると、次のノードに移動する必要があります)

私の現在の解決策は次のようなものです： 

List<Node> nodes = new ArrayList<Node>();
collectNodes(root, nodes);
Iterator<Node> it = nodes.iterator();
// do my job.
...

public void collectNodes(Node node, List<Node> nodes) {
    nodes.add(node);
    for (Node child : node.getChildren()) {
        collectNodes(child, nodes);
    } 
}

コードでわかるように、すべてのノード (collectNodes 内) にアクセスして、それらを収集し、予約注文形式のリストに入れています。

この余分な (collectNodes) 反復なしで解決策があるかどうか疑問に思っていましたか?

よろしく、モハマド

4

3 に答える 3

2

あなたが投稿したアルゴリズムの背後にある考え方は、メソッド スタックを暗黙的なデータ構造として使用することです。トラバースに入ると、すべてのノードが関数スタックに暗黙的にプッシュされ、それらを反復処理するとポップされます。

このアルゴリズムを反復子のように中断可能にするには、この暗黙的なスタックを明示的にするだけです。クラスにスタックを追加し、訪問時にすべての子をプッシュしてから、常にスタックの最上位ノードを使用して続行します。これはいつでも一時停止できますが、一時停止してどこにでも保存できる状態としてスタックを維持できます。

このトリックは、実際にはあらゆる種類の再帰アルゴリズムで機能します。

于 2012-05-24T09:47:28.407 に答える
0

メソッドが 2 つの引数を受け入れるcollectNodes(child)ため、コードでエラーが発生する場合、最後の行を考えませんか。collectNodes()

于 2015-09-17T06:36:13.397 に答える
-1

イテレータを使用してツリーをトラバーサルするためのコードは、ここで段階的に見つけることができます

これがあなたを助けることを願っています。

于 2012-05-24T05:56:36.630 に答える