> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.
# Árbol binario enhebrado: hilos al sucesor y recorrido inorden sin pila
> Qué es un árbol binario enhebrado: hilos al sucesor y al predecesor en inorden, marcas de hilo, recorrido en inorden e inorden inverso sin recursión ni pila, con código Java.
Hilos al sucesor y al predecesor en inorden, y recorrido del árbol en Java sin recursión ni pila.
Un árbol binario con $n$ nodos tiene $2n$ enlaces, pero solo $n - 1$ apuntan a hijos: los otros **$n + 1$ están a `null`**. Un **árbol enhebrado** aprovecha esos enlaces vacíos como **hilos** que apuntan al nodo siguiente o anterior en inorden. Así se puede recorrer el árbol en orden **sin recursión y sin pila**, y encontrar el sucesor de cualquier nodo sin volver a la raíz.
## 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
En un árbol binario de $n$ nodos hay $2n$ referencias (izquierda y derecha de cada nodo). Como cada nodo salvo la raíz tiene un padre, $n - 1$ referencias apuntan a hijos y **$n + 1$ son `null`**.
### 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**.
El primer nodo en inorden no tiene predecesor y el último no tiene sucesor: esos hilos quedan a `null`.
### Marcas
Cada nodo guarda dos booleanos para saber si cada enlace es un hijo o un hilo:
```java theme={null}
class Nodo {
E dato;
Nodo izq, der;
boolean hiloIzq, hiloDer; // true: el enlace es un hilo
}
```
### Recorrido en inorden sin pila
```java theme={null}
Nodo 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.
El **inorden inverso** hace lo mismo con los hilos izquierdos, de mayor a menor.
### Coste
El recorrido completo es $O(n)$ y no usa memoria extra (ni pila ni recursión), frente al $O(h)$ de pila del recorrido recursivo, donde $h$ es la altura.
## Ejemplos resueltos
Árbol de búsqueda con 50, 30, 70, 20, 40, 60 y 80. Inorden: 20, 30, 40, 50, 60, 70, 80.
Hilos derechos (nodos sin hijo derecho): 20 → 30, 40 → 50, 60 → 70 y 80 → `null`.
En el mismo árbol, los nodos sin hijo izquierdo son las hojas: 20 → `null`, 40 → 30, 60 → 50 y 80 → 70.
7 nodos: $2 \cdot 7 = 14$ enlaces, $7 - 1 = 6$ a hijos y $7 + 1 = 8$ vacíos, que se convierten en hilos (dos de ellos quedan a `null`).
## Experimenta con el simulador
Recorre el árbol equilibrado y fíjate en cuándo salta por un hilo y cuándo baja a un subárbol.
Con el árbol degenerado, ¿cuántos hilos hay? ¿Cómo es el recorrido?
Cambia al inorden inverso y comprueba que salen de mayor a menor.
## 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
Árbol binario de búsqueda y recorridos.
El recorrido recursivo y su pila.
Nodos y referencias en Java.
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.