GUÍA 04-11-26 Estructuras de Datos

CN122 · miércoles 04/11/2026 · 13:00-14:15 · Sesión 25

Recorridos de árboles binarios

LOS TRES RECORRIDOS EN PROFUNDIDAD

La diferencia entre ellos es únicamente el momento en que se procesa la raíz respecto a los subárboles.

• Preorden — raíz, izquierdo, derecho.
• Inorden — izquierdo, raíz, derecho.
• Postorden — izquierdo, derecho, raíz.

IMPLEMENTACIÓN RECURSIVA

Las tres son idénticas salvo por la posición de la línea que procesa el nodo. Escribirlas juntas hace evidente la simetría.

• void inorden(Nodo *r) { if (!r) return; inorden(r->izq); visitar(r); inorden(r->der); }

PARA QUÉ SIRVE CADA UNO

• Inorden sobre un ABB devuelve las claves ordenadas de menor a mayor. Es la propiedad más útil del árbol de búsqueda.
• Preorden sirve para copiar o serializar el árbol: al reinsertar en ese orden se reconstruye la misma forma.
• Postorden sirve para liberar la memoria y para evaluar expresiones: se procesan los hijos antes que el padre.

RECORRIDO POR NIVELES

Con una cola: se encola la raíz, y en cada paso se desencola un nodo, se visita y se encolan sus hijos. Es el BFS del árbol y no tiene versión recursiva natural.

ÁRBOLES DE EXPRESIÓN

Un árbol donde las hojas son operandos y los nodos internos operadores. Su recorrido inorden produce la notación infija, el preorden la prefija y el postorden la postfija.

Esto conecta con las pilas de la semana 4: convertir infijo a postfijo y evaluar con pila es lo mismo que construir este árbol y recorrerlo en postorden.

PRÁCTICA

Implementar los cuatro recorridos y construir un árbol de expresión que evalúe una operación aritmética.