二进制树的有序迭代器

Question

我如何编写一个Java迭代器(即需要next和hasNext方法),它采用二叉树的根,并按顺序迭代二叉树的节点？

Answer 1

子树的第一个元素始终是最左边的元素.元素之后的下一个元素是其右子树的第一个元素.如果元素没有正确的子元素,则下一个元素是元素的第一个右祖先.如果元素既没有右子也没有右祖先,那么它就是最右边的元素,它是迭代中的最后一个元素.

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

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没有父母,所以我们不能进一步向上.我们来自最右边的节点,我们已经完成了迭代.