Tareas

INTRODUCCION


Un árbol impone una estructura jerárquica sobre una colección de objetos. Ejemplos claros de utilización de árboles se presentan tanto dentro como fuera del área de computación (índices de libros, árboles genealógicos, etc.); en Informática constituyen una de las estructuras más utilizadas, con aplicaciones que van desde los árboles sintácticos utilizados para la representacióny/o interpretación de términos de un lenguaje o expresiones aritméticas, pasando por los arboles de activación de procedimientos recursivos, hasta la representación de datos que se desea mantener ordenados con un tiempo de acceso relativamente bajo. En general, se usarán árboles siempre que se quiera representar información jerarquizada, cuando esta converja en un solo punto.ÁRBOLES BINARIOS

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o está formado por una raíz con dos árboles binarios disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y subárbol derecho.
Los árboles binarios (también llamados de grado 2) tienen una especial importancia.Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
La representación gráfica de un árbol binario es la siguiente:



Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2subárboles llamados de acuerdo a su caso como:
• Si el nodo raíz tiene 0 relaciones se llama hoja.
• Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo.
• Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.

Hay dos formas tradicionales de representar un árbol binario en memoria:
• Por mediode datos tipo punteros también conocidos como variables dinámicas o listas.
• Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes seutilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:

Clasificación de Arboles Binarios
Existen cuatro tipos de árbol binario:.
• A. B. Distinto.
• A. B. Similares.
• A. B. Equivalentes.
• A. B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario así comoun ejemplo de cada uno de ellos.
A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

A. B. SIMILARES
Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:

A. B. EQUIVALENTES
Son aquellos arboles que son similares y que además los nodoscontienen la misma información. Ejemplo:

A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.
Recorrido de un Arbol Binario
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver acontinuación:
1. INORDEN
o Recorrer el subarbol izquierdo en inorden.
o Examinar la raíz.
o Recorrer el subarbol derecho en inorden.
2. PREORDEN
o Examinar la raíz.
o Recorrer el subarbol izquierdo en preorden.
o recorrer el subarbol derecho en preorden.
3. POSTORDEN
o Recorrer el subarbol izquierdo en postorden.
o Recorrer el subarbol derecho en postorden.
o Examinar la raíz....