java - 二叉树的有序迭代器

Question

如何编写一个 Java 迭代器（即需要nextand方法），它以二叉树的根为根并按顺序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确实有一个正确的孩子，所以 iterateb的右子树
• c没有合适的孩子。它的父是b，已经被遍历了。下一个父节点是d，还没有遍历，所以到此为止。
• d有一个右子树。它最左边的元素是e.
• ...
• g没有右子树，所以往上走。f已经被访问过，因为我们来自右边。d已被访问。d没有父母，所以我们不能更进一步。我们来自最右边的节点，我们已经完成了迭代。

Answer 2

为了获得迭代器的下一个条目“nextEntry()”，我查看了java.util.TreeMap下面粘贴的片段。用简单的英语，我会说你首先确保根节点不为空，否则返回空。如果不是，则访问正确的节点（如果它不为空）。然后访问左边（如果不是 null）并在 while 循环中反复访问左边，直到达到 null。如果原始右节点为空，那么如果不为空，则访问父节点。现在进入一个 while 循环，您可以在其中访问父节点，直到它为 null 或者您当前访问的节点的右（子）节点等于您的最后一个位置。现在返回您正在使用的任何条目。如果所有这些选项都失败，则返回（原始）根节点。'HasNext()' 仅检查此“下一个条目”是否

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

Answer 3

这很简单，对于按顺序遍历，如果有左孩子，则访问左孩子，然后是根节点，然后是右孩子：

visit_node(node)
   if node.left: visit_node(node.left)
   // visit the root node
   if node.right: visit_node(node.right)

图表：

     a 
   /   \        (in-order traversal would give bac)
  b     c