PDF de programación - Tema 5: Árboles - Estructura de datos

Universidad de Valladolid
Departamento de informática

Campus de Segovia

Estructura de datos
Tema 5: Árboles

Prof. Montserrat Serrano Montero

1

ÍNDICE

Primera parte:
• Conceptos básicos
• TAD Árbol binario
• TAD Árbol de búsqueda

2

•

•
•

CONCEPTOS BÁSICOS

Árbol: Estructura no lineal que organiza sus
elementos formando jerarquías.

Nodo: Elemento del árbol.
Árbol: Se define formalmente como una
estructura finita formada por un nodo al cual
están conectados ninguno, uno o más árboles
disjuntos (no comparten elementos).
Definición recursiva: lo definido se encuentra
dentro de la definición.

3

CONCEPTOS BÁSICOS

Bosque: Conjunto de dos o más árboles.
Subárbol: Subconjunto de elementos de un
árbol con estructura de árbol.
Raíz: Nodo superior de un árbol. Al nodo raíz
se le asocia el nivel 1. Nivel cero para el árbol
vacío.
Si existe una arista (rama) dirigida del nodo n
al nodo m, entonces n es el padre o
ascendiente directo de m y m es un hijo o
descendiente directo de n. Los hijos del
mismo padre son hermanos.
Un nodo que no tiene hijos se llama hoja del
árbol. Nodo terminal.
Nodo interior o rama: Tiene descendientes.

•
•

•

•

•

•

4

CONCEPTOS BÁSICOS

•

•

•

Camino: Secuencia de nodos conectados
dentro de un árbol.
Nodo ascendiente y descendiente: n es
antecesor de m si existe un camino de n a m
y en este caso, m es descendiente de n.
Longitud del camino: Número de nodos
menos uno (r-1). (5-1) en el ej.

5

•

•

•

•

CONCEPTOS BÁSICOS

Nivel de un nodo: La longitud del camino
desde el nodo raíz al nodo considerado, más
uno.

Altura o profundidad de un árbol: El nivel
más alto del árbol (o nivel máximo de los
nodos de un árbol).
Grado (aridad): Número de hijos de un
nodo. El grado de un árbol se define como el
máximo del grado de sus nodos.
Árbol ternario: Árbol de grado 3.
Un árbol unario sería un árbol de grado 1. A
este árbol se le llama lista (árbol degenerado)
El máximo número de nodos de un árbol de
altura “h” y grado “g” sería:
1 + g + g2 + g3 +...+ gh-1 = ∑ gi ; 0 ≤ i ≤ (h -1)

6

CONCEPTOS BÁSICOS

•

Representación de árboles:
a) Grafo

b) Jerarquía de márgenes

c) Conjuntos incluidos

d) Listas incluidas

7

TAD ÁRBOL BINARIO

•

Árbol binario: Árbol de grado 2. De cada
nodo parten como máximo dos subárboles
disjuntos (izquierdo y derecho). También
puede estar vacío.

ESPECIFICACIÓN INFORMAL:
TAD ArbolB (VALORES: rango del problema;
OPERACIONES: Inicia, EsVacio, Insertar,
Suprimir, Izquierdo, Derecho, Raiz);

Inicia ( ) → ArbolB

Efecto: Crea un árbol binario vacío y lo deja en
disposición de ser utilizado.

EsVacio (ArbolB) → Boolean
8
Efecto: Devuelve true si el árbol binario es
vacío y false en caso contrario.

TAD ÁRBOL BINARIO

Insertar (ArbolB, Elemento) → ArbolB

Efecto: Introduce en el ArbolB un nuevo nodo
cuyo valor está dado por el Elemento pasado.
Excepción: Árbol lleno en implementa. estática.

Suprimir (ArbolB, Elemento) → ArbolB
Efecto: Borra del árbol binario el nodo cuyo
valor coincide con el que se pasa en Elemento,
si éste existe.
Excepción: Error si el árbol binario está vacío.

Izquierdo (ArbolB) → ArbolB

Efecto: Devuelve el hijo izquierdo del árbol
binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.

Derecho (ArbolB) → ArbolB
Efecto: Devuelve el hijo derecho del árbol
binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.

Raiz (ArbolB) → Elemento

Efecto: Devuelve el Elemento contenido en el
nodo raíz del árbol binario pasado como
entrada.
Excepción: Error si el árbol binario está vacío.

9

DECLARACIÓN DE TIPOS
Con arrays:

•
const
MaxNodos = ...;
type
indice = 0..MaxNodos; {máx nº de nodos}
tInfo = ...; {depende del problema}
tNodo = record
info: tInfo;
iz: indice;
de: indice;

end;
tArbol = record

raiz: indice; (1)
libre: indice; (6)
nodos: array [1..MaxNodos] of tNodo;

end;

10

DECLARACIÓN DE TIPOS
Con punteros: (seguir con esta implementación)

•
tInfo = ...; {depende del problema}
tArbol = ^Nodo;
Nodo = record
info: tInfo;
iz, de: tArbol

end;

11

ALGORITMOS BÁSICOS

procedure Inicia (var ArbolB: tArbol);
begin
ArbolB:= nil
end;
function EsVacio (ArbolB: tArbol): boolean;
begin
EsVacio:= (ArbolB = nil)
end;

function Izquierdo (ArbolB: tArbol): tArbol;
begin
if not EsVacio (ArbolB) then Izquierdo:= ArbolB^.iz
else writeln (‘El árbol está vacío’)
end;
function Derecho (ArbolB: tArbol): tArbol;
begin
if not EsVacio (ArbolB) then Derecho:= ArbolB^.de
else writeln (‘El árbol está vacío’)
end;

procedure Raiz (ArbolB: tArbol; var Elemento: tInfo);

begin
if not EsVacio (ArbolB) then Elemento:= ArbolB^.info
else writeln (‘El árbol está vacío’)
end;

12

ALGORITMOS DE RECORRIDO
Utilizados para visualizar o consultar datos
almacenados en un árbol.

•

• Métodos:

a) En profundidad: Recorre el árbol por
subárboles.

1. Enorden
2. Preorden
3. Postorden

b) En amplitud: Recorre el árbol por niveles.

•

•

•

Los métodos en profundidad pueden
implementarse de forma recursiva e iterativa.
La forma iterativa requiere utilizar una pila.

El recorrido en amplitud se implementa de
forma iterativa con ayuda de una cola como
estructura de datos auxiliar.

Aplicación de estos algoritmos: acceso a
datos de almacenamiento en memoria
13
secundaria.

ALGORITMOS DE RECORRIDO

•

Recorrido recursivo enorden (IND):
1. Recorrer el subárbol izquierdo (I)
2. Visitar el nodo raíz (N)
3. Recorrer el subárbol derecho (D).

1

Resultado: 4-2-5-1-6-3-7

2

3

4

5

6

7

procedure enorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
enorden (Arbol^.iz);
write (Arbol^.info, ‘- ‘);
enorden (Arbol^.de)
end
end;

14

ALGORITMOS DE RECORRIDO

•

Recorrido recursivo preorden (NID):
1. Visitar el nodo raíz (N)
2. Recorrer el subárbol izquierdo (I).
3. Recorrer el subárbol derecho (D).

1

Resultado: 1-2-4-5-3-6-7

2

3

4

5

6

7

procedure preorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
write (Arbol^.info, ‘- ‘);
preorden (Arbol^.iz);
preorden (Arbol^.de)
end
end;

15

ALGORITMOS DE RECORRIDO

•

Recorrido recursivo postorden (IDN):
1. Recorrer el subárbol izquierdo (I).
2. Recorrer el subárbol derecho (D).
3. Visitar el nodo raíz (N).

1

Resultado: 4-5-2-6-7-3-1

2

3

4

5

6

7

procedure postorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
postorden (Arbol^.iz);
postorden (Arbol^.de);
write (Arbol^.info, ‘ - ‘)
end
end;

16

ALGORITMOS DE RECORRIDO
• Hay otras posibles combinaciones,
considerando recorrido primero el
subárbol derecho:
1. Enorden: DNI
2. Preorden: NDI
3. Postorden: DIN
Ejemplo. Deducir los tres recorridos en
profundidad del árbol binario siguiente:

7-3-6-1-5-2-4
1-3-7-6-2-5-4
7-6-3-5-4-2-1

•

A

B

C

D

E

F

G

H

I

J

Enorden: H-D-I-B-J-E-A-F-C-G
Preorden: A-B-D-H-I-E-J-C-F-G
Postorden: H-I-D-J-E-B-F-G-C-A

17

•

ALGORITMOS DE RECORRIDO
Recorrido iterativo en amplitud:
1. Tomar el puntero a la raíz y ponerlo en la cola.
2. Quitar el primer elemento de la cola, mostrar
el contenido del nodo y almacenar en la cola los
punteros correspondientes a sus hijos izquierdo y
derecho.
3. Repetir el paso 2.

procedure amplitud (Arbol: tArbol);
var A: tArbol; cola: tCola;
begin
Inicia (cola);
A:= Arbol;
if A<>nil then Encolar (cola, A);
while not EsVacia (cola) do
begin
Desencolar (cola, A);
write (A^.info, ‘ – ‘);
if A^.iz <> nil then Encolar (cola, A^.iz);
if A^.de <> nil then Encolar (cola, A^.de)
end
end;

18

ALGORITMOS DE RECORRIDO

•

Recorrido iterativo enorden (IND):
Se utiliza una pila donde almacenar punteros a
los distintos nodos del árbol.

2. Recupera de la pila y escribe 1. Como 1 no
3. Se recupera de la pila y se escribe el 6. Como
1. Se van colocando en la pila punteros, a la
raíz y los sucesivos hijos izquierdos de cada
tiene hijo derecho, recupera de la pila y escribe
no tiene hijo derecho, se pasa a recuperar de la
4. El hijo derecho de 4 es 6. Pone en la pila el
pila y a escribir el 8. El 8 tiene un hijo derecho,
nodo.
puntero a 6.
que se coloca en la pila. Después se coloca en la
pila el hijo izquierdo de 12 que será el que se
19
recupere a continuación.

ALGORITMOS DE RECORRIDO

•

Recorrido iterativo enorden (IND):

procedure enorden (Arbol: tArbol);
var A: tArbol; P: tPila;
begin

Inicia (P);
A := Arbol;
repeat
while A <> nil do
begin
Apilar (P, A);
A := A^.iz
end;
if not EsVacia (P) then
begin
Cima (P, A);
Desapilar (P);
write (A^.info, ‘ – ‘);
A := A^.de
end;
until EsVacia (P) and EsVacio (A)

end;

20

ÁRBOLES DE EXPRESIÓN

•

•

Los árboles binarios se utilizan para
almacenar expresiones aritméticas en
memoria, esencialmente en compiladores de
lenguajes de programación.

Los paréntesis no se almacenan en el árbol
pero están implicados en la forma del árbol.

(A + B) * C A + B * C

21

ÁRBOLES DE EXPRESIÓN

•

Ejemplo 1: Deducir las expresiones que
representan los siguientes árboles binarios.

Solución:
•

Ejemplo 2: Dibujar la representación en árbol
binario de cada una de las siguientes
a) X * (Y / - Z)
expresiones:
b) A + [ (B * - (C + D)]
a) X * Y / [ (A + B) * C ]
c) [A * ( X + Y)] * C
b) (X * Y / A) + (B * C)

22

•

•
•

ÁRBOLES BINARIOS

DE BÚSQUEDA

Árbol binario de búsqueda: Árbol binario
ordenado. El valor en el nodo raíz es mayor
que todos los del subárbol izquierdo y menor
que todos los del subárbol derecho.

Si recorremos el árbol enorden, está ordenado.
Las operaciones básicas sobre este tipo de
árboles binarios son:
a) Búsqueda
b) Inserción
c) Borrado
d) Recorridos

23

ESPECIFICACIÓN
TAD Árbol binario de búsqueda:
Busqueda (ABB, Clave) → ABB

•

Efecto: Devuelve el valor de una referencia al
nodo que tiene la clave buscada y nil si la
clave no está en el árbol.

Insertar (ABB, Clave) → ABB

Efecto: Introduce en el árbol como nodo hoja, la
clave pasada como valor de entrada.

Suprimir (ABB,