Árboles binarios y recorridos

Cuatro formas de visitar cada nodo. Lo primero que haces con cualquier árbol.

Tres órdenes en profundidad — una línea movida

• In-order — izquierda, nodo, derecha → ordenado (para un BST)
• Pre-order — nodo, izquierda, derecha → copiar / serializar
• Post-order — izquierda, derecha, nodo → borrar / evaluar
• Por niveles — a lo ancho, con una queue → lo más cercano primero

Mira al in-order producir salida ordenada

Clávate a la izquierda hasta el 1, luego hacia la derecha y arriba: 1,3,4,5,7,8,9. Ordenado, gratis.

Costo

• Todo recorrido: O(n) en tiempo (cada nodo una vez)
• Espacio: O(h) — pila de recursión o queue
• Balanceado h = O(log n); degenerado h = O(n) → la recursión puede hacer overflow

Pre/post-order = notación polaca

(3+4)*5 → pre-order * + 3 4 5 (polaca) · post-order 3 4 + 5 * (RPN, corre sobre una pila).

Para llevar

Elige el orden según cuándo necesitas el nodo respecto a sus hijos. In-order de un BST = ordenado. Sigue: el árbol binario de búsqueda.