Estructuras de Datos no

lineales : Árboles

Estructura de Datos

Definiciones de ÁrbolEn 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.

Usos de un Árbol

Algunos ejemplos donde la estructura de datos árbol puede ser muy útil :

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.

TDA ÁrbolUn árbol es una estructura de datos no lineal.

Las estructuras de datos lineales se caracterizan por que a cada elemento lecorresponde no más que un elemento siguiente.

En las estructuras de datos no lineales, como el árbol, un elemento puedetener diferentes " siguientes elementos ", introduciendo una estructura debifurcación, también conocidas como estructuras multi-enlazada.

Árbol: estructura no lineal y dinámica de datos.

Dinámica: puede cambiar durante la ejecución de un programa.

No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

Definiciones Básicas• Nodo Padre de un nodo N es aquel que apunta al mismo. En un árbol cada nodo sólo puede tener un padre. En el ejemplo, A es el padre de B y C, y a su vez, B es el padre de D.

• Nodo Hijo de otro nodo A es cualquier nodo apuntado por el nodo A. Un nodo puede tener varios hijos. En el ejemplo , B y C son los nodos hijos de A y todos los nodos tienen uno o dos hijos.

• Nodo Raíz es el único del árbol que no tiene padre. En la representación quehemos utilizado, el nodo raíz es el que se encuentra en la parte superior del árbol: A.

• Hojas son todos los nodos que no tienen hijos. En la representación del ejemplo son hojas los nodos situados en la parte inferior: D, G, H y F.

• Nodos Interiores son los nodos que no son ni el nodo raíz, ni nodos hoja. En el ejemplo , son nodos interiores B, C y E.

• Camino es una secuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo. En el ejemplo A-B-D es un camino, al igual que E-G y C-E-H.

• Rama es un camino desde el nodo raíz a una hoja. En el ejemplo, A-C-E-G y AC-F son ramas.

• Altura es el máximo número de nodos de las ramas del árbol. Dicho en otrostérminos, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. La altura del árbol del ejemplo 1 es 4, ya que esa es la longitud de la rama A-C-E-H, que junto a A-C-E-G son las dos más largas.

• Grado es el número máximo de hijos que tienen los nodos del árbol. Así, en el ejemplo anterior el árbol es de grado dos.

• Nivel de un nodo, es el número de nodos del camino desde la raíz hasta dicho nodo. En el árbol del ejemplo, A tiene nivel 1; B y C tienen nivel 2; D, E y F tienen nivel 3 y G y H tienen nivel 4.

• Bosque colección de dos o más árboles. Un ejemplo de bosque sería el siguiente:

Primitivas del TDA ÁrbolCREAR: crea un árbol vacío.Postcondición : árbol creado y vacío.

DESTRUIR: libera los recursos que mantienen el árbol.Precondición: el árbol debe haber sido creado.

PADRE(de un nodo determinado) :devuelve el padre del nodo recibido. En caso de no existir el padre, devuelve NODO_NULO.Precondición : el nodo recibido no es NODO_NULO.

HIJO_IZQUIERDO(de un nodo determinado): devuelve el hijo a la izquierda del nodo recibido o NODO_NULO si no existe .Precondición: el nodo recibido no es NODO_NULO.

HIJO_DERECHO(de un nodo determinado): devuelve el hijo a la derecha del nodo recibido o NODO_NULO si no existe .Precondición: el nodo recibido no es NODO_NULO.

RAIZ: devuelve el nodo que está en la raíz del árbol o NODO_NULO si el árbol es nulo.Precondición: el árbol debe haber sido creado.

INSERTAR_HIJO_IZQUIERDA(recibe un árbol y un nodo determinado): inserta el árbol como hijo a la izquierda del nodo.Si ya existe el hijo a izquierda, la primitiva se encarga de que sea destruido junto con sus descendientes.Precondiciones: el árbol recibido no es ARBOL_VACIO y el nodo no es NODO_NULO.Postcondición: árbol modificado por la inserción del nuevo nodo

INSERTAR_HIJO_DERECHA(recibe un árbol y un nodo determinado): inserta el árbol como hijo a la derecha del nodo.Si ya existe el hijo a derecha, la primitiva se encarga de que sea destruido junto con sus descendientes.Precondiciones: el árbol recibido no es ARBOL_VACIO y el nodo no es NODO_NULO.Postcondición: árbol modificado por la inserción del nuevo nodo

ELIMINAR_HIJO_IZQUIERDA(de un nodo determinado): devuelve el subárbol con raíz hijo a la izquierda del nodo recibido, al cual se le quita el subárbol izquierdo.Precondición: el nodo recibido no es NODO_NULO.Postcondición: árbol modificado por el borrado de un nodo

ELIMINAR_HIJO_DERECHO(de un nodo determinado): devuelve el subárbol con raíz hijo a la derecha del nodo recibido, al cual se le quita el subárbol derecho.Precondición: el nodo recibido no es NODO_NULO.Postcondición: árbol modificado por el borrado de un nodo

120 –87 – 43 – 65 – 140 – 99 – 130 – 22 – 56