バイナリ検索ツリーイテレータ - イン/プレ/ポストオーダー

Question

私はクラスBinarySearchTreeに2つのデータ要素、Node rootとint sizeを持っています。 Nodeクラスは、4つのデータ要素Node left, right, upとint dataを持っています。

コンストラクタがどのタイプのトラバーサルを使用するのかを示すIteratorクラスを作成したいとします。 nextが呼び出されたときにのみ、次の要素を反復処理します。

MyIteratorに含まれるデータ要素は、これが乱雑にならないようにする必要がありますか？私はおそらくStack<Node>を持っていると思っているが、それは本当に悪い解決策のように感じる。可能なモードの3つすべてをカバーするために私ができることは何も賢いことはありますか？イテレータの内部に追加のデータ構造（キュー/スタック/マップ）を持たずにこれを行う方法はありますか？

public class MyIterator 
{ 
    private BinarySearchTree tree; 
    private Node current; 
    private int mode; 

    public MyIterator(BinarySearchTree tree, int mode) 
    { 
     // mode = 1 -> IN ORDER TRAVERSAL 
     // mode = 2 -> PREORDER TRAVERSAL 
     // mode = 3 -> POSTORDER TRAVERSAL 

     this.tree = tree; 
     this.mode = mode; 
    } 

    public boolean hasNext() 
    { 
     ... 
    } 

    public void next() 
    { 
     ... 
    } 
} 

Answer 1

Morris Inorder Treeトラバーサルとそのバリエーションは、私が探していた構造/アルゴリズムです。

Answer 2

あなたの問題は戦略パターンのユースケースのように聞こえます。あなたのイテレータのコンストラクタは、平文の代わりにModeStrategyをパラメータとして使用し、の代わりにを取得する必要があります。戦略はクラス属性に格納されます。

public interface ModeStrategy { 
    boolean hasNext(BinarySearchTree tree, Node current); 
    void next(BinarySearchTree tree, Node current); 
} 

public class MyIterator { 
    private final ModeStrategy mode; 
    // other fields omitted 
    public MyIterator(BinarySearchTree tree, ModeStrategy mode) { 
     this.mode = mode; 
    } 
    // your methods delegate to mode 
} 

Answer 3

最良のオプションは、工場出荷時のパターンを紹介し、独自のIterator Sに実装を分割するようになります：ModeStrategyはこのような何かを探しているインターフェースである可能性があります。

final class IteratorFactory { 
    enum Mode { 
    IN_ORDER, PRE_ORDER, POST_ORDER; 
    } 

    private IteratorFactory() { 
    } 

    public static <T> Iterator<T> get(Mode mode, BinarySearchTree<T> tree) { 
    Objects.requireNonNull(mode); 
    Objects.requireNonNull(tree); 
    switch(mode) { 
     case IN_ORDER: return new InOrderIterator<T>(tree); 
     case PRE_ORDER: return new PreOrderIterator<>(tree); 
     case POST_ORDER: return new PostOrderIterator<>(tree); 
     default: throw new AssertionError("Can't happen"); 
    } 
    } 

    private static class InOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
    private static class PreOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
    private static class PostOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
}