Repasa recursividad, pilas y colas. No necesitas dominar tablas hash para comenzar esta sección.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Árbol binario con DFS en árboles y resolver un caso nuevo.
Reserva entre 35 y 55 minutos para lectura, ejemplos, tres comprobaciones y cierre.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Árbol binario y DFS en árboles? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Representarás jerarquías y derivarás cada recorrido desde el momento exacto en que se visita la raíz.
Al terminar podrás
- Un árbol se define por relaciones, no por el dibujo
- Preorden, inorden y postorden cambian el momento de la acción
- Una cola visita el árbol por distancia desde la raíz
01
Estructura jerárquica
Un árbol se define por relaciones, no por el dibujo
Un nodo puede tener hijos y todo nodo salvo la raíz tiene un padre. Aquí mediremos profundidad y altura en cantidad de aristas: la profundidad parte en la raíz y la altura busca el camino descendente más largo hacia una hoja. Un árbol binario limita a dos hijos, pero no implica ningún orden entre valores.
Hoja: nodo sin hijos.
Subárbol: un nodo junto con sus descendientes.
Altura y cantidad de nodos no son equivalentes.
¿Todo árbol binario es un árbol binario de búsqueda?
Mostrar respuesta ＋
No. Binario solo limita la cantidad de hijos; un ABB añade un invariante de orden.
02
Recorridos en profundidad
Preorden, inorden y postorden cambian el momento de la acción
Preorden visita raíz, izquierda y derecha; inorden visita izquierda, raíz y derecha; postorden visita izquierda, derecha y raíz. La misma plantilla recursiva cambia solo la posición de la acción, pero cada orden responde a usos diferentes.
Preorden puede serializar la estructura si también registra hijos ausentes.
Inorden produce claves ordenadas en un ABB.
Postorden procesa hijos antes que su contenedor.
¿Qué orden visita una raíz antes que todos sus descendientes?
Mostrar respuesta ＋
Preorden: raíz, subárbol izquierdo y subárbol derecho.
03
Recorrido por niveles
Una cola visita el árbol por distancia desde la raíz
El recorrido por niveles agrega la raíz a una cola, retira un nodo y agrega sus hijos. Así procesa primero todos los nodos a distancia d antes de d + 1. Su memoria máxima depende del ancho del árbol.
La cola conserva el orden de descubrimiento.
No agregues hijos null.
La salida puede variar si inviertes el orden de los hijos.
¿Qué estructura auxiliar usarías para un recorrido por niveles?
Mostrar respuesta ＋
Una cola FIFO, porque los nodos descubiertos primero deben procesarse primero.
Tu recorrido en tres ideas
- Un árbol se define por relaciones, no por el dibujo
- Preorden, inorden y postorden cambian el momento de la acción
- Una cola visita el árbol por distancia desde la raíz
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Suponer que árbol binario implica orden de búsqueda.
Memorizar recorridos sin relacionarlos con el momento de visitar la raíz.
Ahora hazlo sin guía
Genera preorden, inorden, postorden y niveles para el mismo árbol y explica una aplicación de cada salida.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Cubre árbol vacío y un nodo.
- Las cuatro salidas son correctas.
- Relaciona niveles con cola y profundidad con pila.