PDF de programación - TEMA 5. ÁRBOLES (I)

TEMA 5. ÁÁRBOLES (I)
RBOLES (I)
TEMA 5.

Estructura de Datos 1º ETIS

1

Índice

1. Concepto de árbol
2. Árboles binarios

1. Especificación informal del TAD árbol binario
2. Implementación del TAD árbol binario
3. Recorrido de un árbol binario
4. Árboles de expresión
5. Árboles hilvanados o enhebrados
6. Árboles parcialmente ordenados (Montículos)
7. Árboles binarios de búsqueda

Estructura de Datos 1º ETIS

2

1

• Estructuras de datos no lineales:

– Cada elemento puede tener varios anteriores y/o siguientes

• Ejemplos de árbol:

– Árboles gramaticales para analizar oraciones
– Árboles genealógicos
– Estructura jerárquica de una organización
– Organización de ficheros en directorios/carpetas según una

estructura en árbol

– Desarrollo de algoritmos
– Recuperación de información

Estructura de Datos 1º ETIS

3

1. Concepto de árbol

• Definición:

– Estructura de datos no lineal, con una organización

jerárquica y elementos homogéneos donde cada
elemento puede tener varios elementos sucesores,
pero un único elemento antecesor

Estructura de Datos 1º ETIS

4

2

1. Concepto de árbol

• Conceptos:

– Nodo

• Cada uno de los componentes o elementos del árbol (1.1, 1.2, …, 2.1, …,

3.3)

– Ascendiente

• Un nodo N1 es ascendiente de N2 si está en un nivel superior dentro de la
estructura jerárquica del árbol. (1.3 es ascendiente de los nodos 1.4, 1.5,
1.6 y 1.7)

– Descendiente:

• Un nodo N1 es descendiente de N2 si está en un nivel inferior dentro de la

estructura jerárquica del árbol. (3.3 es descendiente de 3.1 y 3.2)

Estructura de Datos 1º ETIS

5

1. Concepto de árbol

• Conceptos:

– Nodo Raíz

– Nodo Hoja

– Subárbol:

• Nodo inicial del árbol. Se encuentra en el nivel superior de la estructura jerárquica

del árbol (nivel 1). Es el único que no tiene padre. (1.1, 2.1, 3.1)

• Nodo terminal del árbol. Son todos aquellos nodos que no tienen descendientes y se

encuentran en los niveles más bajos de la estructura jerárquica del árbol, aunque
pueden estar en distintos niveles del mismo. (Árbol 1: 1.2, 1.5, 1.6 y 1.7)

• Subconjunto de nodos de un árbol que a su vez tienen estructura de árbol. El árbol 1

tiene varios subárboles, por ejemplo: desde el nodo 1.3 y todos sus descendientes;
desde el nodo 1.4. El árbol 2 no tiene ningún subárbol.

Estructura de Datos 1º ETIS

6

3

1. Concepto de árbol

• Conceptos:

– Nodo padre:

• Es el nodo ascendiente de sus subárboles. En un árbol cada nodo sólo puede tener

un padre, excepto el nodo raíz, que es el único que no tiene padre. Son nodos
padre:

– 1.1 es padre de 1.2 y 1.3, siendo estos nodos hijos
– 1.3 es padre de 1.4, 1.5 y 1.6, siendo estos nodos hijos
– 1.4 es padre de 1.7, siendo este nodo hijo
– 3.1 es padre de 3.2 y este a su vez es padre de 3.3

– Nodo hijo:

hijos.

– Nodos hermanos:

• Es el nodo descendiente de otro nodo. En un árbol cada nodo puede tener varios

• Dos nodos son hermanos si tienen el mismo padre. (1.2 y 1.3; 1.4, 1.5 y 1.6)

Estructura de Datos 1º ETIS

7

1. Concepto de árbol

• Conceptos:

– Nodo interno:

• Es todo nodo que no es ni nodo raíz ni nodo hoja. Por ejemplo, 1.3, 1.4 y 3.2

– Camino:

• Secuencia de nodos del árbol donde se cumple que cualquier par de nodos

consecutivos son padre e hijo. (1.31.4; 1.11.31.4)

– Longitud del camino:

• Es el número de nodos menos 1 (r-1). Si r>0, se dice que el camino es propio.

longitud(1.31.4)=1; longitud(1.11.31.4)=2

– Rama:

• Cualquier camino desde el nodo raíz del árbol hasta un nodo hoja. (1.11.2;

1.11.31.6; 3.13.23.3)

Estructura de Datos 1º ETIS

8

4

1. Concepto de árbol

• Conceptos:

– Nivel (profundidad):

• Número de nodos terminales u hojas del árbol. peso(árbol1)=4;

peso(árbol2)=1; peso(árbol3)=1

• De un nodo: Número de nodos que tiene el camino desde la raíz a dicho

nodo. nivel(1.3)=2; nivel(1.7)=4; nivel(2.1)=1

• De un nodo: es el número de descendientes directos de dicho nodo o, lo

que es lo mismo, el número de hijos que tiene dicho nodo. grado(1.3)=3;
grado(2.1)=0; grado(3.2)=1

• De un árbol: máximo grado de sus nodos. grado(árbol 1)=3;

grado(árbol2)=0; grado(árbol 3)=1

– Grado:

– Peso:

Estructura de Datos 1º ETIS

9

1. Concepto de árbol

• Conceptos:

– Altura:

• Es el nivel más alto del árbol (nº de niveles del árbol). La
altura es igual al número de nodos que tiene la rama más
larga del árbol. Altura(árbol 1)=4; Altura(árbol 2)=1;
Altura(árbol 3)=3

Estructura de Datos 1º ETIS

10

5

2. Árboles binarios

• Árbol binario:

– Árbol donde cada nodo tiene como máximo grado 2

Estructura de Datos 1º ETIS

11

2. Árboles binarios

• Árbol binario equilibrado:

– Cuando la diferencia de altura entre los subárboles de

cualquier nodo es como máximo una unidad.

– Cuando los subárboles de todos los nodos tienen todos la

misma altura se dice que está perfectamente equilibrado.

• Árbol binario lleno:

– Un árbol binario de altura h es lleno si tiene todas sus hojas a

nivel h y todos los nodos que están en un nivel menor que h
tiene cada uno dos hijos.

Estructura de Datos 1º ETIS

12

6

2. Árboles binarios

• Árbol binario completo:

– A de altura h es completo si está relleno a partir del nivel h-1, con el

nivel h relleno de izquierda a derecha.

– Más formalmente:

• Todos los nodos de nivel h-2 y superiores tienen dos hijos cada uno.
• Cuando un nodo tiene un descendiente derecho de nivel h, todas las hojas

de su subárbol izquierdo están a nivel h.

• SI UN ÁRBOL BINARIO ES LLENO, ES NECESARIAMENTE

COMPLETO.

• UN ÁRBOL BINARIO COMPLETO ES EQUILIBRADO
• UN ÁRBOL BINARIO LLENO ES TOTALMENTE EQUILIBRADO

Estructura de Datos 1º ETIS

13

2.1. Especificación del TAD Árbol Binario
abin=TAD con operaciones crea, esVacio, izq, der,
info, insizq, insder, supizq, supder, modifica.
DESCRIPCIÓN: Los valores del TAD abin son árboles
binarios donde cada nodo contiene un dato del tipo
tipoelem. Los árboles son mutables: insizq, insder,
supizq, supder y modifica añaden, eliminan y
modifican respectivamente elementos de un árbol.

OPERACIONES:
crea() devuelve (abin)
esVacio(A:abin) devuelve (booleano)

– efecto: Devuelve el árbol binario vacío.

– efecto: Devuelve cierto si A es el árbol vacío, y falso en

caso contrario.

Estructura de Datos 1º ETIS

14

7

2.1. Especificación del TAD Árbol binario

izq(A:abin) devuelve (abin)

– requerimientos: El árbol A es no vacío.
– efecto: Devuelve la posición del nodo hijo izquierdo del subárbol A. Si

el nodo A no tiene hijo izquierdo, devuelve nulo.

der(A:abin) devuelve (abin)

– requerimientos: El árbol A es no vacío.
– efecto: Devuelve la posición del nodo hijo derecho del nodo A. Si el

nodo A no tiene hijo derecho, devuelve nulo.
info(A:abin) devuelve (tipoelem)

– requerimientos: El árbol A es no vacío.
– efecto: Devuelve el contenido (etiqueta) del nodo A en el árbol.

insizq(A:abin; E:tipoelem)

– requerimientos: El árbol A es no vacío y nodonulo(izq(A))=cierto.
– modifica: A.
– efecto: Añade un nodo, con contenido E, como hijo izquierdo del

nodo A.

Estructura de Datos 1º ETIS

15

2.1. Especificación del TAD Árbol Binario

insder(A:abin; E:tipoelem)

– requerimientos: El árbol A es no vacío y nodonulo(der(A))=cierto
– modifica: A.
– efecto: Añade un nodo, con contenido E, como hijo derecho del nodo

A.

supizq(A:abin)

descendientes.

supder(A:abin)

– requerimientos: El subárbol A es no vacío
– modifica: A.
– efecto: Suprime el hijo izquierdo del subárbol A y todos sus

– requerimientos: El árbol A es no vacío.
– modifica: A.
– efecto: Suprime el hijo derecho del subárbol A y todos sus

descendientes.

modifica(A:abin; E:tipoelem)
– requerimientos: El árbol A es no vacío.
– modifica: A.
– efecto: Modifica el contenido del nodo A, cambiándolo por el nuevo
contenido E.

Estructura de Datos 1º ETIS

16

8

2.1. Especificación del TAD árbol binario

Estructura de Datos 1º ETIS

17

2.2. Implementación del TAD árbol binario

• Memoria dinámica (punteros)
• Memoria estática (vectores) (simulación de
memoria dinámica montón, como vimos en
listas)

• En cualquier caso, información a almacenar:

– Información con los datos necesarios.
– Enlace hacia el hijo izquierdo o raíz del subárbol

izquierdo.

– Enlace hacia el hijo derecho o raíz del subárbol

derecho.

Estructura de Datos 1º ETIS

18

9

2.2. Implementación del TAD árbol binario

• Realización mediante memoria dinámica

Estructura de Datos 1º ETIS

19

2.2. Implementación del TAD árbol binario

Estructura de Datos 1º ETIS

20

10

2.2. Implementación del TAD árbol binario

Estructura de Datos 1º ETIS

21

2.2. Implementación del TAD árbol binario

Estructura de Datos 1º ETIS

22

11

2.2. Implementación del TAD árbol binario

Estructura de Datos 1º ETIS

23

2.3. Recorrido de un árbol binario

• Recorrido en anchura

– Consiste en recorrer los distintos niveles y, dentro de cada

nivel, los diferentes nodos de izquierda a derecha

• Recorrido en profundidad

– Recorrido inorden:

• IRD, normal de expresiones, orden simétrico u orden central

– Recorro subárbol izquierdo
– Visito nodo raíz
– Recorro subárbol derecho

– Recorrido preorden:

• RID, notación prefija o notación polaca

– Visito nodo raíz
– Recorro subárbol izquierdo
– Recorro subárbol derecho

– Recorrido postorden:

• IDR o notación postfija de expresiones o notación polaca inversa

– Recorro subárbol izquierdo
– Recorro subárbol derecho
– Visito nodo raíz

Estructura de Datos 1º ETIS

24

12

2.3. Recorrido de un árbol binario

• Simulación recorrido en profundidad:
http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BTree.html

Estructura de Datos 1º ETIS

25

2.3. Recorrido de un árbol binario

• Recorrido en profundidad recursivo:

D
D-B

D-B-G
D-B-G-E

D-B-G-E-A

D-B-G-E-A-F

D-B-G-E-A-F-C

Estruct