In ordine iteratore per albero binario

Question

Come si può scrivere un iteratore Java (cioè bisogno della next e hasNext metodi) che prende la radice di un albero binario e scorre attraverso i nodi dell'albero binario in in ordine moda ?

Answer 1

Il primo elemento di un sottostruttura è sempre il più a sinistra. L'elemento successivo dopo un elemento è il primo elemento della sottostruttura di destra. Se l'elemento non ha un figlio destro, l'elemento successivo è il primo antenato di destra dell'elemento. Se l'elemento non ha né un figlio destro né un antenato destro, è l'elemento più a destra ed è l'ultimo in iterazione.

Spero che il mio codice sia leggibile dall'uomo e copra tutti i casi.

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

Si consideri il seguente albero:

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

• Il primo elemento è "completamente a sinistra dalla radice"
• a non hai figlio destro, quindi l'elemento successivo è "up fino a quando non vieni da sinistra "
• b ha un figlio destro, quindi itera la sottostruttura di destra
• c non ha un figlio giusto. È genitore è b, che è stato attraversato. Il prossimo genitore è d, che non è stato attraversato, quindi fermati qui.
• d ha una sottostruttura giusta. Il suo elemento più a sinistra è e.
• ...
• g non ha sottostruttura di destra, quindi camminare. f è stato visitato, poiché siamo venuti da destra. d è stato visitato. d non ha genitore, quindi non possiamo andare oltre. Siamo arrivati ​​dal nodo più a destra e abbiamo finito di ripetere.

Answer 2

E 'piuttosto semplice, per l'attraversamento in ordine di visitare il figlio sinistro se ce n'è uno, quindi il nodo radice, allora il bambino a destra:

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

Diagramma:

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

Answer 3

Per ottenere la voce successiva, 'nextEntry()', per l'iteratore, ho guardato i frammenti da java.util.TreeMap incollati di seguito. In parole povere, direi che assicuri che il nodo radice non sia nullo, altrimenti restituisca null. Se non lo è, consulta il nodo giusto se non è nullo. Quindi visita la sinistra (se non è nullo) e visita quella sinistra ripetutamente in un ciclo while fino a colpire null. Se il nodo destro originale è nullo, invece di tutto ciò, visitare il nodo genitore se non è nullo. Ora inserisci un ciclo while in cui visiti il ​​genitore finché non è nullo o il nodo che stai visitando ha il nodo destro (figlio) uguale alla tua ultima posizione. Ora restituisci qualunque voce tu stia visitando. In mancanza di tutte queste opzioni, restituisce il nodo root (originale). 'HasNext()' si limita a verificare se questa "voce successiva" che si sta restituendo è nullo o no.

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