Итератор в порядке для двоичного дерева

Ответ 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 не имеет родителя, поэтому мы не можем двигаться дальше. Мы пришли с самой правой node, и мы закончили итерацию.

Ответ 2

Чтобы получить следующую запись, 'nextEntry()', для итератора, я просмотрел фрагменты из java.util.TreeMap, вставленные ниже. На простом английском языке я бы сказал, что вы убедитесь, что root node не имеет значение null first else возвращает null. Если это не так, выберите правильный node, если он не является нулевым. Затем перейдите влево (если не null) и перейдите к тому, что один раз несколько раз повторяется в цикле while, пока не нажмете нуль. Если исходное право node равно null, то вместо всего этого, посетите родительский node, если это не null. Теперь введите цикл while, в котором вы выберете родителя, пока он не будет равен нулю или node, который вы посещаете в данный момент, имеет право (ребенок) node, равное вашей последней позиции. Теперь верните любую запись, в которую вы входите. Если все эти опции не выполняются, верните (исходный) корень node. 'HasNext()' просто проверяет, является ли эта "следующая запись", которую вы возвращаете, null или нет.

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

Ответ 3

Это довольно прямолинейно, для обхода в порядке вы посещаете левое дочернее, если оно есть, а затем корень node, а затем правый ребенок:

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