Programación Modular. ETSIT. 1o C.

Guión del profesor Juan Falgueras

Curso 2005
versión: 23 de mayo de 2005

6
Árboles

Contenido
6. Tipos de datos abstractos 1
6.1. Árboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
6.1.1. Conceptos previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
6.1.2. Representaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
6.1.3. Terminologı́a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
6.1.4. Propiedades de los árboles n-arios . . . . . . . . . . . . . . . . . . . . . . . 4
6.1.5. Árboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.2. TDA árbol binario (ArbolB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2.2. Especificación del TDA ArbolB . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2.3. Definiciones y propiedades sobre los Arboles Binarios . . . . . . . . . . . . . 11
6.2.4. Árboles balanceados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.2.5. Aplicaciones de los ArbolB . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3. Iteradores sobre árboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.3.1. Árboles entrelazados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.4. Árboles de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.5. Prácticas y ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.6. Apendice A: Técnicas de Compresión . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.6.1. Codificado de secuencias (Run-Length encoding) . . . . . . . . . . . . . . . 24
6.6.2. Codificado de longitud variable . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.7. Referencias de consulta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6. Tipos de datos abstractos

6.1. Árboles
En este apartado se tratará de una forma general la estructura de datos árbol, que es funda-
mental en informática. Comenzaremos resumiento las definiciones más elementales con la máxima
precisión. Presentaremos los axiomas más generales válidos para árboles de cualquier tipo. Poco a
poco iremos concretando en problemas y estructuras más particulares el TDA árbol binario, Ar-
bolB, elemental, nos servirá para introducir los conceptos de recorridos básicos a través de árboles;
definiremos también otra serie especial de estructuras arbóreas (como los árboles balanceados),
que tienen particulares propiedades, útiles para mejorar las implementaciones.
Sin dejar este TDA ArbolB sencillo, veremos formas de implementación (como la entrelazada)
que optimizan los recorridos fundamentales.

Nótese que no hablamos de TDA árbol ya que aunque lo tratemos como tal, desde
el punto de vista de una especificación más o menos abstracta, no estamos al nivel
de abstracción del que disfrutábamos con los TDAs pila, cola, etc.; en aquellos la idea
6.1 Árboles 2

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

6.1.1. Conceptos previos

Las listas, pilas y colas son estructuras lineales (unidimensionales, si se quiere); los conjuntos
y diccionarios en principio carecen de estructura1 ; los árboles son estructuras que podemos llamar
bidimensionales o de enlaces bidimensionales.
Las estructuras de árbol permiten describir jerarquı́as de dependencias de muchos tipos. Un
buen ejemplo de tales estructuras no técnicas son los árboles de familia. En los árboles de familia se
sitúa al hijo como origen y de él se relacionan sus dos padres, por ejemplo, madre a su izda, padre
a su drch; a su vez, cada ancestro lleva sus dos padres asociados, etc. Otra importante variante
de este tipo de árboles es el diagrama lineal. En este último, el origen es el padre de una serie
de descendientes que a su vez son los padres de otros, ramificándose cada uno en varios o ningún
descendiente.
Una definición general de la estructura recursiva TDA árbol es:

Definición Un árbol es o bien el vacı́o o bien un dato con el que están relacionados otra serie
disjunta (no interrelacionada) de n ≥ 0 árboles, junto con sus procedimientos de acceso.

Ante esta definición podemos decir que una lista es un tipo de árbol con n = 1, un árbol binario
tendrá n = 2, etc. Genéricamente un árbol n-ario puede tener en cada nodo desde 0 hasta n árboles
(o “subárboles”), aunque todos o ninguno de estos n subárboles pueden estar vacı́os.
Más adelante veremos otros tipos de árboles, los multicamino que permiten más de un elemento
informativo en cada árbol o nodo de árbol como veremos y, veremos, los árboles generales, que
permiten una secuencia (lista no acotada) de nodos, siendo realmente una lista de árboles con
subárboles2 . Notemos que el elemento informativo puede ser múltiple en algunos casos (como
veremos en los árboles de Bayer, llamados B-Tree, que se usan en el indexado de ficheros.).
De lo anterior se desprende que la caracterı́stica esencial de los árboles es la de no disponer
de ciclos o enlaces de los descendientes con los ancestros: las relaciones son jerárquicas: ningún
descendiente puede ser ancestro de su ancestro. Esto, por supuesto sı́ está permitido en los grafos,
como veremos, desapareciendo allı́ el concepto de niveles, de ancestros y de descencientes dispuestos
jerárquicamente.
La definición dada antes es necesariamente recursiva. La estructura árbol lleva ı́ntimamente
asociada la recursividad. La mayorı́a de los procedimientos de acceso y utilidades sobre árboles
son recursivas por naturaleza. Piénsese que el tipo array o el tipo lista lineal pueden naturalmente
ser descritos iterativamente. En este sentido, cada vez que operemos o analicemos un árbol, em-
plearemos el mismo procedimiento recursivamente sobre sus árboles descendientes. Sólo en algunos
casos podremos conseguir recorrer el árbol sin necesidad de recurrir sobre los subárboles, tan sólo
iterar sobre ellos. En la estructura árbol, cada descendiente relacionado es a su vez un árbol por
lo que vuelve a estar en la misma situación que el original: vuelve a aplicarse el mismo proceso.

6.1.2. Representaciones
Podemos ver en la Figura 1 diversas formas de representar las estructuras arbóreas en las que
se refleja el que un nodo está relacionado con subnodos y estos a su vez con otros, etc. (y que
los subnodos son disjuntos). Ası́ aparecen representaciones que son conjuntos incluı́dos (nótese,
siempre disjuntos), parentizada e indentada. Pero la forma más clara y frecuente es la de grafo.
Ver Figura 23
1 visible externamente, todos los TDAs tienen que estructurarse en su implementación pero esta estructura es

evidenciable o no externamente. En el caso de los conjuntos no lo es, sı́ en las listas, pilas, árboles, etc.
2 Curiosamente los árboles generales no necesitarán tener definido árbol vacı́o, ya que admiten una lista vacı́a de

descendientes
3 Esta forma es algo más difı́cil de lograr en la pantalla de un ordenador.
6.1 Árboles 3

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

Figura 1: Representación de árboles.

Figura 2: Representación de un árbol como grafo.

6.1.3. Terminologı́a
Antes de dar definiciones más concretas de árboles vamos a dar nombre a cada parte de estas
estructuras:

enlace (arco, branch) Dependencia de un nodo con otro

raiz (root) Información asociada al primer árbol que no depende de otro anterior
nodo (node) Una raiz más el conjunto de dependencias
subárbol (subtree) Cada uno de los árboles que dependen de una raiz
hijo (child, descendent) Raices de los subárboles (respecto a la raiz principal)
padre (direct ancestor, parent) Respecto a las raices de los subárboles, la raiz del árbol
hermano. . . (sibling. . . ) Nodo en el mismo nivel. Se puede también hablar de abuelo, nieto,
primo, etc. considerando al árbol como una jerarquı́a familiar con la raiz como origen.
grado (degree) Número de subárboles no vacı́os (enlaces) de un nodo
grado de un árbol Máximo posible de los grados del árbol
hoja (leaf, terminal node, external nodes) Nodo de grado cero
nodo interno Nodos de grado distinto de cero
camino (path) de un nodo es la secuencia de nodos por los que hay que descender (de padre a
hijo) desde la raiz hasta él. Si es desde el nodo a0 al nodo aN de un subárbol; Camino serı́a
a0 , . . . , tN , con ai+1 descendiente de ai (0 ≤ i < N )
camino (path) entre dos nodos es la secuencia de nodos por los que hay que pasar para comunicar
uno con otro. Esta secuencia podrá hacerse de hijos a padres y después de padres a hijos
antecesores (ancestors) Conjunto de nodos del camino
mı́nimo ancestro común (least common ancestor ) De dos nodos que no son ancestro el uno del
otro, es el primer nodo común en los caminos de esos nodos hacia la raiz. Es único.
6.1 Árboles 4

nivel (level ) De un nodo es el número de descendencias que haya que hacer desde la raiz hasta
llegar al nodo. La raiz está en el nivel 1.

hermano (sibling) Nodos con el mismo padre. A veces también se entienden como hermanos a
los primos, nodos en el mismo nivel.

altura (high, profundidad, depth) Máximo nivel de todos los nodos de un árbol

longitud de camino de un nodo Número de arcos que hay que tomar desde la raiz del árbol
para llegar al nodo. Es igual al valor del nivel del nodo.

lista de nivel (level list) Lista de nodos en el mismo nivel

bosque (forest) Conjunto de n ≥ 0 árboles disjuntos. Si se elimina un nodo no hoja de un árbol

queda un bosque

camino interno (longitud de camino de un árbol ) suma de las longitudes de camino (niveles) de
todos sus componentes. Por ejemplo, el camino interno de

P
es 16. Si es ni el número de nodos en
Pel nivel i, la longitud de camino interno es C = i ni · i
y el camino interno medio CI = n1 i ni · i.
nodo especial (nodo imaginario) Nodo no existente añadido a un enlace vacante de otro nodo.

camino externo Creando nodos imaginarios en todos los brazos vacantes del árbol n-ario, el
camino externo es la suma de los caminos de de esos nodos imaginarios. Por ejemplo, en la
Figura 3 se tiene un camino externo de 54. De nuevo, si el número de nodos especiales en el

Figura 3: Caminos externos.

1
P
nivel i es mi , el camino externo medio serı́a: CE = m i mi · i.

lleno (full, perfectamente balanceadado) Árbol n-ario que tiene todos los nodos con grado n,
excepto las hojas que se hayan todas al mismo nivel con grado 0.

6.1.4. Propiedades de los árboles n-arios

A continuación damos un conjunto de propiedades que sirven para cualquier árbol n-ario, esto
es, árbol con un máximo número de hijos por nodo.

Lema 1 Hay un camino único que pueda unir dos nodos cualesquiera.
6.1 Árboles 5

Prueba: Si los dos nodos están en el mismo camino desde la raiz a alguno de ellos, siendo este
camino único, cumplirı́an esta propiedad. Pero si no, sabemos que cualesquiera dos nodos de un
árbol tienen un mı́nimo ancestro común (mac), este debe existir (podrı́a ser la raiz). Tomando
entonces el camino desde un nodo al mac y desde el mac al otro tenemos el camino único buscado.


Lema 2 El máximo número de nodos de un árbol g-ario de altura h o número de nodos de

un árbol g-ario lleno de altura h es:
h−1
X gh − 1
Ng (h) = 1 + g + g 2 + · · · + g h−1 = gi =
i=0
g−1

Prueba: La demostración es inmediata observando la forma de reproducción del árbol desde la

raiz, (1 +), el segundo nivel, (g nodos +), el tercer nivel, (cada uno de los g anteriores g veces: g 2
+) etc. 

Lema 3 El número de arcos reales B de un árbol binario es el de nodos menos 1:

B =n−1

Prueba: Cualquier nodo, excepto la raiz lleva un arco asociado. 

Lema 4 Si m es el número de enlaces vacantes y n el de nodos de un árbol g-ario, se cumple:

m = (g − 1) n + 1

Prueba: De 3 si contamos los nodos especiales m, el total de arcos posibles (reales + especiales)
de un árbol g-ario será m+n−1. Por otro lado, para n nodos existen g ·n posibles arcos. Igualando
ambas cantidades, nos queda la expresión buscada. 

6.1.5. Árboles Binarios

Los árboles binarios son árboles n-arios con n = 2. Tienen pues las propiedades antedichas
para árboles n-arios; y, en concreto:
De los lemas 2 y 4 podemos extraer:

Lema 5 (a) El número máximo de nodos en el nivel i de un árbol binario es 2i−1 , con i ≥ 1 y
(b) el máximo número de nodos de un árbol binario de altura k es: 2k − 1, con k ≥ 1

Prueba: (b): Basta con sustituir g = 2 en el lema 2.

(a) Por inducción en i: para i = 1, en la raiz, se cumple que el número máximo de nodos es 20 = 1.
Supongamos que es válido para j, con 1 ≤ j < i; entonces el máximo número de nodos para
el nodo anterior a i será 2i−2 y, dado que cada nodo en un árbol binario puede tener hasta dos
descendientes, el máximo número de nodos en el nivel i será dos veces el del nivel i − 1, esto es:
2 · 2i−2 = 2i−1 . 

Lema 6 Para cualquier árbol binario no vacı́o, si n0 es el número de hojas y n2 el número de

nodos de grado 2, entonces: n0 = n2 + 1

Prueba: Si es n1 el número de nodos de grado 1 y n el total de nodos, se tendrá:

n = n0 + n1 + n2 (1)

Repasando el Lema 4 recordamos que el total de arcos reales en un árbol (binario) es igual al
número de nodos menos 1, ya que la raiz no lleva arco asociado. Sea B ese total de arcos, tenemos:
6.1 Árboles 6

n = B + 1. Por otro lado de un nodo de grado 1 emana 1 arco, mientras que si es de grado dos,
son dos: B = n1 + 2n2 . Tenemos:
n = 1 + n1 + 2n2 (2)
Restando 2 de 1 nos queda:
n0 = n2 + 1. 
6.2 TDA árbol binario (ArbolB) 7

6.2. TDA árbol binario (ArbolB)

6.2.1. Definición
Un árbol binario es o el vacı́o o un ı́tem (llamado raı́z —root) junto con dos árboles binarios
(lt, rt), izquierdo y derecho (lefttree, righttree).

6.2.2. Especificación del TDA ArbolB

Especificación formal del TDA ArbolB

Nombre: ArbolB (Base)

Conjuntos:
T: conjunto de los Árboles Binarios
I: conjunto de items de tipo Base
B: (false, true)
E: Excepciones

Especificaciones Sintácticas:
ArbolB: →T
ArbolB: T ×I ×T →T
EstaVacio: T →B
Raiz: T →I ∪ E
Izda: T →T ∪ E
Dcha: T →T ∪ E

Axiomas:
A1) EstaVacio(ArbolB()) ::= true
A2) EstaVacio(ArbolB(lt, x, rt)) ::= false
A3) Raiz(ArbolB()) ::= error
A4) Raiz(ArbolB(lt, x, rt)) ::= x
A5) Izda(ArbolB()) ::= error
A6) Izda(ArbolB(lt, x, rt)) ::= lt
A7) Dcha(ArbolB()) ::= error
A8) Dcha(ArbolB(lt, x, rt)) ::= rt

Especificaciones Constructivas:
ArbolB()

Pre ::= Ninguna
Ret ::= ( )
ArbolB ( ArbolB lt; x : Base; ArbolB rt)
Pre ::= lt ∈ T ; rt ∈ T
Post ::= lt0 = lt; x0 = x; rt0 = rt
Ret ::= (lt, x, rt)
B bt->EstaVacio()

Pre ::= bt ∈ T
Post ::= bt = bt0
Ret ::= bt0 = ( )
6.2 TDA árbol binario (ArbolB) 8

I bt->Raiz
 ( )
Pre ::= bt ∈ T ; bt 6= ( )
Post ::= bt = bt0
Ret ::= x
ArbolB bt->Izda ( )
Pre ::= bt ∈ T ; bt =6 ()
Post ::= bt = bt0
Ret ::= lt
ArbolB bt->Dcha ( )
Pre ::= bt ∈ T ; bt = 6 ()
Post ::= bt = bt0
Ret ::= rt
Al devolver en los objetos de tipo árbol, estamos tratando de emplear una “sintaxis funcio-
nal” con los árboles. Recordemos que hasta ahora la sintaxis de los métodos era procedural: se
modificaba el objeto con las llamadas a sus métodos. Ahora se llama al método de un árbol pero
se devuelve otro. Este cambio de estrategia que va en perjuicio de:
1. un reciclado de basura. Los objetos árbol a los que se llama pueden perderse en asignaciones.
2. Se pierde fiabilidad en el uso de los objetos, sobre todo en asignaciones y reconocimiento del
estado de los parámetros, ya que al pretender asignar el resultado de una llamada a método,
la asignación puede no ser válida por no ser válido el tipo de árbol usado en la llamada. Si
la sintaxis fuese procedural podrı́a controlarse algo mejor esto.
3. Posibilidad de control de precondiciones y mantenimiento de errores internos garantizando
las postcondiciones
y esto es debido, sobre todo en la necesidad de la recursividad, que se hace frecuente uso en los
algoritmos sobre árboles. Si no se utilizan procedimientos de aspecto funcional4 nos encontrarı́amos
con los procedimientos en los que todo se hace con parámetros por referencia (como será necesario
en C++) y, en las llamadas recursivas esto implicarı́a la creación de múltiples variables temporales
que complicarı́an excesivamente el código. Por ejemplo, supongamos que queremos calcular el
número de nodos de un árbol; esto se puede hacer iterativamente mediante el uso de pilas y
bucles, como veremos, pero es mucho más fácil recursivamente.
Supongamos, sin embargo, que los procedimientos de acceso al TDA ArbolB se han hecho “pro-
ceduralmente” mediante parámetros por referencia (en concreto serı́a: Izda(ArbolB b, ArbolB *lt)).
Para contar recursivamente el número de nodos basta con contar el nodo en que empezamos y
sumarle el número de nodos del subárbol izquierdo además del número de nodos del subárbol
derecho.
1 int b->NumNodos() {
2 ArbolB t; int tmp;

4 if (b->EstaVacio()) return 0;
5 else {
6 Izda(b, &t);
7 tmp = NumNodos(t);
8 Dcha(b, &t);
9 RETURN tmp + t->NumNodos() + 1;
10 }
11 }

Esto, realizado en “C++ a la funcional”:

4 C++ no tiene mucho de lenguaje funcional. Aunque es capaz de admitir la definición de un método de copia

implı́citamente llamado en el paso por copia de los parámetros y en las asignaciones, serı́a necesario efectivamente
copiar toda la estructura, ya que si no a la vuelta de las llamadas, el correspondiente operador de destrucción,
también llamado implı́citamente entonces, destruirı́a el árbol referenciado en el parámetro inicial, el original. El
copiar toda la estructura es altamente ineficiente. El abordar todas las situaciones conflictivas en las que puede
hacer falta la copia es más complejo, en C++, de lo pretendido respecto a ese lenguaje a este nivel.
6.2 TDA árbol binario (ArbolB) 9

1 int b->NumNodos()
2 {
3 if (b->EstaVacio()) return 0;
4 else return b->Izda()->NumNodos()+b->Dcha()->NumNodos()+1;
5 }

Este es un ejemplo muy sencillo por lo que más adelante nos replantearemos esta cuestión.

Costructores y selectores En nuestra definición del TDA árbol binario aparecen dos cons-
tructores: ArbolB() y ArbolB(l,x,r); mientras aparecen los selectores EstaVacio, Raiz, Izda y
Dcha. No se han definido aún iteradores.
ArbolB() es un constructor especial del árbol vacı́o. Se puede entender, si se quiere, como la
constante “árbol binario vacı́o”.
El operador ArbolB(l,x,r) para la (modificación) construcción de un árbol binario obligan a
modificaciones globales de cada nodo, no se puede modificar un componente de un nodo, ası́mismo,
las modificaciones de un subárbol son imposibles (ver ejercicio 2), aisladamente.
La construcción con ArbolB(l,x,r) se realiza de abajo (hojas) a arriba; necesariamente las
hojas deben tener en su construcción árboles vacı́os. Por ejemplo:
1 b= ArbolB(ArbolB(ArbolB(ArbolB(), ’D’, ArbolB()),
2 ’B’,
3 ArbolB()),
4 ’A’,
5 ArbolB(ArbolB(ArbolB(), ’E’, ArbolB(),
6 ’C’,
7 ArbolB(ArbolB(), ’F’, ArbolB())) \pict{0}{0}{grf/[Link]}
8 )

Excepciones Las excepciones más importantes propias del TDA son la de la búsqueda de una
raiz (o de un subárbol izquierdo/derecho) en un árbol vacı́o.

Formas de implementación Las formas de implementación más importantes de los árboles

van a ser las dinámicas, sin embargo las estáticas pueden aportar eficiencia y simplicidad. Una
implementación muy interesante la sugiere la siguiente numeración ordenada por niveles de un árbol
binario lleno que vemos en la Figura 4. Ya que este árbol contiene el máximo número de elementos

Figura 4: Numeración de un árbol binario.

posibles, una representación estática que reserve espacio para sus elementos nos servirá para todos
los posibles árboles binarios con ese número de niveles. La numeración por niveles sugiere que para
árboles binarios de altura h podemos emplear un array o vector de 2h − 1 celdas al menos sabiendo
que nos podremos mover de un nodo al descenciende mediante una sencilla y rápida equación:
Lema 7 Si un árbol binario lleno con n nodos (y altura Altura = blog2 (n + 1)c) se representa
secuencialmente, como en la gráfica anterior, entonces, para cualquier nodo de ı́ndice i, 1 ≤ i ≤ n
tenemos:
Padre(ti ) = tbi/2c ; 1 < i ≥ n
Izda(ti ) = t2i ; 2i ≤ n
Dcha(ti ) = t2i+1 ; 2i + 1 ≤ n
 6.2 TDA árbol binario (ArbolB) 10

Prueba: Es directa por inducción en i. Se deja como ejercicio.

Esta forma de implementación, para seguir la sintaxis funcional del interfaz, requiere copiar
la estructura, antes de operar con ella o de devolver alguna parte de ella.
cursores
La forma acotada mediante cursores es muy importante por su caracterı́stica principal de no
requerir punteros. Esto es imprescindible cuando se quiere mantener una estructura entrelazada
como el árbol soportada o almacenada en un medio que no sea la memoria principal de un compu-
tador. Supongamos, por ejemplo, que se quiere almacenar un recurso gráfico, como una ventana
de diálogo, como parte de un fichero. Normalmente, estos recursos se representan mediante es-
tructuras arbóreas en las que una región de la ventana contiene jerárquicamente otra serie de
“descendientes” y ası́ recursivamente. Ver Figura 5. de esta forma las relaciones se simplifican

Figura 5: Diálogos en interfaces de usuario WIMP, evidenciando su estructura arbórea.

respecto a la raiz más cercana, tanto en coordenadas, como en agrupación, etc. Por ejemplo, las
coordenadas de los objetos pertenecientes a otro objeto se pueden dar en forma relativa a aquél,
de esta forma la localización y el movimiento conjunto de objetos es más rápida: por ejemplo,
saber si las coordenadas de un cursor gráfico están dentro de un objeto se hacen jerárquicamente,
averiguando si están dentro de las del objeto padre, primero.
Este es el caso realmente de un árbol general que podrı́a mejor ser implementado como se ve
en la Figura 6, donde los cursores son números enteros indicativos del desplazamiento respecto al

Figura 6: Implementación de un árbol como cursor tı́pica en la representación de diálo-

gos y ventanas.

origen del bloque. Opcionalmente el último de los hermanos puede apuntar convenenientemente al
padre. La implementación de un árbol binario con cursores es más simple que esta, pero vemos,
en general la necesidad de un bloque de memoria principal (que puede cargarse de una memoria
secundaria —disco, en una única operación) con celdas estructurando los nodos.
dinámica
La implementación más interesante es, para nosotros, la dinámica, ya que es más simple (siempre
que ignoremos el correcto uso de la memoria), y con más libertades que la estática.
Haremos uso en general de las formas más simples de implementación, sin cabeceras ni excesiva
información extra. Con esto estamos siguiendo la idea de simplicidad en los algoritmos iniciada
con la sintaxis “a lo funcional” de los procedimientos de acceso.
Una estructura dinámica sencilla válida para un árbol binario serı́a:
1 typedef char Base;

3 class ArbolB {
4 public:
5 ArbolB();
6 ArbolB(ArbolB *iz, Base x, ArbolB *de);
7 ~ArbolB(void);
6.2 TDA árbol binario (ArbolB) 11

8 bool EstaVacio();
9 Base Raiz();
10 ArbolB *Izdo();
11 ArbolB *Decho();
12 private:
13 bool estoyVacio;
14 Base raiz;
15 ArbolB *izdo;
16 ArbolB *drch;
17 };

Interfaces de las clases-TDA árbol binario. Para poder hacer llamadas recursivas sobre los resulta-
dos de otras llamadas tipo 1 + NumNodos(Izdo()) (en la que ponemos como parámetro por copia
otro árbol), hemos recurrido a usar punteros a los objetos, de manera que no se copien los propios
objetos al ser devueltos. Nótese la existencia de dos tipos de creadores, uno para el árbol vacı́o y
otro para un árbol con información. Como ambos objetos han de ser tratados equivalentemente y
no queremos hacer clases compuestas hemos recurrido a ’marcar’ el árbol como vacı́o o lleno con
un atributo booleano. Esto permite la manipulación de un objeto del mismo tipo que responda a
preguntas tipo “EstaVacio()”.
Con esta forma de implementación podremos jugar con los procedimientos más tı́picos de
árboles en forma recursiva, sin problemas de copia. El único inconveniente es la necesidad de usar
punteros a árboles. Por ejemplo:
1 int NumNodos(ArbolB *a)
2 {
3 if (a->EstaVacio())
4 return 0;
5 else
6 return 1 + NumNodos(a->Izdo()) + NumNodos(a->Decho());
7 }

La implementación completa del árbol se deja como ejercicio (ver 3).

6.2.3. Definiciones y propiedades sobre los Arboles Binarios

Veamos las definiciones del apartado 6.1.3 para el TDA ArbolB:
Número de elementos serı́a, como ya hemos visto, [NumNodos : T → N ]
∀t ∈ T, NumNodos(t) ≡ si EstaVacio(t) entonces
0
sino


1 + NumN odos Izda(t) + NumNodos Dcha(t)
finsi
k
Camino ([Camino : (T × T ) → (T × T )]) Un camino entre dos nodos de un árbol ti y tk es la
secuencia de nodos ti , t0 , t00 , . . . , tk del árbol que satisface:
 
0 00 (n Dcha
Camino(ti , tk ) = (ti , t , t , . . . , tk ) | ∀ (n : t = (t(n−1 )
Izda


Hoja ([EsHoja : T →
B]) Un árbol t se dice hoja si ¬EstaVacio(t) ∧ EstaVacio Izda(t) ∧
EstaVacio Dcha(t)
Altura ([Altura : T → N ]) Llamaremos altura (“Altura”) o profundidad (“depth”) de un árbol
binario al máximo de los cardinales de todos los caminos:
∀t ∈ T, Altura(t) ≡ si EstaVacio(t) entonces
0
sino 


1 + máx Altura Izda(t) , Altura Dcha(t)
finsi
6.2 TDA árbol binario (ArbolB) 12

Camino mı́nimo ([CamMin : T → N ]) LLamaremos camino mı́nimo al mı́nimo de los cardinales

de todos los caminos desde la raiz a las hojas:

∀t ∈ T, Altura(t) ≡ si EstaVacio(t) entonces

0
sino



1 + mı́n CamMin Izda(t) , CamMin Dcha(t)
finsi

Donde se ha utilizado [mı́n, máx : N × N → N ]:

máx(a, b) ≡ si a < b entonces b sino a finsi

mı́n(a, b) ≡ si a < b entonces a sino b finsi

n
Lista Nivel ([ListaNivel : T × N → (T × T )]) Lista de nodos a la altura k:

∀t ∈ T, k ∈ N Nivel(t, k) ≡
si EstaVacio(t) entonces
()
sino
si k = 1 entonces
(Raiz(t))
sino



Concatenar Nivel Izda(t), n − 1 , Nivel Dcha(t), n − 1
finsi
finsi

Nivel 2

Nivel 4

Figura 7: Niveles en un árbol.

El que los nodos vacantes se denotan en la ListaNivel como vacı́os o, por el contrario, no se
denoten (no queden ‘huecos’ en la lista), quedando acumulados todos los nodos existentes al
comienzo de la lista depende del funcionamiento de Concatenar que es la función encargada de
encadenar las sublistas vacı́as que pueden aparecer.

6.2.4. Árboles balanceados

Vamos a ver las propiedades de árbol lleno o perfectamente balanceado, y balanceado (sóla-
mente) o completo.
Definición Un árbol t se dice lleno o perfectamente balanceado (ABPB) si Altura(t) =
CamMin(t). ABPB(ArbolB()) = true.

Propiedades
Lema 8 Un árbol t de Altura(t) = k es ABPB sii k = 0 ó t tiene dos subárboles de Altura= k − 1
ABPB.
6.2 TDA árbol binario (ArbolB) 13

Prueba: (⇒) Si t es ABPB eliminando la raiz, nos quedamos con dos árboles Izda(t) y Dcha(t),
cuyos Altura y CamMin son menores en 1 que los de t, por la definición. Por otro lado (⇐) si
tenemos dos árboles t1 y t2 de alturas k − 1 y ABPB, el árbol ArbolB(t1 , Raiz(t), t2 ) tiene por la
definición de Altura, 1 + k − 1 y análogamente tiene camino mı́nimo k, con lo que es ABPB. 
Ya hemos visto (lema 5) que el número de nodos de un ABPB será NumNodos(ABP B) =
2k − 1. Y por tanto, Altura(ABPB) = log2 (n + 1), (lo que hace, por ejemplo, que un árbol binario
de 8 elementos no pueda ser ABPB).

Definición Un árbol se dice balanceado o completo si tiene profundidad mı́nima, es decir:

Altura(t) ≤ blog2 (n + 1)c + 1

Lema 9 Un árbol binario t es balanceado sii CamMin(t) − Altura(t) ≤ 1

Prueba: En un árbol lleno t, necesariamente las hojas tienen todas la misma altura, por lo que,
una nueva hoja (en un subárbol) aumentarı́a en 1 la altura del árbol pero no cambiarı́a su camino
mı́nimo porque el otro de los subárboles (desde la raiz) mantendrı́a el mismo camino mı́nimo. En
realidad, para completar un nivel k se necesitan 2k−1 nodos. Ası́ pues existen 2k−1 vacantes que no
aumentarı́an la altura del árbol ni su camino mı́nimo que por tanto mantendrı́an 1 de diferencia.


Definición Un árbol aleatorio t con un conjunto de n > 0 hojas distintas se construye añadiendo
aleatoriamente los nodos con igual probabilidad 0.5 de corresponder el nuevo nodo (no existente
en la raiz) al subárbol izquierdo que al derecho de la raiz.

Un árbol de tal tipo tiene una altura esperada de

Altura(n) ≤ 2,41 · log2 (n + 1).

En este tipo de árboles se puede ver como el crecimiento logarı́tmico de la altura o la dependencia
logarı́tmica de la altura respecto al número de nodos incluso en casos estadı́sticos.

6.2.5. Aplicaciones de los ArbolB

En general los tipos no lineales de datos son útiles para representar relaciones de tipo uno-a-
muchos. Representación de resultados de combinaciones, como las de campeonatos de tenis5 , por
ejemplo, etc. Una estructura muy interesante es la utilizada en los códigos de Huffman que fueron
de los primeros que se emplean en algoritmos de compresión de la información o criptografı́a, etc.
En estos, cada letra del alfabeto es una hoja de un árbol binario (nada balanceado) y en el que los
caminos más largos a las hojas se procuran sean los de las letras de menos frecuencia de aparición.
Cada nodo excepto la raiz está etiquetado con un 0 ó un 1; 0 indicará una rama izquierda, 1,
derecha. De esa forma una letra queda descrita por un camino de 0’s y 1’s con la propiedad de que
todas y cada una de las letras tendrán secuencias de 0’s y 1’s siempre diferentes. Y se tendrá la
propiedan de prefijos, que equivale, en la representación arbórea de las letras el hecho de que cada
letra sea una hoja. Por ejemplo (ver [AHU83] y Apéndice A) si a → 000; b → 11, c → 01 y
d → 001, la secuencia 1101001 serı́a bcd. Ver Figura 8. El problema de los códigos de Huffman
es encontrar el reparto de códigos según la frecuencia de aparición de cada letra de forma que el
código resultante sea lo más corto posible6 .

Parse tree Vimos como se pueden evaluar expresiones polacas mediante pilas en las que se alma-
cenan los resultados intermedios. Ver en la Figura 9 como una expresión aritmética tiene una clara
representación mediante árboles binarios. Nótese que cada nodo opera sobre sus dos descendientes
5 En un campeonato de tenis aparecerán las parejas de jugadores en las hojas de un árbol, y en cada sesión de

partidos ascenderá uno de cada pareja al nodo padre correspondiente.

6 Si se hace que las letras con mayor probabilidad tengan el código más corto y estos códigos cumplen la propiedad

de prefijos, tendremos un código de compresión eficiente.

6.3 Iteradores sobre árboles 14

c e b
a d
Figura 8: Mecanismo de compresión de Huffman.

Figura 9: Representación medienta un árbol de una expresión analizada por un compi-

lador.

que hacen de operandos. Los operadores son siempre nodos interiores mientras los operandos son
hojas. Ahora el recorrido de la expresión polaca correspondiente A B C + D E ∗ ∗ F + ∗ es igual
al de la evaluación de mediante una pila de apoyo sólo que aquı́:

1. cuando se encuentre un operando ‘c’ se creará un árbol ArbolB(ArbolB(), ’c’, ArbolB())

y se apilará este árbol hoja

2. un operador ‘o’ desapilará los dos árboles últimos (se supone operadores binarios) y los to-
mará como descendientes ArbolB(Desapilar(p), ’o’, Desapilar(p)), apilando entonces
el árbol resultante.

El último ı́tem de la pila es el árbol de parsing equivalente a la expresión original. La ventaja es

que es mucho más fácil de operar con él, que conserva, su carácter simbólico (expresando ası́ la
estructura original intacta) y no se tiene que reducir a otra forma que pierda información sobre
la estructura original. En general este es el método empleado por los compiladores en el análisis
sintáctico de las expresiones. Ver el ejercicio 7.

6.3. Iteradores sobre árboles

Cuando un TDA muestra algún tipo de explı́cito de estructura, ello nos permite recorrerlo
mediante iteradores. Ya vimos que los iteradores son procedimientos (o métodos, depende) que
recorren la estructura sin modificarla. El hecho de que no se modifique la estructura no impide
que no se modifique, sin embargo, a los nodos, a los elementos.
Las estructuras lineales sólo tienen una forma de ser recorridas, a saber desde el principio
al final, en el orden en el que se hayan concebido. Los conjuntos no tienen una forma propia
de recorrido; de hecho tan sólo se acuerda, que por comodidad, se busque la forma canónica de
recorrido, que suele ser, si lo admiten los elementos del conjunto, recorrerlos por orden alfabético.
Los árboles y los grafos, en general, permiten infinidad de maneras de ser recorridos. Recorrer una
estructura plana como un grafo es linealizarla, aplastarla, para ser visitada. Ver la figura 10.
Vamos a definir formas de recorrido muy útiles sobre árboles binarios pero teniendo en cuenta
que son aplicables a cualesquiera otro tipo de árboles por medio de una fácil generalización.
Un iterador es un método asociado al TDA que pasea una función sobre cada elemento de la
estructura. Los iteradores no pueden modificar la estructura aunque sı́ los nodos, los valores en
ella. Un iterador puede no llegar al final de su recorrido si se trata de un iterador de búsqueda.
Hay dos formas de recorrido claramente distinguibles en los árboles, el recorrido en profuncidad
y el recorrido en anchura.
6.3 Iteradores sobre árboles 15

una forma de recorrido

TLista

muchas formas de recorrido

TConjunto

TGrafo

Figura 10: Cuando un TAD se define mediante relaciones entre sus componentes, los
recorridos se pueden hacer siguiendo esas relaciones. Pero cuando la relación
es con varios aparecen diversas formas de recorrerlos.

El recorrido en anchura visita los nodos por niveles:

1 1

2 2 3

3 4 5 7

Se puede implementar haciendo una función que acceda a los nodos de un nivel n y recorrer
todos los niveles del árbol desde el primero hasta su altura. Ya hemos hecho el procedimiento
ListaNivel (pág. 12). Se deja como ejercicio la presentación de estos niveles de manera que según
se vaya bajando en los niveles vayan espaciándose los nodos y quede un dibujo adecuado de los
mismos.
Los recorridos en profundidad se pueden hacer fundamentalmente de tres formas:
1. Preorden: Consiste en operar primero la raiz, luego hacer una visita en Preorden del hijo
izquierdo y después igualmente del hijo derecho

Preorden(t, op) ≡ si No EstaVacio(t) entonces

→ op(Raiz(t))
Preorden(Izda(t),op)
Preorden(Dcha(t),op)
finsi
Notemos que ocurrirı́a con una llamada como t->Preorden(PrintBase) sobre el árbol de
parsing del ejemplo anterior:
∗A+∗+BC∗DEF

2. Enorden: Consiste en visitar primero en Enorden el hijo izquierdo, después operar la raiz y
finalmente el hijo derecho

Enorden(t, op) ≡ si No EstaVacio(t) entonces

Enorden(Izda(t),op)
→ op(Raiz(t))
Enorden(Dcha(t),op)
finsi
6.3 Iteradores sobre árboles 16

Apliquemos ahora Enorden(t, WriteBase) sobre el árbol de parsing del ejemplo anterior7 :

A∗B+C∗D∗E+F

3. Posorden: Consiste en visitar primero en los hijos derecho e izquierdo en Posorden, y después
operar la raiz
Posorden(t, op) ≡ si No EstaVacio(t) entonces
Posorden(Izda(t),op)
Posorden(Dcha(t),op)
→ op(Raiz(t))
finsi
Veamos finalmente que ocurrirı́a con una llamada como Posorden(t, WriteBase) sobre el
árbol de parsing del ejemplo anterior:

ABC+DE∗∗F+∗

donde debemos reconocer la expresión original en forma postfija. Precisamente cada tipo
de recorrido representa un tipo de sintaxis de operadores: prefija (como en cos(θ) en que
aparece antes el operador que el operando), infijo, (como en 2 + 2) y postfija (2 2 +).

Podrı́an pensarse otros tipos de recorridos, pero realmente sólo de la simetrı́a de estos tres
tipos se pueden extraer propiedades interesantes. Ver los ejercicios 4 y 20.

Recorridos no recursivos Es posible evitar usar la recursión en los recorridos de los árboles
si se utilizan estructuras de apoyo como la pila y la cola. Si al llegar a un nodo lo encolamos,
procesamos, y encolamos para iterar el proceso desencolando y encolando la descendencia, nos
encontramos:

1. Vemos primero los nodos superiores

2. Vemos en orden los nodos por niveles

y se trata, por lo tanto, de un recorrido en anchura.

El algoritmo en C++ serı́a:
1 void EnAnchura(ArbolB *t) {
2 ColaNoAc q;

4 if (t->EstaVacio()) return;

6 [Link](t);
7 do {
8 ArbolB *x = [Link]();

10 cout << x->Raiz() << ", ";

12 if (!x->Izdo()->EstaVacio()) {
13 [Link](x->Izdo());
14 }
15 if (!x->Decho()->EstaVacio()) {
16 [Link](x->Decho());
17 }

19 } while (![Link]());
20 }
7 Nótese que la expresión en el árbol tiene más información que la plana en infija; entre otras cosas la última no

tiene parentizadas las operaciones que deben realizarse antes, cosa que en el árbol es obvia. Una forma de resolver
esto es “añadir un paréntesis” de apertura antes de visitar en de nuevo en Enorden y uno de cierre a la salida de la
visita.
6.3 Iteradores sobre árboles 17

Por otro lado, si en vez de una cola utilizamos una pila, el orden de visitas cambia, quedando
enterrados los primeros nodos que dejan paso a los más profundos descendientes, que son visitados
antes: recorrido en profundidad:
1 void EnProfundidad(ArbolB *t) {
2 PilaAc p;

4 if (t->EstaVacio()) return;

6 [Link](t);
7 do {
8 ArbolB *x = [Link]();

10 cout << x->Raiz() << ", ";

12 // ponemos antes al decho para que se vea después

13 if (!x->Decho()->EstaVacio()) {
14 [Link](x->Decho());
15 }
16 if (!x->Izdo()->EstaVacio()) {
17 [Link](x->Izdo());
18 }

20 } while (![Link]());
21 }

teniéndose un recorrido en preorden.

6.3.1. Árboles entrelazados

Del Lema 4 se deduce que hay n + 1 referencias a árbol vacı́o en cualquier árbol binario.
Una forma propuesta por A. J. Perlis y C. Thornton es la de reemplazar las referencias a vacı́o
por enlaces (threads) a otros nodos en el árbol. Concretamente, si Dcha(t) = ArbolB( ), podemos
sustiuirlo por una referencia al nodo que seguirı́a a t en un recorrido en Enorden; análogamente, si
Izda(t) = ArbolB( ) , lo hacemos referenciar al predecesor en el recorrido en Enorden. Ver Fig.11.
Sin embargo, para distinguir el tipo de referencia que se tiene en cada antigua referencia, se

A
B C

D E F G

H I

Figura 11: Descendientes vacı́os enlazados a los siguientes en orden.

necesitarán dos campos booleanos. La búsqueda del sucesor en Enorden de un nodo es fácil y no
requiere recursividad, en C++:
1 ArbolB *EnOrdenSuce(t: ArbolB)
2 {
3 ArbolB *temp = t->Dcha();
4 if (!t->esHiloElDcho()) // si no es ya el siguiente, buscarlo
5 while (!temp->esHiloElIzdo())
6 temp = temp->Izda();
7 return temp;
8 }

esHiloElDcho() es un método que indica si el enlace del que serı́a hijo derecho es en realidad un
hilo a siguiente. Análogamente esHiloElIzdo(). Se deja como ejercicio (26) la implementación de
un procedimiento semejante de recorrido en Enorden.
6.4 Árboles de búsqueda 18

La inserción es inmediata en nodos hoja se puede ver en la Figura 12. y, si se tienen dos

U U

B B

+T
S S

J J T

Figura 12: Inserción en nodos hoja

descendientes, hay que buscar el predecesor del subárbol derecho para actualizarlo; la sustitución
en el subárbol izquierdo de s es simétrica, como se ve en la Figura 13. Se deja como ejercicio la

Y
B

B
S
+T
S
J T

J V
V

H X
H X

Figura 13: Inserción en nodos hoja

implementación completa de árboles binarios entrelazados (28). Los árboles entrelazados también
simplifican los recorridos en Pre y Posorden.

6.4. Árboles de búsqueda

Un árbol ordenado lleno permite la búsqueda óptima de sus elementos.
En un árbol binario ordenado cada vez que comparamos el elemento buscado con la raiz
decidimos si continuar hacia abajo por la derecha o por la izquierda, dejando ası́ la mitad de los
nodos a un lado. En un número de comparaciones proporcional a la altura del árbol (h ≈ log2 (N ))
habremos decidido si el elemento está o no en el árbol. Por ejemplo, si hay 32.768 (= 215 ) elementos
en el árbol de búsqueda lleno, sólo se requieren 15 comparaciones.
1 bool Buscar(ArbolB* t, Base x) {
2 if (t->EstaVacio()) return false;
3 else if (x == t->Raiz()) return true;
4 else if (x < t->Raiz()) return Buscar(t->Izdo());
5 else return Buscar(t->Dcho());
6 }

¿Qué es un árbol binario ordenado?

Un árbol binario ordenado es un árbol binario en el que la raı́z es mayor que todos los
nodos de su subárbol izquierdo y mayor que todos los de su subárbol derecho siendo
además ambos subárboles ordenados.
6.4 Árboles de búsqueda 19

Si sólo imponemos el que sea mayor/menor que la raiz del subárbol izquierdo/derecho y no
imponemos la condición de ser mayor/menor que todos los de su subárbol izquierdo/derecho,
podrı́amos tener un árbol en el que habrı́a nodos a niveles más bajos mayores/menores que la raiz.
Ver por ejemplo la Figura 14.

10 20
8 30 15 30

7 15 8 50 7 18 25 50

2 20 2 8
no ordenado sí ordenado

Figura 14: Árboles no y sı́ ordenados

La estructura de árbol con la condición de ordenación es una excelente estructura de alma-

cenamiénto para consultas, óptima. La idea es la de guardar un número de datos grande al que
se quiera acceder con frecuencia en tiempo mı́nimo. Cuando se requiere este tipo de almacenes de
datos sin lı́mite de capacidad y óptimo acceso se recurre a los árboles binarios ordenados. Se puede
definir una interfaz para esta estructura de datos8 . En C++:
1 class ArbolBus {
2 public:
3 ArbolBus();
4 ArbolBus *Anyade(Base x);
5 ArbolBus *Borra(Base x);
6 ArbolBus *Izdo();
7 ArbolBus *Dcho();
8 Base Raiz();
9 bool EstaVacio();
10 bool Esta(Base x);
11 private:
12 bool estoyVacio;
13 Base raiz;
14 ArbolBus *izdo, *dcho;
15 ArbolBus *hacerArbol(ArbolBus *iz, Base x, ArbolBus *de);
16 Base menorABB();
17 };

No hacemos público el procedimiento de construcción hacerArbol ya que el construir y mantener

el criterio de orden es responsabilidad de la propia estructura o clase.
Se dejan como ejercicios para el estudiante los procedimientos de añadido y borrado. Nótese
que para añadir se puede seguir el mismo criterio de la búsqueda antes visto, y, si no coincide
con la raı́z, devolver el mismo árbol pero con la información añadida (recursivamente) al subárbol
adecuado. Para el borrado, sin embargo la cosa es más complicada cuando el nodo a borrar tiene
dos descendientes. Si sólo se tiene uno, o ninguno no hay problema, se devuelve el otro y ya está;
pero si se tienen los dos, no se puede devolver como árbol con el nodo borrado a los dos árboles
descendientes. En este caso se puede hacer lo siguiente:

1. substituir la información de la raiz a borrar por la del subnodo siguiente a ella (que será el
menor del subárbol derecho)

2. borrar aquél nodo (el menor del derecho)

Por lo tanto al borrar una raiz con dos descendientes devolveremos un árbol con el mismo izquierdo,
la raiz menor del derecho y el subárbol derecho con su menor borrado.
8 Reuı́mos usar la palabra TDA ya que no es exactamente una estructura abstracta sino que hacemos explı́cita la

forma en que organizamos los datos y no abstraemos sólo el comportamiento que esperamos de la estructura, que
es el de un almacén, sino que dependemos también de su estructura.
6.5 Prácticas y ejercicios 20

6.5. Prácticas y ejercicios

. 1 Para cada uno de los tres tipos de árboles que se presentan en la Figura 15, identificar

A A A

B B C D
B C D E F
E F G H I

Figura 15: Tipos de árboles del ejercicio 1.

sus roots (raı́ces), sus subtrees (subárboles), todos sus paths (caminos), minpaths (caminos
mı́nimos) y sus correspondientes lengths (longitudes) y las heights (alturas) de cada árbol.
Dar la presentación lineal parentizada de cada uno. ¿Cuál puede ser binario?

. 2 Desarrollar un procedimiento de modificación (inserción) de un nuevo nodo (hoja) en un

árbol binario, con la siguiente sintáxis:

Insert(ArbolBt, ArbolBx, boolleft, ArbolBnt)

Siendo t el árbol a modificar; x el nodo en cuyo subárbol vamos a insertar; left dirı́a si
es el izquierdo, si no, el derecho y nt serı́a el nuevo nodo a insertar. Añadir unas pre y
postcondiciones razonables y desarrollar la semántica axiomática del procedimiento.

. 3 Hacer una implementación completa en forma dinámica del TDA árbol binario en la forma
más sencilla posible con los procedimientos de acceso definidos para el TDA. No pretender
añadir reciclado de basura (es imposible en esta forma en C++). No incluir verificación de
pre y postcondiciones.

. 4 Desarrollar una librerı́a especı́fica de iteradores sobre árboles binarios IterArbolBs. Com-
pletar en C++ los tres tipos de iteradores pero cada uno con tres tipos de operaciones, un tipo
de función, operador, pasivo sobre el tipo Base de la raiz, otro activo, que pueda modificar
la raiz y, finalmente, una función que devuelva false o true sin modificar el parámetro
tipo Base de forma que el iterador se detenga en su recorrido cuando el valor sea de true y
devuelva además el subárbol del árbol en cuya raiz se dio ese true.
1 ArbolB PreordenActivo(op(Base &x)) {
2 if (!EstaVacio()) {
3 op(raiz);
4 izdo->PreordenActivo(op);
5 dcho->PreordenActivo(op);
6 return this;
7 }
8 }

Serı́a un posible aspecto del procedimiento activo, pero nótese que habrá de ser un método del
propio TDA ArbolB para poder modificar la raiz9 y devolver el mismo árbol this modificado.
En otro caso deberı́amos copiar el árbol completo con la raiz modificada.

. 5 Hacer un procedimiento bool BuscaEnArbolB(ArbolB *t, Base x) que utilizando el TDA ArbolB,
busque en un árbol binario el ı́tem dado devolviendo true si lo encuentra y false si no.

. 6 Dada la representación “arbórea” de una expresión aritmética de la Figura 16. (a) reconstruir
9 Otra opción, no contemplada en este curso, es el uso de procedimientos o clases friend, que pueden ver y

modificar los atributos del que las elija friend.

6.5 Prácticas y ejercicios 21

Figura 16: Representación expresión aritmética del ejercicio 6.

la expresión parentizada infija. (b) Presentar los operadores en forma prefija, para ello utilizar
paréntesis para aclarar los grupos de parámetros de cada operador.
NOTA: Hacer los recorridos Enorden y Posorden encerrando entre paréntesis los operandos
(que constituirı́an los descendientes de cada raiz operador).
. 7 Desarrollar un programa que utilizando los tipos Pila(ArbolB) y ArbolB(char) transforme
una cadena de caracteres en la que cada carácter represente un operando u operador de una
expresión polaca. Representar el árbol resultante.
. 8 Realizar un programa que inserte en un árbol de forma balanceada un número de elementos
cifras enteras recibidas por teclado. Previamente el driver dará al procedimiento de cons-
trucción el total de elementos a insertar. Imprimir finalmente el árbol generado.
. 9 ¿Qué problemas añade la implementación acotada mediante cursores al TDA árbol binario
de búsqueda si se implementa en C++ “a la funcional”? Desarróllese esta implementación.
Un fichero de implementación sólo podrá manejar un bloque de memoria; gestionarlo con
capacidad para que pueda mantener más de una variable árbol. Recuérdese para ello la
implementación acotada de listas con cursores ((a) sin, (b) con mantenimiento explı́cito de
vacı́os).
. 10 Construir para el TDA árbol binario (ArbolB) los procedimientos de librerı́a:
1. MinDeArbolB : T → I; PRE : T 6= ∅
devuelve el nodo más pequeño del árbol binario
2. MaxDeArbolB:T → I; PRE : T 6= ∅
devuelve el nodo mayor del árbol binario
. 11 Construir para el TDA árbol binario (ArbolB) los procedimientos de librerı́a:
1. MinHojaDeAB : T → I; PRE : T 6= ∅
devuelve la menor hoja del árbol binario
2. MaxHojaDeAB : T → I; PRE : T 6= ∅
devuelve la mayor hoja del árbol binario
. 12 Construir para el TDA árbol binario (ArbolB) el procedimiento de librerı́a: EsABB : T → B;
que nos dice si un árbol binario es balanceado
. 13 Construir para el TDA árbol binario (ArbolB) el procedimiento de librerı́a: EsABPB : T → B;
que nos dice si un árbol binario es perfectamente balanceado
. 14 Construir para el TDA árbol binario (ArbolB) el procedimiento de librerı́a: SonIgualesABAB :
T × T → B; que nos dice si dos árboles binarios son exactamente iguales.
. 15 Construir para el TDA árbol binario (ArbolB) los procedimientos de librerı́a:
1. MinEnNivelDeAB : T × N → I; PRE : Nivel(T, n) 6= ∅
devuelve la menor hoja de un nivel del árbol binario
2. MaxEnNivelDeAB : T × N → I; PRE : Nivel(T, n) 6= ∅
devuelve la mayor hoja de un nivel del árbol binario
6.5 Prácticas y ejercicios 22

. 16 Construir para el TDA árbol binario (ArbolB) el procedimiento de librerı́a: MaxNivelLlenoAB :

T → N ; que devuelve el nivel lleno más bajo.

. 17 Escribir un procedimiento que cuente el número de hojas de un TDA árbol binario

. 18 Escribir un procedimiento que cuente el número de nodos con un sólo descendiente de un
TDA árbol binario

. 19 Escribir un procedimiento que cuente el número de nodos con dos descendientes de un TDA
árbol binario

. 20 ¿Es posible reconstruir la estructura de un árbol binario a partir del conocimiento de uno
de sus recorridos? Con dos recorridos, como el Preorden y el Enorden, es posible reconocer
los nodos raiz y las hojas de un ArbolB. Hacer un procedimiento que reconstruya el árbol
original a partir de estos dos recorridos. ¿Se podrı́a hacer esto con Pre y Posorden?

. 21 Construir el procedimiento de librerı́a Nivel(ArbolB t, int n, Lista &l) que pone en l una
lista (ya creada antes) con los componentes en el nivel n del árbol.
NOTA: Usar los tipos ArbolB(char) y Lista(char).

. 22 Hacer el procedimiento CopyArbolB:

1 ArbolB *CopyArbolB(ArbolB *t)
2 /**PRE:: t existe
3 POST:: t’ = t
4 RETURN: un ArbolB conteniendo
5 la misma estructura con los ı́tems de t */

. 23 Escribir un procedimiento que devuelve el árbol simétrico (Izquierdo

Derecho) de un TDA
árbol binario. Ver Figura 17.

1 1

2 3 3 2

4 5 7 7 5 4

Figura 17: Reflexión de un árbol del ejercicio 23.

. 24 Utilizar el ArbolB con los recorridos anteriores 4 para construir una utilidad de librerı́a de
ArbolB que presente en pantalla la estructura actual de un ArbolB. Utilizar

1. el método de los paréntesis anidados

2. un método gráfico en el que el árbol aparezca verticalmente en Enorden e indentado
según el nivel

. 25 Desarrollar un procedimiento de librerı́a:

1 void PrintArbolB(ArbolB *t, int width, writeBase(const Base));
6.6 Apendice A: Técnicas de Compresión 23

que imprimirá el árbol t en un ancho de caracteres de pantalla width utilizando para cada
nodo(Base) el procedimiento que se le pase writeBase. Para ello desarrollar un procedimien-
to:
1 void PrintNivel(ArbolB *t, int nivel,int pos,int width) {
2 if ( !t->EstaVacio() && nivel > 0)
3 if (nivel == 1)
4 PrintRoot(t->Raiz(), pos);
5 else {
6 PrintNivel(t->Izda(), nivel-1, pos-width/4, width/2);
7 PrintNivel(t->Dcha(), nivel-1, pos+width/4, width/2);
8 }
9 }

que imprimirá por niveles separando adecuadamente los nodos (considerando ası́mismo los
que no existan). PrintRoot(BAse, pos) pone la información de tipo Base en la columna
pos de la lı́nea actual.
. 26 Implementar el procedimiento completo de recorrido en Enorden suponiendo que el TDA
ofrece también el procedimiento EnOrdenSuce(t) que devolverı́a el nodo siguiente a t en
Enorden (ver apartado 6.3.1).
. 27 Calcular la complejidad del procedimiento EnOrdenSuce(t) del ejercicio 26 suponiendo que
es el mismo explicado en el apartado 6.3.1. Calcular igualmente la complejidad de la iteración
recursiva en Enorden. ¿En qué difieren?
. 28 Implementar un árbol binario en forma entrelazada extendiendo la definición con dos procedi-
mientos EnOrdenSuce(t) y EnOrdenPred(t) que devolverı́an los nodos siguiente y predecesor
respectivamente en Enorden.
. 29 Implementar completamente el árbol de búsqueda descrito en la teorı́a (apartado 6.4).

6.6. Apendice A: Técnicas de Compresión

Aunque originalmente desarrolladas estas técnicas para el ahorro de tiempo minimizando la
cantidad de información a transmitir en sistemas de comunicaciones, su uso se ha generalizado
para el ahorro de espacio en sistemas de almacenamiento. Pero actualmente el auge de las co-
municaciones ha llevado a las técnicas de compresión a un primerı́simo plano en informática. De
hecho se aceptan incluso técnicas de compresión con pérdidas esto es que eliminan parte de la
información del objeto original en el afán de disminuir el el tamaño del resultado. En gráficos
por ejemplo JPG (Joint Photographic Group) es un formato que, en un grado ajustable, comprime
dramáticamente imágenes de tipo fotográfico (con degradados de color y muchos colores), mientras
que formatos como GIF (Graphic Image Format, original y con Copyright aún de Compuserve),
no provoca pérdida y es más adecuado para gráficos de (menos) colores planos.
En general, la mayorı́a de los ficheros de ordenador contienen, vistos en su representación fı́sica,
una cantidad de redundancia. Los métodos de compresión de ficheros se basan en precisamente en
el hecho del “poco contenido informativo contenido en los ficheros”. Especialmente los dibujos del
tipo “imagen de bits” son de los mejores candidatos a la compresión10 .
10 Existen fundamentalmente dos tipos de representación de imágenes en el ordenador aunque algunos formatos

como el ‘PICT’ de Macintosh o el ‘EPSF’ de Adobe, pueden coexistir las dos en un único fichero. Estos son el
de parámetros, también llamado de objetos, donde cada elemento del dibujo es un conjunto de parámetros y los
objetos se reproducen cada vez que se quieren visualizar adaptándose al medio fı́sico en el que se quiera dibujar; dan
la mejor calidad en cada medio. El otro formato, fundamental en captación de imágenes ‘fotográficas’ o de scanner
es el de “imagen de bits” de colores o de semitonos (especialmente conocido es el formato ‘TIFF’), que se construye
como imagen directa del original, por puntos sin reconocimiento ninguno de objetos y adaptado únicamente a la
resolución (número de dips por pulgada, dpi, y colores y tonos controlados por los bits por pulgada, bpi), cuya
calidad depende del medio de recogida de la imagen directa o del programa de ‘dibujo’ empleado. Especialmente
estos últimos ficheros requieren gran espacio de almacenamiento. Por ejemplo, una imagen ‘TIFF’ de tamaño A4
con 300dpi y 8bpi (256 colores, sólo) ocuparı́a del orden de
(300 × 300) × (11 × 8) × 8 = 631 360,000/8 = 71 920,000 bytes
6.6 Apendice A: Técnicas de Compresión 24

Con métodos elementales como los que veremos son tı́picos ahorros del orden del 20 % al 50 %
en ficheros de texto y, del orden del 50 % al 90 % en ficheros binarios. En algunos tipos de ficheros,
como los compuestos por bits aleatorios, poco ahorro se puede conseguir, ası́mismo con ficheros
ya comprimidos, como serı́a de esperar. En estos últimos casos incluso podemos tener ficheros que
ocupen más que los originales.
Finalmente, aunque el costo de los periféricos pudiera hacer pensar en la caı́da en desuso de
las técnicas de compresión, las necesidades de espacio crecen aún con mayor velocidad conforme
aumenta la velocidad de procesamiento de la información. Un buen ejemplo de esto lo constituyen
las “animaciones en tiempo real”, que vienen a estar constituı́das por secuencias de unos 30–
60 ‘frames’ por segundo y cada frame (imagen), ocupa del orden de megabytes de información.
Hasta tal punto se requieren técnicas de compresión y lo más eficientes posible que se están
diseñando y comercializando ya ‘tarjetas’ que comprimen las imágenes de manera aproximada, esto
es, recogiendo tan sólo las partes más rápidamente analizables de la imagen. En estos procesos se
emplean intensivamente técnicas avanzadas basadas en la transformada rápida de Fourier (FFT).

6.6.1. Codificado de secuencias (Run-Length encoding)

El tipo de redundancia más simple que puede aparecer en un fichero es el de encontrarse
secuencias de caracteres (o bits) repetidos. Por ejemplo, en una cadena de “sólo texto”:
AAAABBBBBBBBCCDDDDDDDDDDDDDABCABCABCABCABCABCMMMMMMMMMMABCM

Esta cadena puede ser representada de manera compacta reemplazando cada patrón de caracteres
repetido por una sóla representación del carácter (o del conjunto de caracteres) y un número indica-
tivo del orden de repetición. Por ejemplo: 4A8BCC13D6(ABC)10M ABCM . En ficheros binarios
será necesaria una convención más refinada. Notemos que parte de la información ya comprimida
está compuesta por dı́gitos, en general, “no caracteres”, de forma que es fácil diferenciar la infor-
mación en sı́ de la información de compresión de secuencias repetidas. En estos casos se recurre
a convenir en un código o “carácter de escape” como método de separación entre la información
en sı́, que puede ser cualquiera, y la información de compresión. Pero, ¿qué hacemos si aparece
el código de escape en la secuencia de información repetida? La solución está en convenir en que
dos secuencuencias de escape repetidas (esto es una cadena de información nula) representan a un
carácter de información igual al de escape. De esta forma los únicos ficheros que pueden llegar a
crecer al ser comprimidos son los que tengan el carácter de escape muchas veces.
El método de run-length encoding es inútil, en general con los ficheros de texto, donde lo
único que se suele repetir son los espacios en blanco. Y, hoy dı́a, más que antes, cuando alguna vez
se usó este método de compresión para comprimir ficheros, se suele utilizar el tabulador en vez de
los múltiples espacios.

6.6.2. Codificado de longitud variable

El codificado de longitud variable (variable-length encoding) se basa en rediseñar totalmente el
método de representar la información en los bytes. Efectivamente, si los caracteres más repetidos
de un fichero se codifican con menor cantidad de bits que la estándard de 8 bits/carácter, nos
escontraremos ahorrando espacio según lo repetido que se encuentre cualquier carácter, y no sólo
por formar secuencias, como en el run-length encoding. Por ejemplo, si queremos codificar la
palabra: ‘ABRACADABRA’ utilizando un código estándard de 5 bits/letra que represente a cada
letra del alfabeto inglés (sin acentos) por su posición (al espacio, con 0):

0000100010100100000100011000010010000001000101001000001

que para ser leı́do bastarı́a con leer de cinco en cinco bits e irse al carácter correspondiente a ese
valor. Sin embargo con este método, la ‘D’, que aparece sólo una vez, requiere la misma cantidad
de bits que la ‘A’, que aparece 5. Con un codificado de longitud variable podrı́amos minimizar la
longitud de los códigos de las letras más frecuentes reduciendo ası́ la longitud del código completo.
de los cuales, basta con que exista un fondo uniforme para que se tengan repetidos, a veces, algunos de estos 7Mb.
 6.6 Apendice A: Técnicas de Compresión 25

propiedad de prefijos
Ahora bien, para poder emplear menor cantidad de bits para las letras más frecuentes, es necesario
que las menos frecuentes comiencen su codificación por secuencias de bits completamente distintas
de las más cortas. Esta es la única forma de evitar ambigüedades en el código resultante. Por
supuesto, también se pueden emplear caracteres especiales de separación entre los códigos, pero
esto alargarı́a mucho el resultado. A la caracterı́stica anterior de la codificación sin cabeceras
repetidas se le llama propiedad de prefijos.
Por ejemplo, si codificamos:
A 11
B 00
C 010
D 10
R 011
sólo existe una forma de codificar la cadena original del ejemplo:

1100011110101110110001111

que ocupa tan sólo 25 frente a los 55 bits originales (45 % del original).
Una forma fácil de representar el código es mediante un árbol (trie 11 ). En efecto, como
veremos, cualquier trie con M nodos externos puede ser usado para representar cualquier mensaje
con M posibles letras. Ver Figura 18. El código correspondiente a cada carácter es el camino hasta

Figura 18: Árboles para codificar palabras: Tries.

el carácter desde la raiz, tomando ‘0’ cuando se “tuerce a la izquierda” y ‘1’, a la derecha. La
segunda codificación del gráfico nos darı́a:

01101001111011100110100

y es dos bits más corta.

Con esta representación en forma de trie tenemos garantizada la propiedad de prefijos, pero
¿cuál es la representación que nos dá el código más corto? Existe un método elegante de computar
el trie que nos lleva a la cadena de bits más corta para cualquier mensaje dado. El método general
original para esto fue inventado por D. Huffman en 1952.

Construcción de códigos de Huffman Lo primero que necesitamos para construir los códigos
de Huffman son las frecuencias de aparición de cada carácter dentro del texto a codificar12 . Una
vez construido el array de frecuencias
int freq[128];

se construye un nodo por cada letra con frecuencia > 0 guardando en el nodo tanto la letra como
su frecuencia. Después se buscan los dos nodos con menor frecuencia y se construye otro nodo que
los tenga como hijos y, sumando las frecuencias de los dos nodos la contamos como la frecuencia
del padre recien creado (no importa cuáles se tomen si existen varios con la menor frecuencia).
Después se vuelven a buscar los dos nodos con la menor frecuencia en ese bosque en extinción
11 Un trie, de retrieval es un árbol n-ario que contiene la información en los nodos externos, teniendo, por lo tanto

dos tipos de nodos, los internos, para los enlaces y los externos
12 Supondremos, en lo que sigue, que estamos codificando texto ASCII, esto es, las letras pertenecientes a los

primeros 128 caracteres ASCII

6.7 Referencias de consulta 26

y se crea un nuevo nodo de la misma forma. Este proceso se continúa con árboles cada vez más
alto y reduciendo la población del bosque de uno en uno: se eliminan dos árboles, se añade uno.
Finalmente nos quedará un sólo árbol conjunto.
En el árbol construı́do tendremos los nodos con menor frecuencia más abajo y los de mayor
frecuencia más arriba. Por otro lado, las etiquetas contenidas en los nodos externos informan
de la frecuencia de aparición mientras que las de los nodos internos son los acumulados de su
descendencia.
La construcción final del código de Huffman no es más que el ver cada nodo externo como
una letra y el camino desde la raiz hasta él (más corto mientras más frecuente sea la letra), una
serie de ‘0’ y ‘1’ según se tome la rama izquierda o la derecha, respectivamente.

Lema 10 La longitud del mensaje comprimido por el método de Huffman es igual a la longitud
de los cominos externos ‘pesada’ con las frecuencias de cada nodo externo.

Prueba: La longitud de camino externo pesada es la suma de las longitudes de cada camino
externo multiplicada por la frecuencia, en este caso, de aparición de cada nodo externo. Por tanto,
tenemos la cantidad de bits total del texto codificado. 

Lema 11 No existe un árbol con las mismas frecuencias en los nodos externos que tenga menor
longitud de camino externo pesada que la del árbol de Huffman.

Prueba: Si se construye cualquier otro árbol con distinta estrategia que la de tomar los dos
nodos con menores frecuencias primero, por el lema anterior nos encontraremos con términos que
aumentan necesariamente la longitud del código resultante. Por inducción se puede comprobar que
no existe mejor estrategia que la de tomar los nodos de menor frecuencia primero. 

6.7. Referencias de consulta

Sobre el tema de árboles y en particular, binarios y de búsqueda, hay abundantes referencias. El
TDA está claramente formalizado en [Mar86]; igualmente [Har89] ofrece una rigurosa visión de
TDA. Por otro lado, [AHU83] da una visión amplia de aplicaciones estudiadas en detalle. Tam-
bién [Wir76] expone el tipo de datos árbol muy detenidamente y desarrolla diversos algoritmos
de equilibrado, etc. Sobre los códigos de Huffman se pueden encontrar discusiones en [AHU83]
y [Kin90]. Sobre árboles equilibrados, de búsqueda, y tipos especiales de árboles, etc. consul-
tar [Knu73]. Los árboles entrelazados y AVL están muy claramente expuestos en [Azm88].

Referencias
[AHU83] A. Aho, J. Hopcroft, and J. Ullman. Data Structures and Algorithms. Addison-Wesley,
1983. Traducido al castellano, 1988.
[Azm88] Manoochehr Azmoodeh. Abstract data types and algorithms. MacMillan Education, first
edition, 1988.
[Har89] Rachel Harrison. Abstract Data Types in Modula-2. John Wiley & Sons, 1989.
[Kin90] Jeffrey H. Kingston. Algorithms and Data Structures. Design, Correctness, Analysis.
Addison-Wesley, 1990.
[Knu73] Donald E. Knuth. The Art of Computer Programming. Vol. 3: Searching and Sorting.
Addison-Wesley, Massachusetts, 1973. Traducido al castellano en Ed. Reverté, Barcelona.
[Mar86] Johannes J. Martin. Data types and data structures. Prentice-Hall, 1986.
[Wir76] Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice-Hall, New York,
1976. Traducción al castellano en Ed. del Castillo, Madrid (1980).
REFERENCIAS 27

Juan Falgueras
Dpto. Lenguajes y Ciencias de la Computación
Universidad de Málaga
Despacho 3.2.32