Un árbol se puede definir como una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, antecesor, sucesor, ancestro etc.
Formalmente se define un árbol de tipo T como una estructura homogenea resultado de concatenación de un elemento de tipo T con un numero finito de arboles
APLICACIONES.
Los arboles se pueden aplicar para la solución de una gran cantidad de problemas. Se pueden utilizar para representar formulas matemáticas, para registrar la historia de un campeonato de tenis,para construir un árbol genealógico etc.
PROPIEDADES.
Todos los nodos son descendientes directos hijos de un mismo nodo padre, son hermanos.
- Todo nodo que no tiene ramificaciones hijo se conoce con el nombre de terminal u hoja.
- Grado. Numero de descendientes directos de un determinado nodo.
- Grado de árbol. Es el max grado de todos los nodos del árbol.
- Nivel. Es el numero de arcos que pueden ser recurridos para llegar a un determinado nodo.
LONGITUD DE CAMINO INTERNO.
Es la suma de longitudes de camino de todos los nodos de el árbol.
i= nivel del árbol.
h=altura
ni=numero de nodos en el nivel.
LCI= 1*1+2*2+3*4+4*4=33.
LONGITUD DE CAMINO EXTERNO.
X árbol extendido: Es aquel en el que el numero de hijos de cada nodo es igual al grado del árbol de no cumplir con estas características se deben incorporar nodos especiales.
Nodo especiales: reemplazan las ramas vacías o nulas.
LCE: es la suma de tos los nodos especiales.
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.
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 tarea 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: Raíz, subárbol izquierdo y subárbol derecho.
Orden central: Subárbol izquierdo, raíz, subárbol derecho.
Postorden: Subárbol izquierdo, subárbol derecho, raíz.
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: Raíz, subárbol izquierdo y subárbol derecho.
Orden central: Subárbol izquierdo, raíz, subárbol derecho.
Postorden: Subárbol izquierdo, subárbol derecho, raíz.
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
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
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
Transformación de un Árbol Gral. en un Árbol Binario.
- Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
- Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos.
- Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente.
BOSQUE.
Rpresentacion de un conjunto normalmente ordenado de uno o mas arboles generales.
