Programacion

Laboratorio de Programación 1ºA E.T.S.I. Informática Gestión

Práctica 19: Árboles

Binarios en C++

Teoría.
Las estructuras dinámicas vistas hasta ahora son lineales (listas enlazadas, pilas,colas). Estas estructuras tienen grandes
ventajas en cuanto a flexibilidad sobre las representaciones contiguas, pero tienen un punto débil: son listas secuenciales,
es decir, están dispuestas deforma que es necesario recorrer cada posición al menos una vez (cada elemento tiene un
sucesor). Mediante los árboles binarios se introduce el concepto de estructura de bifurcación, donde cadaelemento puede
tener más de un posible 'siguiente', con lo cual es posible resolver algunos problemas de difícil solución cuando se usan
estructuras dinámicas lineales.
El árbol es una estructura muyusada en todos los ámbitos de la informática ya que se adapta a la representación natural de
informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Las estructuras tipoárbol se
usan para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.
Un árbol se define como un conjunto finito de uno o más nodosrelacionados de la siguiente forma:
• Hay un nodo especial llamado raíz del árbol, que proporciona un punto de entrada a la estructura.
• Los nodos restantes se subdividen en m>=0 conjuntos disjuntos, cadauno de los cuales es a su vez un árbol.
Estos árboles se llaman subárboles del raíz.
Nótese que esta definición es recursiva, se define un árbol en función de otros árboles.
La representación yterminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los
árboles genealógicos: padre, hijo, hermano, ascendiente, descendiente. Junto a estos conceptos sedefinen otros tales como
raíz, nodo, hoja, camino, nivel, profundidad, etc., con los cuales se supone familiarizado al alumno.

1
2
4

3
6

5

7

8

9
Un Árbol Binario se define como...