子树的第一个元素总是最左边的元素。元素之后的下一个元素是其右子树的第一个元素。如果元素没有正确的子元素，则下一个元素是元素的第一个正确的祖先。如果元素既没有正确的子节点也没有正确的祖先，它是最右边的元素，它是迭代的最后一个。
我希望我的代码是人类可读的，涵盖所有案例。
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;
}else 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没有父母，所以我们不能再进一步。我们来自最右边的节点，我们完成了迭代。
| 
转播
