PDF de programación - Estructuras de datos y algoritmos 3. Estructuras de datos jerárquicas

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas, y pilas
6. Implementación de mapas, árboles, y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

28/oct/09

1

UNIVERSIDAD
DE CANTABRIA

3. Estructuras de datos jerárquicas
• 3.1 Árboles
• 3.2 Recorrido y ordenación
• 3.3 El ADT árbol
• 3.4 Árboles binarios
• 3.5 Búsqueda

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

2

3.1 Árboles
Un árbol es una estructura de datos jerarquizada
Cada dato reside en un nudo, y existen relaciones de parentesco
entre nudos:

UNIVERSIDAD
DE CANTABRIA

Ejemplo:

Capítulos de
un libro

Libro

Raíz

C1

C2

C3

Nudos

Hojas

S1.1

S1.2 S2.1

S2.2

S2.3

Hermanos

S2.2.1

S2.2.2

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

3

Notas:

UNIVERSIDAD
DE CANTABRIA

Los árboles constituyen estructuras de datos jerarquizados, y tienen multitud de aplicaciones, como
por ejemplo:

• Análisis de circuitos, Representación de estructuras de fórmulas matemáticas
• Organización de datos en bases de datos
• Representación de la estructura sintáctica en compiladores.
• En muchas otras áreas de las ciencias del computador.

Un árbol está constituido por una colección de elementos denominados nudos, uno de los cuales se
distingue con el nombre raíz, junto con una relación de 'parentesco' que establece una estructura jerárquica
sobre los nudos. Cada nudo tiene un padre (excepto el raíz) y puede tener cero o más hijos. Se denomina
hoja a un nudo sin hijos. Como ejemplo se muestra en la figura superior la tabla de contenidos de un libro

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

4

Definición recursiva de los árboles
Un nudo simple n constituye un árbol
• se denomina la raíz del árbol
Supongamos que n es un nudo y T1, T2, ...,
Tk son árboles cuyas raíces son n1, n2, ...,
nk, respectivamente.
• Podemos construir un nuevo árbol
haciendo que n sea el padre de los
nudos n1, n2, ..., nk
• En el nuevo árbol n es la raíz y n1, n2, ...,
nk se denominan los hijos de n

T1

UNIVERSIDAD
DE CANTABRIA

n

...

T2

Tk

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

5

Definiciones
• Camino: secuencia de nudos tales que cada uno es hijo del

UNIVERSIDAD
DE CANTABRIA

anterior

• Longitud del camino: nº de nudos que tiene
• Antecesor: un nudo es antecesor de otro si hay un camino del

primero al segundo

• Descendiente: un nudo es descendiente de otro si hay un

camino del segundo al primero

• Subárbol o Rama: Un nudo y todos sus descendientes

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

6

3.2 Recorrido y ordenación de los
nudos
Los hermanos se ordenan generalmente de izquierda a derecha

UNIVERSIDAD
DE CANTABRIA

A

A

B

C

C
C

B
B

Dos árboles ordenados, distintos

La ordenación o recorrido de los nudos se suele hacer de 3
modos:
• preorden, postorden, e inorden

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

7

Ordenación de los nudos (cont.)

UNIVERSIDAD
DE CANTABRIA

n

T1

T2

...

Tk

2

1

3

Preorden: n,T1,T2,...,Tk
Postorden: T1,T2,...,Tk,n
Inorden: T1,n,T2,...,Tk

5

8

9

6

10

4

7

Figura A

Figura B

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

8

Notas:

UNIVERSIDAD
DE CANTABRIA

Estos tipos de ordenación se definen recursivamente de la forma siguiente:

1. Si el árbol T es nulo, entonces la lista vacía es la lista de T en preorden, postorden e inorden.
2. Si T tiene un solo nudo, entonces el nudo es la lista de T en preorden, postorden e inorden.
3. Si T consiste en un árbol con una raíz n y subárboles T1, T2, ..., Tk, como en la figura a de arriba:

- a)La lista de T en preorden es la raíz n seguida de los nudos de T1 en preorden, luego los nudos de

T2 en preorden, hasta finalizar con la lista de Tk en preorden.

- b)La lista de T en inorden es la lista de los nudos de T1 en inorden, seguida de la raíz n, luego los

nudos de T2, ..., Tk con cada grupo de nudos en inorden.

- c)La lista de T en postorden es la lista de los nudos de T1 en postorden, luego los nudos de T2 en

postorden, y así hasta la lista de Tk en postorden, finalizando con el nudo raíz n.

Un método para producir estas tres ordenaciones de nudos a mano consiste en recorrer los nudos en la
forma que se indica en la figura b de arriba:

• Para ordenar en preorden se lista cada nudo la primera vez que se pasa por él. Para postorden la

última vez. Para inorden se listan las hojas la primera vez que se pasa por ellas, pero los nudos
interiores la segunda.

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

9

Recorrido de árboles
método Preorden (N : Nudo; A : Arbol)

UNIVERSIDAD
DE CANTABRIA

Preorden(H,A);

listar N;
para cada hijo H de N, y empezando por la izquierda
hacer
fpara;
fmétodo;
método Postorden (N : Nudo; A : Arbol)

para cada hijo H de N, y empezando por la izquierda
hacer
fpara;
listar N;
fmétodo;

Postorden(H,A);

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

10

UNIVERSIDAD
DE CANTABRIA

Recorrido de árboles (cont.)
método Inorden (N : Nudo; A : Arbol)

si n es una hoja entonces
si no

listar n;
Inorden(hijo más a la izquierda de n,A);
listar n;
para cada hijo h de n, excepto el más a la
izquierda, y empezando por la izquierda
hacer
fpara;

Inorden(H,A);

fsi;

fmétodo;

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

11

Ejemplo de ordenación de expresiones
aritméticas
Expresión: 5+8*(3+4)-3*5:
• preorden: +5-*8+3,4*3,5
• inorden: 5+(8*(3+4)-(3*5)) es la

+

5

-

UNIVERSIDAD
DE CANTABRIA

expresión en notación matemática
normal

• postorden: 5,8,3,4+*3,5*-+ es la
expresión en Notación Polaca
Inversa (RPN)

*

*

8

+

3
3

5
5

3

4

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

12

3.3. El Tipo de datos abstracto árbol
Operaciones del árbol:

UNIVERSIDAD
DE CANTABRIA

operación
constructor
hazNulo
estaVacio
iterador

argumentos
Elemento

Árbol

retorna

errores

booleano
IteradorDeArbol

Podemos restringir el árbol a que no esté vacío

- en este caso no lo haremos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

13

El Iterador de árboles
La mayoría de las operaciones se encuentran en el iterador de
árboles, que
• contiene una referencia a uno de los nudos del árbol

UNIVERSIDAD
DE CANTABRIA

inicialmente es la raíz

-
- si la referencia es nula, se dice que el iterador no es válido

• puede usarse para recorrer y/o modificar el árbol
• si el iterador no es válido, casi todas las operaciones lanzan
NoValido

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

14

Operaciones del iterador de árboles:
operaciones de modificación

UNIVERSIDAD
DE CANTABRIA

operación

argumentos
constructor
elArbol
insertaPrimerHijo
Elemento
insertaSiguienteHermano Elemento

retorna

errores

IteradorDeArbol

eliminaHoja

modificaElemento
cortaRama
reemplazaRama
anadeRama

Elemento

Elemento

Elemento viejo
Rama cortada
Nueva Rama Rama cortada
Nueva Rama

NoValido
EsRaiz,
NoValido
NoEsHoja,
NoValido
NoValido
NoValido
NoValido
NoValido

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

15

Notas:

UNIVERSIDAD
DE CANTABRIA

• constructor: Crea el iterador del árbol, con el nudo actual igual a la raiz, o no válido si el árbol está

vacío

• insertaPrimerHijo: Añade un hijo al nudo actual, situado más a la izquierda que los actuales, y con el

valor indicado
• insertaSiguienteHermano: Añade un hijo al padre del nudo actual, situándolo inmediatamente a la
derecha del nudo actual. Lanza EsRaiz si se intenta añadir un hermano a la raiz
• eliminaHoja: Si el nudo actual es una hoja, la elimina del árbol y hace que el nudo actual sea su padre.
Si no es una hoja, lanza NoEsHoja.
• modificaElemento: Modifica el contenido del nudo actual reemplazándolo por el elementoNuevo.
Retorna el antiguo contenido del nudo actual

• cortaRama: Elimina la rama del árbol cuya raíz es en nudo actual, y hace que el nudo actual sea su

padre. Retorna la rama cortada como un árbol independiente.
• reemplazaRama: reemplaza la rama del árbol cuya raíz es el nudo actual, sustituyéndola por
nuevaRama; la posición actual no cambia, y será por tanto la raiz de nuevaRama en el árbol actual.
Retorna la rama que ha sido reemplazada como un árbol independiente.
• anadeRama: Añade el árbol indicado por nuevaRama haciendo que su raíz sea hija del nudo actual,
situándola a la derecha de los hijos actuales, si los hay

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

16

Operaciones del iterador de árboles:
operaciones de consulta y recorrido

UNIVERSIDAD
DE CANTABRIA

operación

argumentos

retorna

errores

irARaiz
irAPrimerHijo
irASiguienteHermano
irAPadre
contenido
esHoja
esRaiz
esUltimoHijo
esValido
clonar

NoValido
NoValido
NoValido
NoValido
NoValido
NoValido
NoValido

Elemento
Booleano
Booleano
Booleano
Booleano
IteradorDeArbol

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

28/oct/09

17

Notas:

UNIVERSIDAD
DE CANTABRIA

• contenido: retorna el elemento contenido en el nudo actual
• iaARaiz: hace que el nudo actual sea la raíz del árbol; valdrá no válido si el árbol está vacío
• irAPrimerHijo: hace que el nudo actual sea el primer hijo del actual; valdrá no válido si el nudo actual

no tiene hijos

• irASiguienteHermano: hace q