Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Estructura de datos. Árboles




Enviado por Pablo Turmero



Partes: 1, 2

    Monografias.com

    Ejemplos de estructuras arborescentes
    Arborescente -con forma de árbol

    Monografias.com

    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)).

    Monografias.com

    Ejemplos de estructuras arborescentes

    Monografias.com

    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

    Monografias.com

    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

    Monografias.com

    Ejemplo de árbol no vacío

    Monografias.com

    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?)

    Monografias.com

    Á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.

    Monografias.com

    Árboles n-arios y finitarios (ejemplos)
    los árboles binarios son 2-arios (obvio)

    obviamente los árboles n-arios son todos finitarios

    Monografias.com

    Árboles Binarios – Definición Inductiva
    Definimos a AB (Árbol Binario de tipo ):

    Monografias.com

    Árboles Binarios – Definición Inductiva
    En la notación gráfica (bidimensional) podríamos definir:

    Monografias.com

    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).

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter