10

我对树很陌生，我正在尝试创建一种“叶子迭代器”。我认为它应该将所有没有 a.left和.rightvalue 的节点放入堆栈，但我不确定如何做，甚至是否是正确的做法。我已经尝试搜索它，但是我遇到的每个示例都从转到最左边的叶子开始，然后转到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);
            }
        }
    }
}

我不确定上面的代码是否有效，但这与需要做的事情差不多。另一种选择是javax.swing.TreeModel（半开玩笑）。

于 2012-11-05T20:23:22.823 回答
1

下面是如何实现一个只返回叶节点的迭代器，即没有左子树或右子树的节点。

迭代器通过深度优先搜索在树中搜索叶节点，记住堆栈中搜索的当前状态并在找到叶节点时“暂停”（参见 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 回答