28

バイナリ ツリーのルートを取得し、バイナリ ツリーのノードを順番nextに繰り返す Java イテレータ (つまりandメソッドが必要) を作成するにはどうすればよいですか?hasNext

4

3 に答える 3

45

サブツリーの最初の要素は常に左端の要素です。要素の次の要素は、その右側のサブツリーの最初の要素です。要素に適切な子がない場合、次の要素は要素の最初の適切な祖先です。要素に適切な子も適切な祖先もない場合、それは右端の要素であり、反復の最後になります。

私のコードが人間が読める形式であり、すべてのケースをカバーしていることを願っています。

public class TreeIterator {
    private Node next;

    public TreeIterator(Node root) {
        next = root;
        if(next == null)
            return;

        while (next.left != null)
           next = next.left;
    }

    public boolean hasNext(){
        return next != null;
    }

    public Node next(){
        if(!hasNext()) throw new NoSuchElementException();
        Node r = next;

        // If you can walk right, walk right, then fully left.
        // otherwise, walk up until you come from left.
        if(next.right != null) {
            next = next.right;
            while (next.left != null)
                next = next.left;
            return r;
        }

        while(true) {
            if(next.parent == null) {
                next = null;
                return r;
            }
            if(next.parent.left == next) {
                next = next.parent;
               return r;
            }
            next = next.parent;
        }
     }
 }

次のツリーについて考えてみます。

     d
   /   \
  b     f
 / \   / \
a   c e   g
  • 最初の要素は「ルートから完全に離れている」
  • a右の子がいないので、次の要素は「左から来るまで」です。
  • b正しい子がありますので、bの正しいサブツリーを繰り返します
  • c正しい子供がいません。親はb、トラバースされたです。次の親はd、トラバースされていないので、ここで停止します。
  • d正しいサブツリーがあります。その左端の要素はeです。
  • ..。
  • g正しいサブツリーがないので、上に歩いてください。f私たちは右から来たので、訪問されました。d訪問されました。d親がいないので、それ以上上に移動することはできません。右端のノードから来て、反復が完了しました。
于 2012-10-12T02:33:47.337 に答える
3

イテレータの次のエントリ'nextEntry（）'を取得するために、java.util.TreeMap以下に貼り付けたスニペットを確認しました。平易な英語では、最初にルートノードがnullでないことを確認してください。そうでない場合は、nullを返します。そうでない場合は、nullでない場合は右側のノードをビストします。次に、左側（nullでない場合）にアクセスし、nullに達するまでwhileループでその左側に繰り返しアクセスします。元の右ノードがnullの場合、それがnullでない場合は、そのすべてではなく、親ノードにアクセスします。次に、親がnullになるか、現在アクセスしているノードの右（子）ノードが最後の位置と等しくなるまで、親をビストするwhileループに入ります。次に、座っているエントリを返します。これらすべてのオプションが失敗した場合は、（元の）ルートノードを返します。'HasNext（）'は、この「次のエントリ」かどうかをチェックするだけです

public final boolean hasNext() {
     return next != null;
}

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
于 2012-10-12T02:31:34.077 に答える
-2

順序通りのトラバーサルでは、左の子がある場合はそこにアクセスし、次にルート ノード、次に右の子にアクセスします。

visit_node(node)
   if node.left: visit_node(node.left)
   // visit the root node
   if node.right: visit_node(node.right)

図:

     a 
   /   \        (in-order traversal would give bac)
  b     c
于 2012-10-12T01:14:53.097 に答える