Ejemplos de estructuras arborescentes
Arborescente -con forma de árbol
Ejemplos de estructuras arborescentes
Regla de Alcance: las variables visibles en un procedimiento son aquellos declarados en él mismo o en cualquier ancestro de él (cualquier procedimiento que se encuentre en el camino [único] desde él hasta el origen del árbol (=la raíz)).
Ejemplos de estructuras arborescentes
Ejemplos de estructuras arborescentes
Normalmente se escriben en forma lineal:
Pero para entender cómo son evaluadas se construye (implícitamente) un árbol:
las reglas de precedencia aseguran la existencia de un único árbol para cada expresión en forma lineal;
la forma de árbol representa directamente la estructura de la fórmula; pero es difícil de escribir (con la tecnología más comúnmente usada). La forma lineal es más fácil de escribir, pero más difícil de entender
forma lineal = sintaxis concreta forma de árbol = sintaxis abstracta
Abstracción de la Noción de Árbol
Tratamos de definir:
árbol de elementos de tipo A
Un árbol de (elementos de tipo) A es:
o bien vacío
o bien consta de:
un elemento de tipo A
más un número de árboles de elementos de tipo A
Ejemplo de árbol no vacío
Abstracción de la Noción de Árbol (continuación)
los elementos se llaman habitualmente NODOS del árbol
los árboles también pueden definirse como grafos con ciertas propiedades especiales. (CUALES?)
Árboles n-arios y finitarios
árbol n-ario: si no es vacío, tiene exactamente n subárboles n-arios
árbol finitario: si no es vacío, tiene una cantidad finita de subárboles finitarios.
Pero: Todo árbol finitario puede representarse como un árbol binario, según un método a ver más adelante.
Árboles n-arios y finitarios (ejemplos)
los árboles binarios son 2-arios (obvio)
obviamente los árboles n-arios son todos finitarios
Árboles Binarios – Definición Inductiva
Definimos a AB (Árbol Binario de tipo ):
Árboles Binarios – Definición Inductiva
En la notación gráfica (bidimensional) podríamos definir:
Funciones (recurrentes) sobre árboles binarios
Recurrencia primitiva:
f : – AB ? X
f (()) = xo
f ((izq, a, der)) = c (a, f(izq), f(der) )
Recurrencia (más) general:
En los casos con llamadas recurrentes:
f(t) = c ( f(t1), . . . , f (tn) )
alcanza que cada ti sea más chico que t (por ejemplo: en cantidad total de nodos).
Página siguiente |