Estudiante

ACTIVIDAD : TIPO DE DATO ARBOL
(No Presencial)

Plazo de entrega: 14/10/2011

1. a) Defina el concepto de tipo de dato árbol general, árbol binario y árbol binario de búsqueda. Especifique su representación en Pascal para cada uno de los tipos definidos.
b) ¿Por qué cree que es conveniente utilizar representaciones con árboles binarios de búsqueda? Justifique su respuesta.
c)¿Existen diferencias en las representaciones de árbol binario y árbol binario ordenado en Pascal? Justifique su respuesta.

2. Describa tres situaciones reales que pueden ser representadas utilizando los tres tipos de datos especificados en 1.a). Especifique su representación en Pascal para cada ejemplo descripto.

3. Se dispone de un vector que contiene valores enteros (a lo sumo 100 valores). Elvector puede tener valores repetidos. Realice un programa que invoque a:
a) El módulo CARGAR-VECTOR que genera el vector con los valores enteros. Los valores no guardan ningún orden interno.
b) El módulo CARGAR-ARBOL que genera un árbol binario ordenado a partir de los valores que aparecen en el vector y la cantidad de ocurrencias (es decir en el árbol cada valor del vector aparece una solavez)
c) El módulo MOSTRAR-ARBOL que imprime los elementos del árbol binario ordenado, utilizando el recorrido En Orden.

4. Teniendo en cuenta el ejercicio 3):
a) Analice y detalle en palabras que modificaría en su solución en el caso que los elementos del vector estuvieran ordenados.
b) Qué característica tendría el árbol resultante para el caso planteado en (a).
c) Realicealgún comentario acerca de la eficiencia de esta solución.



Se debe entregar el código fuente (en Pascal) de la solución al ejercicio 3). Escribir un único programa que invoque a los módulos que solucionan los incisos a), b) y c).









1.
a) El tipo de dato árbol es una estructura de datos que satisface tres propiedades:
• Cada elemento del árbol (nodo) puede relacionarse concero o más elementos a quienes llama “hijos”.
• Si el árbol no está vacío, hay un único elemento al cual se llama raíz y que no tiene padre (predecesor), es decir, no es hijo de ningún otro.
• Todo otro elemento del árbol posee un único padre y es un descendiente (hijo del hijo del hijo, etc.) de la raíz.

Este tipo de dato se caracteriza por ser:
Homogéneo: todos los elementos sondel mismo tipo.
Dinámica: puede aumentar o disminuir su tamaño durante la ejecución del programa
No lineal: cada elemento puede tener 0, 1, o más sucesores.
Además permite la representación jerárquica como, por ejemplo, las relaciones que existen en una empresa o la representación de una red ferroviaria (más de un sucesor por elemento).
Representación en pascal
Type
Tipo_elem :…;
arbol =^nodo;
Nodo = record
Dato: Tipo_elem; tantos sucesores como sean necesarios
H_1: arbol;
H_2: arbol;
…
H_n:arbol;
End;

Como mencionamos antes un árbol es una estructura donde cada nodo puede tener múltiples links a otros nodos: si cada nodo tiene como máximo dos links estése denomina binario
Representación en pascal
Type
Tipo_elem :…;
arbol = ^nodo;
Nodo = record
Dato: Tipo_elem;
Izq: arbol;
Der: arbol;
End;

El árbol binario de búsqueda es un árbol binario que presenta un orden sobre los datos almacenados en ellos. Mantiene sus datos de tal manera que siempre es posible recuperarlo en el orden dado.Representación en pascal
Type
Tipo_elem :…;
arbol = ^nodo;
Nodo = record
Dato: Tipo_elem ;
Izq: arbol;
Der: arbol;
End;

b) Es conveniente usar representaciones con árboles binarios de búsqueda porque permiten la utilizar del método dicotómico para hallar un elemento en un árbol, el cual consiste en preguntar si el...