Árbol binario enhebrado: hilos al sucesor y recorrido inorden sin pila

​

Lo que vas a aprender

• Cuántos enlaces vacíos tiene un árbol binario.
• Qué es un hilo derecho y un hilo izquierdo.
• Cómo se distinguen hijos e hilos.
• El recorrido en inorden e inorden inverso con hilos.

​

Cómo se usa el simulador

• Escribe los valores en orden de inserción (árbol de búsqueda) y pulsa Construir, o elige un árbol equilibrado, degenerado, irregular o 🎲 al azar.
• Elige el recorrido: inorden o inorden inverso, y qué hilos dibujar: derechos, izquierdos o ambos.
• Avanza con ⏮, ◀, ▶ Recorrer, ▶ y ⏭. Se resaltan el nodo actual, el hilo por el que se salta y la línea del código Java, y se van apuntando los nodos visitados.

​

Fundamentos teóricos

​

Enlaces vacíos

​

Hilos

• Hilo derecho: si un nodo no tiene hijo derecho, su enlace derecho apunta a su sucesor en inorden.
• Hilo izquierdo: si no tiene hijo izquierdo, su enlace izquierdo apunta a su predecesor.

​

Marcas

class Nodo<E> {
    E dato;
    Nodo<E> izq, der;
    boolean hiloIzq, hiloDer;   // true: el enlace es un hilo
}

​

Recorrido en inorden sin pila

Nodo<E> act = masIzquierda(raiz);
while (act != null) {
    visitar(act.dato);
    if (act.hiloDer) act = act.der;           // salta al sucesor
    else act = masIzquierda(act.der);         // baja al subárbol derecho
}

1. Empieza por el nodo más a la izquierda (el menor).
2. Tras visitar un nodo: si su enlace derecho es un hilo, salta por él; si es un hijo, baja a ese subárbol hasta su nodo más a la izquierda.

​

Coste

​

Ejemplos resueltos

​

Experimenta con el simulador

​

Errores frecuentes

• Confundir un hilo con un hijo si no se miran las marcas.
• Pensar que el hilo derecho apunta al padre. Apunta al sucesor en inorden, que puede ser un antepasado más lejano.

​

Herramientas relacionadas