Iterador en orden para árbol binario [cerrado]

Question

Iterador en orden para árbol binario [cerrado]

¿Cómo puedo escribir un iterador Java (es decir, necesita los métodos next y hasNext) que toma la raíz de un árbol binario e itera a través de los nodos del árbol binario en en orden?

22

java algorithm binary-tree iterator nodes

Author: Paul S., 2012-10-12

Source

3 answers

Para obtener la siguiente entrada, 'nextEntry()', para el iterador, miré los fragmentos de java.util.TreeMap pegados a continuación. En inglés sencillo, yo diría que te aseguras de que el nodo raíz no es null primero si no devuelves null. Si no lo es, visite el nodo derecho si no es null. Luego visita la izquierda (si no null) y visita la izquierda repetidamente en un bucle while hasta que golpees null. Si el nodo derecho original es null, entonces en lugar de todo eso, visite el nodo padre si no es null. Ahora ingrese un bucle while donde visita el padre hasta que sea nulo o el nodo que estás visitando tiene su nodo derecho (hijo) igual a tu última posición. Ahora devuelve cualquier entrada en la que estés sentado. Si falla todas esas opciones, devuelve el nodo raíz (original). 'hasNext ()' simplemente comprueba si esta "siguiente entrada" que está devolviendo es nula 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;
    }
}

2

Author: apcris,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-10-12 02:40:08

Es bastante sencillo, para el recorrido en orden se visita el hijo izquierdo si hay uno, luego el nodo raíz, luego el hijo derecho:

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

Diagrama:

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

0

Author: Hunter McMillen,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-10-12 01:14:53

score 38 · Accepted Answer

El primer elemento de un subárbol es siempre el más a la izquierda. El siguiente elemento después de un elemento es el primer elemento de su subárbol derecho. Si el elemento no tiene un hijo correcto, el siguiente elemento es el primer antepasado correcto del elemento. Si el elemento no tiene ni un hijo correcto ni un antepasado correcto, es el elemento más a la derecha y es el último en iteración.

Espero que mi código sea legible por humanos y cubra todos los casos.

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

Considere lo siguiente árbol:

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

El primer elemento es "totalmente a la izquierda de la raíz"
a no tiene un hijo correcto, por lo que el siguiente elemento es "hasta que vengas de la izquierda"
b tiene un hijo correcto, así que itera el subárbol correcto b
c no tiene un hijo correcto. Su padre es b, que ha sido atravesado. El siguiente padre es d, que no ha sido atravesado, así que deténgase aquí.
d tiene un subárbol derecho. Su elemento más a la izquierda es e.
...
g no tiene un subárbol derecho, así que camina hacia arriba. f ha sido visitado, ya que hemos venido de la derecha. d ha sido visitado. d no tiene padre, por lo que no podemos avanzar más. Hemos venido del nodo más a la derecha y hemos terminado de iterar.