PDF de programación - Capítulo 1 Diseño e implementación de TADs arborescentes

Capítulo 1
Diseño e implementación de TADs
arborescentes1

Los ordenadores son buenos siguiendo
instrucciones, no leyendo tu mente

Donald Knuth

Resumen: En este tema se presentan los TADs basados en árboles, prestando espe-
cial atención a los árboles binarios. Además, se introducen distintos tipos de recorridos
usando tanto listas como iteradores.

1. Motivación

Queremos hacer un pequeño juego en el que la máquina pide al usuario que piense un

animal y ésta trata de adivinarlo haciendo distintas preguntas2:

¿Tiene cuatro patas? (Si/No)
no
¿Vive en el agua? (Si/No)
no
Mmmmmm, dejame que piense.....
Creo que el animal en que estabas pensando era...: ¡Serpiente!
¿Acerté? (Si/No)
si
¡Estupendo! Gracias por jugar conmigo.

Cuando la máquina falla, le pide al usuario que diga una pregunta que discrimine entre
el animal por el que apostó y el animal real que pensó. De esta forma, la aplicación aprende
de sus errores e incorpora en su base de conocimiento el nuevo animal. Si por ejemplo el
usuario pensó en el orangután, en la siguiente partida en vez de decir serpiente, seguiría

1Marco Antonio Gómez y Antonio Sánchez son los autores principales de este tema.
2Un clon de un antiguo juego de

la década de 1980,
llamado Animal, vegetal, mineral, http://www.amstrad.es/programas/amsdos/educativos/
animalvegetalmineral.php.

los ordenadores de 8 bits de

1

2

Capítulo 1. Diseño e implementación de TADs arborescentes

preguntando algo como ¿Es un reptil? para en base a la respuesta, contestar serpiente
u orangután.

¾Cómo implementarías la aplicación?

2.

Introducción

En el capítulo anterior estudiamos distintos TADs lineales para representar datos or-
ganizados de manera secuencial. En este capítulo usaremos árboles para representar de
manera intuitiva datos organizados en jerarquías. Este tipo de estructuras jerárquicas sur-
ge de manera natural dentro y fuera de la Informática:

Árboles genealógicos.

Organización de un libro en capítulos, secciones, etc.

Estructura de directorios y archivos de un sistema operativo.

Árboles de análisis de expresiones aritméticas.

2.1. Modelo matemático

Desde un punto de vista matemático, los árboles son estructuras jerárquicas formadas

por nodos, que se construyen de manera inductiva:

Un solo nodo es un árbol a. El nodo es la raiz del árbol.

Dados n árboles a1, . . . , an, podemos construir un nuevo árbol a añadiendo un nuevo
nodo como raíz y conectándolo con las raíces de los árboles ai. Se dice que los ai son
subárboles de a.

Para identicar los distintos nodos de un árbol, vamos a usar una función que asigna

a cada posición una cadena de números naturales con el siguiente criterio:

Estructura de Datos y Algoritmos

2. Introducción

3

Figura 1: Posiciones y valores de cada nodo de un árbol.

La raíz del árbol tiene como posición la cadena vacía
.
Si un cierto nodo tiene como posición la cadena α ∈ ℵ∗, el hijo i-ésimo de ese nodo
tendrá como posición la cadena α.i.

de sus nodos.

Por ejemplo, la gura 1 muestra un árbol y las cadenas que identican las posiciones
Un árbol puede describirse como una aplicación a : N → V donde N ⊆ ℵ∗ es el
conjunto de posiciones de los nodos, y V es el conjunto de valores posibles asociados a los
nodos. Podemos describir el árbol de la gura 1 de la siguiente manera:

N = {
, 1, 2, 3, 1.1, 1.2, 3.1, 3.2, 3.3, 3.4, 3.3.1, 3.3.2}
V = {A, B, C, D, E, F, G}

a(
) = A
a(1) = B
a(1.1) = A

a(2) = A
a(1.2) = C

a(3) = D
a(3.1) = E

etc.

2.2. Terminología

Antes de seguir adelante, debemos establecer un vocabulario común que nos permita

describir árboles. Dado un árbol a : N → V

Cada nodo es una tupla (α, a(α)) que contiene la posición y el valor asociado al nodo.
Distinguimos 3 tipos de nodos:

• La raíz es el nodo de posición
.
• Las hojas son los nodos de posición α tales que no existe i tal que α.i ∈ N
• Los nodos internos son los nodos que no son hojas.

Un nodo α.i tiene como padre a α, y se dice que es hijo de α.
Dos nodos de posiciones α.i y α.j (i = j) se llaman hermanos.

Facultad de Informática - UCM

4

Capítulo 1. Diseño e implementación de TADs arborescentes

Un camino es una sucesión de nodos α1, α2, . . . αn en la que cada nodo es padre del
siguiente. El camino anterior tiene longitud n.

Una rama es cualquier camino que empieza en la raíz y acaba en una hoja.

El nivel o profundidad de un nodo es la longitud del camino que va desde la raíz
hasta al nodo. En particular, el nivel de la raíz es 1.

La talla o altura de un árbol es el máximo de los niveles de todos los nodos del árbol.

El grado o aridad de un nodo interno es su número de hijos. La aridad de un árbol
es el máximo de las aridades de todos sus nodos internos.

Decimos que α es antepasado de β (resp. β es descenciente de α) si existe un camino
desde α hasta β.

Cada nodo de un árbol a determina un subárbol a0 con raíz en ese nodo.

Dado un árbol a, los subárboles de a (si existen) se llaman árboles hijos de a.

2.3. Tipos de árboles

Distinguimos distintos tipos de árboles en función de sus características:

Ordenados o no ordenados. Un árbol es ordenado si el orden de los hijos de cada
nodo es relevante.

Generales o n-ários. Un árbol es n-ário si el máximo numero de hijos de cualquier
nodo es n. Un árbol es general si no existe una limitación jada al número máximo
de hijos de cada nodo.

3. Árboles binarios: operaciones

Un árbol binario consiste en una estructura recursiva cuyos nodos tienen como mucho
dos hijos, un hijo izquierdo y un hijo derecho. El TAD de los árboles binarios (lo llamaremos
Arbin) tiene las siguientes operaciones:

ArbolVacio: operación generadora que construye un árbol vacío (un árbol sin nin-
gún nodo).

Cons(iz, elem, dr): segunda operación generadora que construye un árbol bi-
nario a partir de otros dos (el que será el hijo izquierdo y el hijo derecho) y de la
información que se almacenará en la raíz.

raiz: operación observadora que devuelve el elemento almacenado en la raíz del
árbol. Es parcial pues falla si el árbol es vacío.

hijoIz, hijoDr: dos operaciones observadoras (ambas parciales) que permiten ob-
tener el hijo izquierdo y el hijo derecho de un árbol dado. Las operaciones no están
denidas para árboles vacíos.

esVacio: otra operación observadora para saber si un árbol tiene algún nodo o no.

Con sólo estas operaciones la utilidad del TAD está muy limitada. En apartados si-

guientes lo extenderemos con otras operaciones observadoras.

Estructura de Datos y Algoritmos

4. Implementación de árboles binarios

5

4.

Implementación de árboles binarios

Igual que ocurre con los TADs lineales, podemos implementar el TAD Arbin utilizando
distintas estructuras en memoria. Sin embargo cuando la forma de los árboles no está
restringida la única implementación factible es la que utiliza nodos.

La intuición detrás de la implementación es sencilla y sale directamente de las repre-
sentaciones de los árboles que hemos utilizado en la sección anterior: cada nodo del árbol
será representado como un nodo en memoria que contendrá tres atributos: el elemento
almacenado y punteros al hijo izquierdo y al hijo derecho.

No obstante, no debe confundirse un elemento del TAD Arbin de la estructura en
memoria utilizado para almacenarlo. Si bien existe una transformación directa entre uno
y otro son conceptos distintos. Un árbol es un elemento del TAD construido utilizando
las operaciones generadoras anteriores (y que, cuando lo programemos, será un objeto de
la clase Arbin); los nodos en los que nos basamos forman una estructura jerárquica de
nodos que tiene sentido únicamente en la implementación. Veremos en la implementación
que hay métodos (privados o protegidos) que trabajan directamente con esta estructura
jerárquica a la que el usuario del TAD no tendrá acceso directo (en otro caso se rompería
la barrera de abstracción impuesta por las operaciones del TAD).

A continuación aparece la denición de la clase Nodo que, como no podría ser de otra
manera, es una clase interna a Arbin. La clase Arbin necesita únicamente almacenar un
puntero a la raíz de la estructura jerárquica de nodos que representan el árbol3.

template <class T>
class Arbin {
public:

...

protected:

/∗∗
C l a s e nodo que almacena i n t e r n a m e n t e
y l o s p u n t e r o s a l h i j o i z q u i e r d o y a l h i j o d e r e c h o .
∗/
class Nodo {
public:

e l

e l e m e n t o ( de t i p o T) ,

Nodo() : _iz(NULL), _dr(NULL) {}
Nodo(const T &elem) : _elem(elem), _iz(NULL), _dr(NULL) {}
Nodo(Nodo *iz, const T &elem, Nodo *dr) :

_elem(elem), _iz(iz), _dr(dr) {}

T _elem;
Nodo *_iz;
Nodo *_dr;

};

...

private:

/∗∗
Puntero a l a r a í z de l a e s t r u c t u r a j e r á r q u i c a
de nodos .

3Estas estructuras jerárquicas de nodos son útiles también para resolver otros problemas distintos a la

implementación del TAD de los árboles binarios; ver por ejemplo el ejercicio 13.

Facultad de Informática - UCM

Capítulo 1. Diseño e implementación de TADs arborescentes

6

};

∗/
Nodo *_ra;

El invariante de la representación de esta implementación debe asegurarse de que:

Todos los nodos contienen información válida y están ubicados correctamente en
memoria.

El subárbol izquierdo y el subárbol derecho no comparten nodos.

No hay ciclos entre los nodos, o lo que es lo mismo, los nodos alcanzables desde al
raíz no incluyen a la propia raíz.

Con estas ideas el invariante queda:

RArbinT (p)

⇐⇒def

buenaJerarquia(p._ra)

donde

buenaJerarquia(ptr) = true
buenaJerarquia(ptr) = ubicado(ptr) ∧ RT (ptr._elem)∧

nodos(ptr._iz) nodos(ptr._dr) = ∅∧

ptr ∈ nodos(ptr._iz)∧
ptr ∈ nodos(ptr._dr)∧
buenaJerarquia(ptr._iz)∧
buenaJerarquia(ptr._dr)

si ptr = null

si ptr = null

nodos(ptr) = ∅

nodos(ptr) = {ptr} nodos(ptr._iz) nodos(ptr._dr) si ptr = null

si ptr = null

La denición de la relación de equivalencia que se utiliza para saber si dos árboles son

o no iguales también sigue una denición recursiva:

p1 ≡