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 |