Arboles Binarios

Árboles binarios.

Los árboles de grado 2 tienen una especial importancia. Se les conoce con el nombre de árboles binarios. Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formado por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz.

En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.

Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.

Ejemplo:

Operaciones básicas.- Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol.Esta operación se considera entonces como un parámetro de una taré más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.

Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.

Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.

Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:

12 - 8,17 - 5,9,15

Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, orden central y postorden.

Preorden: Raiz, subárbol izquierdo y subárbol derecho.

Orden central: Subarbol izquierdo, raiz, subarbol derecho.

Postorden: Subarbol izquierdo, subarbol derecho, raiz.

Ejemplo:

Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47

Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47

Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20

Ejemplo:

Preorden: / + a b * c d Notación polaca

Orden central: a + b / c * d Notación infija

Postorden: a b + c d * / Notación polaca inversa

Estructura de datos

Variables

Las variables son estructura de datos usados para almacenar información. Hay dos tipos de información que puede ser almacenada: Números y texto. Antes de usar una variable ésta, deberá primero ser definida:

Dim nombre_de_variable As Tipo

Ejemplo:

Dim precio As Long

Dim nombre_de_articulo As String

Tipo Rango permitido

Integer -32,768 a 32,767

Long -2,147,483,648 a 2,147,483,647

Single -3.402823E38 a -1.401298E-45

1.401298E-45 a 3.402823E38

Double -1.79769313486232D308 a -4.94065645841247D-324

4.94065645841247D-324 a 1.79769313486232D308

Currency -922337203685477.5808 a 922337203685477.5807

...