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

Árboles y su implementación en Object Pascal



    1. Resumen
    2. Desarrollo
    3. Conclusiones
    4. Bibliografía

    Resumen:

    En este artículo el autor describe como se
    implementan los árboles
    en el lenguaje de
    programación Object Pascal.

    Introducción:

    Una de las características más importantes
    de Object Pascal es su capacidad para admitir diferentes tipos de datos.
    Entre ellos están los datos de tipo
    simple, los de tipo estructurado y los de tipo
    puntero.

    Los datos de tipo simple son elementos individuales
    (números, caracteres, etc) que se asocian a
    identificadores únicos.

    Existen varios tipos de datos simples que abarcan los
    cuatro tipos estándar (entero, real, de caracteres,
    boléanos) y a los tipos simples definidos por el
    programador (enumerados y subrango).

    Los datos de tipo estructurado se componen de
    múltiples elementos relacionados entre sí que se
    asocian a un único identificador.

    Los elementos individuales, dentro del grupo, pueden
    asociarse también a identificadores independientes. Hay
    cuatro tipos de datos estructurados: arrays, registros,
    ficheros y conjuntos.

    Los datos de tipo puntero se emplean para construir
    tipos dinámicos de datos estructurados tales como las
    listas enlazadas y los árboles.

    Este trabajo tiene
    como propósito describir la implementación de estos
    últimos en Object Pascal.

    Desarrollo:

    Los datos presentan frecuentemente una relación
    jerárquica entre sus elementos; tal es el caso, por
    ejemplo, de árboles genealógicos, tablas de
    contenidos, etc. La estructura de
    datos que se emplea para reflejar esta relación recibe
    el nombre de grafo en árbol o simplemente
    árbol.

    Un árbol se representa generalmente en forma de
    diagrama:

    En este caso se dice que el árbol tiene nueve
    nodos, representados por las letras de la A a la I,
    la raíz del árbol es el nodo A que es el que
    está en la parte superior del diagrama; una línea
    hacia abajo y a la izquierda de un nodo señala un sucesor
    izquierdo del mismo, y una línea hacia abajo y a la
    derecha señala un sucesor derecho (B es un sucesor
    izquierdo de A y C un sucesor derecho), el
    subárbol izquierdo de la raíz A consiste en
    los nodos B, D y E, y el subárbol
    derecho en los nodos C, F, G, H,
    I.

    Los nodos sin sucesor se llaman nodos
    terminales.

    Cada nodo del árbol contiene un subárbol
    izquierdo y uno derecho. Si el nodo es terminal, ambos
    subárboles están vacíos.

    La forma más usual de representar un árbol
    en la memoria de
    la computadora
    es la llamada representación enlazada:

    En esta representación, cada nodo consta de tres
    campos: uno para almacenar la información que contiene el nodo y los
    otros dos para apuntar a los subárboles izquierdo y
    derecho del mismo, respectivamente.

    Para ilustrar cómo se implementan los
    árboles en Object Pascal, se analiza a continuación
    como se podría crear un programa que
    "aprenda" sobre personajes históricos en la medida en que
    se trabaje con él.

    El programa constará con una base de
    "conocimientos", que le permitirá a partir de ciertos
    datos "adivinar" un personaje histórico, en el caso de que
    el personaje no esté registrado en su base de
    conocimientos, el programa lo incorporará a esta junto con
    una información sobre el mismo que lo distinga de los
    demás.

    Supongamos que la base inicial de conocimientos
    está limitada a una pregunta con dos posibles respuestas,
    una afirmativa y otra negativa. La pregunta pudiera ser:
    ¿Fue asaltante del Moncada? Si la respuesta es afirmativa,
    se podría pensar en Fidel, mientras que si es negativa, se
    podría pensar en Martí.

    Para implementar el árbol, se utilizan variables de
    tipo puntero y variables referenciadas.

    La variable de tipo puntero se llamará
    Puntero y apuntará a la variable referenciada
    Arbol que será un registro que
    estará formado por tres campos: Nodo para almacenar
    la información sobre el hecho histórico,
    Ramazquierda que apuntará al personaje
    histórico que cumple con las exigencias de la
    información y RamaDerecha que utilizaremos para
    apuntar al personaje que no cumple los requisitos de la
    información.

    Type

    Puntero = ˆ Arbol;

    Arbol = Record

    Nodo : String;

    RamaIzquierda : Puntero;

    RamaDerecha : Puntero;

    End;

    La variable referenciada se crea dinámicamente
    utilizando el procedimiento
    estándar New.

    El árbol se construirá creando cada nodo y
    enlazándolo, después que se creen los
    subárboles, a su sucesor izquierdo y derecho
    respectivamente. Para ello se declaran las variables de tipo
    Puntero:

    Var

    Elemento, Predecesor : Puntero;

    Elemento para el nodo que se crea y
    Predecesor para poder
    actualizar los punteros, de ese elemento que se creó,
    después que se creen los subárboles ya que dichos
    punteros, inicialmente, apuntarán a Nil para
    indicar que están vacío.

    New (Elemento);

    Elemento.Nodo := ‘¿Fue asaltante del
    Moncada?’;

    Elemento.RamaIzquierda := Nil;

    ElementoRamaDerecha := Nil;

    Predecesor := Elemento;

    New (Elemento);

    Elemento.Nodo :=
    ‘Fidel’;

    Elemento.RamaIzquierda := Nil;

    ElementoRamaDerecha := Nil;

    Predecesor.RamaIzquierda :=
    Elemento;

    New (Elemento);

    Elemento.Nodo := ‘Martí’;

    Elemento.RamaIzquierda := Nil;

    ElementoRamaDerecha := Nil;

    Predecesor.RamaDerecha := Elemento;

    Si al correr el programa el usuario pensó por
    ejemplo en Maceo, se recorrerá el subárbol
    derecho al responderse que no fue asaltante al Moncada y se
    preguntará entonces si es Martí, como la
    respuesta es de nuevo negativa, le pedirá al usuario que
    introduzca el nombre del personaje y una información que
    lo distinga de Martí.

    Suponga que la información es:
    ¿Participó en la Protesta de Baragua? Con
    esta información se debe modificar la información
    de la rama derecha del árbol.

    En este caso se creará primero el personaje y
    después el nodo que contendrá la información
    relacionada con el mismo por lo que se utilizará otra
    variable de tipo Puntero que se llamará
    Sucesor y que se empleará para enlazar el nuevo
    nodo con este personaje.

    New (Elemento);

    Elemento.Nodo := ‘Maceo;

    Elemento.RamaIzquierda := Nil;

    ElementoRamaDerecha := Nil;

    Sucesor := Elemento;

    New (Elemento);

    Elemento.Nodo := ‘¿Participó en
    la Protesta de Baragua?’;

    Elemento.RamaIzquierda := Sucesor;

    Elemento.RamaDerecha :=
    Predecesor.RamaDerecha;

    Predecesor.RamaDerecha := Elemento;

    Note como con las instrucciones
    Elemento.RamaIzquierda := Sucesor; y Elemento.RamaDerecha :=
    Predecesor.RamaDerecha
    ; se enlaza el nuevo nodo con los
    personajes Maceo y Martí,
    respectivamente.

    Con la instrucción Predecesor.RamaDerecha :=
    Elemento;
    se actualiza la rama derecha del nodo que antecede
    al que se está insertando.

    Si el usuario pensó por ejemplo en Abel y la
    pregunta es: ¿Es mártir de la Revolución?, el árbol sería
    entonces:

    Por lo que se deberá modificar la
    información de la rama izquierda.

    New (Elemento);

    Elemento.Nodo := ‘Abel;

    Elemento.RamaIzquierda := Nil;

    ElementoRamaDerecha := Nil;

    Sucesor := Elemento;

    New (Elemento);

    Elemento.Nodo := ‘¿Es mártir de
    la Revolución?’;

    Elemento.RamaIzquierda := Sucesor;

    Elemento.RamaDerecha :=
    Predecesor.RamaIzquierda

    Predecesor.RamaIzquierda :=
    Elemento;

    En la medida en que se corra el programa el árbol
    crecerá por las diferentes ramas en función de
    la información entrada por el usuario, se
    enriquecerá la base de conocimientos y el programa
    habrá "aprendido".

    Conclusiones:

    El conocimiento
    de la implementación de los árboles en Object
    Pascal, permite la representación de estructuras de
    datos en la memoria de la
    computadora
    cuando la relación entre los elementos que componen dicha
    estructura es
    una relación jerárquica.

    Bibliografía:

    De la Torre García, Ernesto. Iniciación en
    Logo.– Ciudad de la Habana : Editorial Pueblo y Educación,
    1988

    Gottfried, Byron S. Programación en Pascal.– Ciudad de la
    Habana : Editorial Pueblo y Educación, 1989

    Lipschutz, Seymour. Estructura de datos.– Ciudad de la
    Habana : Edición
    Revolucionaria, 1989

     

     

    Autor:

    Asistente Juan Antonio Fonseca
    Hernández
    .

    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