二叉树的有序迭代器

子树的第一个元素始终是最左边的一个。元素之后的下一个元素是其右子树的第一个元素。如果元素没有正确的子元素，则下一个元素是元素的第一个正确的祖先。如果元素既没有正确的子元素也没有正确的祖先，则它是最右边的元素，并且它是迭代中的最后一个元素。

我希望我的代码是人类可读的并且涵盖所有情况。

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

  没有父母，所以我们不能进一步前进。我们来自最右边的节点，并且已经完成了迭代。