Arboles

Programaci´n Modular. ETSIT. 1o C.
o
Gui´n del profesor Juan Falgueras
o
Curso 2005
versi´n: 23 de mayo de 2005
o

6
´
Arboles
Contenido
6. Tipos de datos abstractos
´
6.1. Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1. Conceptos previos . . . . . . . . . . . . . . . . . . . .
6.1.2. Representaciones . . . . . . . . . . . . . . . . . . . . .
6.1.3.Terminolog´ . . . . . . . . . . . . . . . . . . . . . . .
ıa
6.1.4. Propiedades de los ´rboles n-arios . . . . . . . . . . .
a
´
6.1.5. Arboles Binarios . . . . . . . . . . . . . . . . . . . . .
6.2. TDA ´rbol binario (ArbolB) . . . . . . . . . . . . . . . . . . .
a
6.2.1. Definici´n . . . . . . . . . . . . . . . . . . . . . . . . .
o
6.2.2. Especificaci´n del TDA ArbolB . . . . . . . . . . .. .
o
6.2.3. Definiciones y propiedades sobre los Arboles Binarios .
´
6.2.4. Arboles balanceados . . . . . . . . . . . . . . . . . . .
6.2.5. Aplicaciones de los ArbolB . . . . . . . . . . . . . . .
6.3. Iteradores sobre ´rboles . . . . . . . . . . . . . . . . . . . . .
a
´
6.3.1. Arboles entrelazados . . . . . . . . . . . . . . . . . . .
´
6.4. Arboles de b´squeda . . . . . . . . . .. . . . . . . . . . . . .
u
6.5. Pr´cticas y ejercicios . . . . . . . . . . . . . . . . . . . . . . .
a
6.6. Apendice A: T´cnicas de Compresi´n . . . . . . . . . . . . . .
e
o
6.6.1. Codificado de secuencias (Run-Length encoding) . . .
6.6.2. Codificado de longitud variable . . . . . . . . . . . . .
6.7. Referencias de consulta . . . . . . . . . . . . . . . . . . . . .

6.

6.1.

.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

1
1
2
2
3
4
5
7
7
7
11
12
13
14
17
18
20
2324
24
26

Tipos de datos abstractos
´
Arboles

En este apartado se tratar´ de una forma general la estructura de datos ´rbol, que es fundaa
a
mental en inform´tica. Comenzaremos resumiento las definiciones m´s elementales con la m´xima
a
a
a
precisi´n. Presentaremos los axiomas m´s generales v´lidos para ´rboles de cualquier tipo. Poco a
o
a
a
a
poco iremos concretando enproblemas y estructuras m´s particulares el TDA ´rbol binario, Ara
a
bolB, elemental, nos servir´ para introducir los conceptos de recorridos b´sicos a trav´s de ´rboles;
a
a
e
a
definiremos tambi´n otra serie especial de estructuras arb´reas (como los ´rboles balanceados),
e
o
a
que tienen particulares propiedades, utiles para mejorar las implementaciones.
´
Sin dejar este TDA ArbolBsencillo, veremos formas de implementaci´n (como la entrelazada)
o
que optimizan los recorridos fundamentales.
N´tese que no hablamos de TDA ´rbol ya que aunque lo tratemos como tal, desde
o
a
el punto de vista de una especificaci´n m´s o menos abstracta, no estamos al nivel
o
a
de abstracci´n del que disfrut´bamos con los TDAs pila, cola, etc.; en aquellos la idea
o
a

6.1

´
Arboles2

de partida no exig´ una interrelaci´n entre los elementos particular (se hablaba de
ıa
o
estructuras LIFO, FIFO, etc.) mientras que con los ´rboles bajamos a detallar el tipo
a
de relaci´n existente entre elementos y no propiedades abstractas de la organizaci´n.
o
o
6.1.1.

Conceptos previos

Las listas, pilas y colas son estructuras lineales (unidimensionales, si se quiere);...