二叉树的顺序迭代器 [已关闭]

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

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

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没有合适的孩子。它的父级是 ，已被遍历。下一个父项是 ，尚未遍历，因此请到此为止。bd
• d具有正确的子树。它最左边的元素是 。e
• ...
• g没有正确的子树，所以向上走。 已经访问过，因为我们来自正确的。 已被访问。 没有父母，所以我们不能进一步向上移动。我们来自最右边的节点，我们已经完成了迭代。fdd

为了获取迭代器的下一个条目“nextEntry（）”，我查看了下面粘贴的片段。用简单的英语来说，我会说你确保根节点不是空的，否则返回null。如果不是，则 vist 正确的节点（如果它不为 null）。然后访问左侧（如果不是空），并在一段时间内循环中反复访问左侧，直到命中 null。如果原始右节点为 null，则访问父节点（如果该节点不为 null），而不是全部。现在进入一个 while 循环，在其中访问父节点，直到它为 null 或您当前正在访问的节点的右（子）节点等于您的上一个位置。现在返回您正在放置的任何条目。如果所有这些选项失败，则返回（原始）根节点。'HasNext（）' 只是检查您返回的这个“下一个条目”是否为空。java.util.TreeMap

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

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}