通过二叉搜索树遍历来查找所有树叶

Question

我对树很新颖，我试图创建一种“叶子迭代器”。我认为它应该把没有.left和.right值的所有节点放到堆栈上，但我不知道如何或者甚至是否是正确的做法。我尝试过搜索它，但是我过来的每个示例都是从最左边的叶开始的，然后去掉p = node.parent，并且我避免链接到节点的父节点。

我不明白我怎么可以反复地从根开始，经过葡萄藤而不是一遍又一遍地访问相同的葡萄树。

编辑

我看到有人建议使用递归的方法来解决这个问题，我现在同意。但是我一直在努力寻找解决方案，以迭代器类的方式来做这件事一段时间，我仍然想知道这是否可能，以及如何！

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>这一点，你就必须递归翻译成环，然后用状态遍历。不平凡，但应该给你很多乐趣。

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

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(); 
    } 
}