10

私は木にかなり慣れていないので、一種の「葉のイテレータ」を作成しようとしています。.leftと値を持たないすべてのノードを.rightスタックに配置する必要があると思いますが、それが正しい方法であるかどうかはわかりません。私はそれを検索しようとしましたが、私が出くわすすべての例は、左端のリーフに移動し、次に移動することから始まりp = node.parent、ノードの親へのリンクを避けています。

同じブドウの木を何度も訪れずに、根から始めてブドウの木を何度も通り抜ける方法がわかりません。

編集

私は人々がこれを解決するために再帰的な方法を使用することを提案しているのを見ます、そして私は今同意します。しかし、私はしばらくの間、これを行うためのイテレータクラスの方法の解決策を見つけようと頭を悩ませてきました。それが可能かどうか、そしてその方法を知りたいのです。

4

3 に答える 3

19

再帰を使用します。

public void visitNode(Node node) {
    if(node.left != null) {
        visitNode(node.left);
    }
    if(node.right != null) {
        visitNode(node.right);
    }
    if(node.left == null && node.right == null) {
        //OMG! leaf!
    }
}

次を指定して開始しrootます。

visitNode(root);

これを に変換するにIterator<Node>は、再帰をループに変換してから、状態を走査する必要があります。些細なことではありませんが、あなたに多くの楽しみを与えるはずです。

于 2012-11-05T19:56:08.060 に答える
3 
class Node {
    public Node left = null;
    public Node right = null;
    // data and other goodies
}
class Tree {
    public Node root = null;
    // add and remove methods, etc.
    public void visitAllLeaves(Node root) {
        // visit all leaves starting at the root
        java.util.Stack<Node> stack = new java.util.Stack<Node>();
        if (root == null) return; // check to make sure we're given a good node
        stack.push(root);
        while (!stack.empty()) {
            root = stack.pop();
            if (root.left == null && root.right == null) {
                // this is a leaf
                // do stuff here
            }
            if (root.left != null) {
                stack.push(root.left);
            }
            if (root.right != null) {
                stack.push(root.right);
            }
        }
    }
}

上記のコードが機能するかどうかはわかりませんが、それは何をする必要があるかのどこかにあります。もう 1 つのオプションは、javax.swing.TreeModel (冗談半分) です。

于 2012-11-05T20:23:22.823 に答える
1

以下は、葉ノード、つまり左または右のサブツリーを持たないノードのみを返す Iterator を実装する方法です。

イテレータは、深さ優先検索を実行してツリー内のリーフ ノードを検索し、スタック内の検索の現在の状態を記憶し、リーフ ノードが見つかったときに「一時停止」します (fetchNext() メソッドを参照)。

クライアントが next() を呼び出してリーフ ノードを「消費」すると、検索が再開されます。

class Node {
  public Node left;
  public Node right;
}

class LeaveIterator implements Iterator<Node> {
  private final Stack<Node> stack = new Stack<>();
  private Node nextNode = null;

  public LeaveIterator(Node root) {
    if (root != null) {
      stack.push(root);
      nextNode = fetchNext();
    }
  }

  private void fetchNext() {
    Node next = null;
    while (!stack.isEmpty() && next == null) {
      Node node = stack.pop();
      if (node.left == null && node.right == null) {
        next = node;
      }
      if (node.right != null) {
        stack.push(node.right);
      }
      if (node.left != null) {
        stack.push(node.left);
      }
    }
    return next;
  }

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

  public Node next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    Node n = nextNode;
    nextNode = fetchNext();
    return n;
  }

  public void remove() {
    throw new UnsupportedOperationException();
  }
}
于 2014-10-23T12:22:49.987 に答える