遍历二叉搜索树以查找所有叶子节点。

Question

我对树结构比较陌生，正在尝试创建一种“叶子迭代器”。我的想法是把所有没有.left和.right值的节点放到一个栈上，但我不确定这样做是否正确，也不知道怎么做。我已经尝试搜索，但我找到的每个例子都是从最左边的叶子开始，然后去p = node.parent，但我不想链接到节点的父节点。

我不明白如何重复从根节点开始遍历树枝，而不会反复访问相同的树枝。

编辑

我看到有人建议使用递归方法来解决这个问题，现在我同意了。但我一直在思考用迭代器类的方法来实现这个，而且我仍然想知道是否可能以及如何实现！

- Sti

---

我会推荐使用递归而不是迭代方法。 - Woot4Moo

Answer 1

使用递归：

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>，您需要将递归转换为循环，然后转换为带有状态的遍历。 不是微不足道的工作，但应该会带给你很多乐趣。

- Tomasz Nurkiewicz

---

但这只会找到一个叶子吗？最左边的那个？ - Sti

它使用系统堆栈来访问所有叶子节点。 - Whymarrh

@Sti：关键词是递归。一旦到达最左边的叶子，它就会返回并逐渐遍历整棵树。 - Tomasz Nurkiewicz

@TomaszNurkiewicz 好的，那么将 if()if()if() 转换为 if()elseif()else() 在递归世界中会成为一个绝佳选择吗？但是出于好玩的目的，你所说的“将递归转换为循环和状态遍历”是什么意思呢？这听起来很有趣。 - Sti

尝试在所有叶子节点上实现一个Iterator，你会发现其中的挑战。 - Tomasz Nurkiewicz

Answer 2

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（半开玩笑）。

- Whymarrh

Answer 3

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

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

- applequist

---

你能解释一下为什么这个回答是正确的吗？最好的回答不仅包括代码！ - Ben