W zamówienie iterator do binarnego drzewa

Question

Jak mogę napisać iterator Java (tj potrzebuje next i hasNext metody), który zajmuje korzenia binarnego drzewa i iteracji węzłów drzewa binarnego w na zamówienie modę ?

Answer 1

Pierwszym elementem poddrzewa jest zawsze ten z lewej. Następny element po elemencie jest pierwszym elementem jego prawego poddrzewa. Jeśli element nie ma prawego elementu potomnego, następnym elementem jest pierwszy prawy przodek elementu. Jeśli element nie ma prawego dziecka ani prawego przodka, jest to element najbardziej prawy i jest ostatnim w iteracji.

Mam nadzieję, że mój kod jest czytelny dla człowieka i obejmuje wszystkie przypadki.

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

Rozważmy następujący drzewa:

 d 
/ \ 
    b  f 
/\ /\ 
a c e g 

• Pierwszym elementem jest „w pełni lewo od korzenia”
• a nie ma prawa dziecka, więc następnym elementem jest „up do momentu pojawienia się od lewej "
• b ma prawo dziecko, więc iterować b prawy poddrzewo
• c nie ma właściwego dziecka. Jego rodzicem jest b, który został przemierzony. Następny rodzic to d, który nie został przejechany, więc zatrzymaj się tutaj.
• d ma prawo poddrzewo. Jego lewym elementem jest e.
• ...
• g nie ma prawego poddrzewo, więc podejdź. f został odwiedzony, ponieważ pochodzimy z prawej strony. d został odwiedzony. d nie ma rodzica, więc nie możemy przejść dalej. Przybyliśmy z prawego węzła i skończyliśmy iterować.

Answer 2

Jest to dość proste, bo w prawidłowej kolejności przechodzenia odwiedzić lewy dziecko, jeśli istnieje, to węzeł główny, a następnie prawy dziecko:

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

Diagram:

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

Answer 3

Aby uzyskać następny wpis, "nextEntry()", dla iteratora, spojrzałem na fragmenty z java.util.TreeMap wklejone poniżej. Mówiąc prostym językiem, powiedziałbym, że upewniasz się, że węzeł główny nie ma wartości null, a po pierwsze zwraca zero. Jeśli nie jest, przejrzyj prawy węzeł, jeśli nie jest pusty. Następnie odwiedź lewą stronę (jeśli nie jest pusta) i odwiedzaj ją wielokrotnie w pętli, aż naciśniesz zero. Jeśli pierwotny węzeł prawy ma wartość NULL, zamiast tego należy odwiedzić węzeł nadrzędny, jeśli nie jest to wartość NULL. Teraz wprowadź pętlę while, w której zobaczysz obiekt nadrzędny, aż uzyska on wartość zerową lub węzeł, który aktualnie odwiedzasz, ma swój prawy (podrzędny) węzeł równy ostatniej pozycji. Teraz zwróć dowolny wpis, na którym siedzisz. W przypadku niepowodzenia wszystkich tych opcji zwraca (oryginalny) węzeł główny. "HasNext()" sprawdza tylko, czy ten "następny wpis", który zwracasz, jest pusty lub nie.

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