ARBOLES Y GRAFOS

ARBOLES Y GRAFOS

DEFINICIONES

En términos matemáticos, un árbol es cualquier conjunto de puntos, llamados vértices, y cualquier conjunto de pares de distintos vértices, llamados lados o ramas, tales que:

·         Hay una secuencia de ramas, llamada paso de cualquier vértice a cualquier otro vértice.

·         No hay lazos, o sea, que no hay pasos que comiencen en un vértice y puedan volver al mismo vértice.

Los árboles que tienen un vértice o nodo especial, llamado raíz, reciben el nombre de árboles enraizados. La particularidad del nodo raíz es que no puede ser hijo de otro nodo.

Un árbol es una estructura de datos no lineal. Las estructuras de datos lineales se caracterizan por que a cada elemento le corresponde no más que un elemento siguiente. En las estructuras de datos no lineales, como el árbol, un elemento puede tener diferentes " siguientes elementos ", introduciendo una estructura de bifurcación, también conocidas como estructuras multi enlazada.

Un árbol ordenado se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En una árbol ordenado podemos hablar del primero, segundo o último hijo de un nodo particular. El primer hijo de un nodo, en un árbol ordenado, se denomina con frecuencia el hijo más viejo de este nodo y el último hijo, se denomina el hijo más joven.

USOS

Veamos algunos ejemplos donde la estructura de datos árbol puede ser muy util :

1. Los sistemas de archivos de los sistemas operativos, compuestos por jerarquías de directorios y archivos.
2. La jerarquía de clases en los lenguajes orientados a objetos.
3. La jerarquía de países, provincias, departamentos y municipios que organiza al poder político de una república.

Tipos de arboles

1. Arboles binarios
2. árbol multicamino

Árbol binario

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

árbol multicamino

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

• A está vacío

Existen muchas aplicaciones en las que el volumen de la información es tal, que los datos no caben en la memoria principal y es necesario almacenarlos, organizados en archivos, en dispositivos de almacenamiento secundario. Esta organización de archivos debe ser suficientemente adecuada como para recuperar los datos del mismo en forma eficiente.

RECORRIDO

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 a continuación: