PDF de programación - Arboles Binarios

Arboles Binarios

Objetivo:
Dar una introducción a los árboles y mostrar la forma de implementar un árbol binario, ya sea en una
estructura estática (un vector) o dinámicamente (semejante a una lista ligada).

Descripción:
A lo largo de la siguiente práctica se mostrarán algunos conceptos útiles para comprender que es y para
que pudiera servir un árbol, además de que se mostrarán dos pequeños ejemplos que muestran algunos
ejemplos de utilidad para árboles binarios.

Nota:
El presente documento es una pequeña síntesis sobre árboles binarios. Se trata este
tema porque estos representan una de las estructuras de datos más importantes en
computación y estos pueden aplicarse para la solución de una gran variedad de
problemas, pero no muchas personas los ven como una buena solución puesto que los
consideran un tanto complejos. El objetivo del presente será dejar claro que es un
árbol binario y crear algunos ejemplos para tratar de tener una mayor comprensión.
Y así después cada uno de nosotros podamos definir si es conveniente aplicarlos a
la solución de algún problema o si alguna otra estructura de datos puede ser una
mejor opción. Puesto que solo veremos árboles las estructuras de datos alternativas
corren por su cuenta :-)

Desarrollo:
Conceptos y Terminología básica
Si vamos a trabajar con árboles, lo primero que tenemos que ver es que es un árbol. Aquí tenemos
algunas definiciones para árbol:

- Un árbol es una estructura de datos no lineal y homogénea en el que cada elemento puede

tener varios elementos posteriores, pero tan sólo puede tener un elemento anterior.

- Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados
nodos; de los cuales uno es conocido como raíz. Además se crea una relación o parentesco entre
los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

- Un árbol es una estructura compuesta por un dato y varios árboles. Dado un nodo cualquiera de
la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo
cualquiera puede ser considerado como la raíz de un árbol completo.
Son estructuras dinámicas no lineales. Dinámicas porque las estructuras de árbol pueden
cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol
pueden seguirle varios elementos. En las estructuras de datos lineales cada elemento tiene un
único elemento anterior y un único elemento posterior.

-

El tipo de estructura más general son los grafos. En un grafo cada elemento puede tener varios
elementos anteriores y varios elementos posteriores. Los árboles no son más que un tipo especial de
grafo en el que cada elemento puede tener varios elementos posteriores, pero tan sólo puede tener un
elemento anterior. Tanto grafos como árboles son estructuras no lineales.

Creo que la mayoría, sino es que todos, hemos utilizado los árboles cuando hemos hecho un árbol
genealógico o alguna estructura jerárquica de alguna organización. Y que me dicen de la forma en la
que organizamos la información en nuestras maquinas (se hace en una estructura de directorios y
subdirectorios en forma de árbol, para facilitar su búsqueda). Talvez sin darnos cuenta, pero hemos
manejado el concepto de árbol .

Además de la definición debemos conocer otros conceptos bastante importantes, pues estos pudieran
ser útiles a la hora de codificar un árbol:
En relación con otros nodos:

 Nodo padre. Nodo que contiene un puntero al nodo actual. En un árbol un nodo solo puede
tener un nodo padre. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X
es antecesor de Y. En la Figura 1: B es padre de E y F.

 Nodo hijo. Cualquiera de los nodos apuntados por uno de los nodos del árbol. Un nodo puede
tener varios hijos. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que
X es descendiente directo de Y. En la Figura 1: E es hijo de B.

 Hermano. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. En la

Figura 1: E y F son hermanos.

En cuanto a la posición dentro del árbol:

 Nodo raíz. Es el único nodo del árbol que no tiene padre. Este es el nodo que usaremos para

referirnos al árbol. En la Figura 1 A es el nodo raíz.

 Nodo hoja. Nodo que no tiene hijos. Se le llama hoja o terminal a aquellos nodos que no tienen

ramificaciones (hijos). En la Figura 1 N es un nodo hoja.

 Nodo interior. Es un nodo que no es raíz ni hoja. En la Figura 1 D es un nodo interior.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

 Orden. Es el número potencial de hijos que puede tener cada elemento de árbol. De este modo,
diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede
apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo (Figura 1)
es de orden tres.

 Grado. El número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del
ejemplo, el grado es tres, ya que tanto A como D tienen tres hijos, y no existen elementos con
más de tres hijos.

 Nivel. Se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El
nivel de la raíz es cero, el de sus hijos uno y así sucesivamente. En el ejemplo, el nodo D tiene
nivel 1, el nodo G tiene nivel 2, y el nodo N nivel 3.

 Altura. La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo
de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de
altura de ramas; el máximo número de nodos que hay que recorrer para llegar de la raíz a una de
las hojas. El árbol de la Figura 1 tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1,
la N cero...

 Peso. Es el número de nodos del árbol sin contar la raíz.
 Camino. Es una secuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e

hijo. En el ejemplo A-D-H y A-C-G-M son caminos.

 Longitud de camino. Es el número de arcos que deben ser recorridos para llegar desde la raíz
al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos
longitud de camino 2 y así sucesivamente. En nuestro árbol de ejemplo G tiene longitud de
camino 3 y N tiene longitud de camino 4.

 Rama. Es el camino desde el nodo raíz a una hoja. En el ejemplo A-B-E-K y A-B-F son ramas.

A

C

B

E

F

G

H

D

I

J

K

L

M

N

O

Figura 1. Árbol de grado tres

Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar
fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol
genealógico, para el análisis de circuitos eléctricos, para numerar los capítulos y secciones de un libro,
etc.

Bueno y como dijimos que lo que se vería aquí es árboles binarios pues yo creo que mejor nos vamos
centrando en estos…

Árboles binarios
Los árboles de orden dos son bastante especiales. Estos árboles se conocen también como árboles
binarios, ya que cada nodo del árbol no tendrá más de dos descendientes directos.

Algunas definiciones pueden ser:
1. Un Árbol binario es un árbol de grado 2
2. Un Árbol binario es aquel que:

a. Es vacío, ó
b. Esta formado por un nodo cuyos subárboles izquierdo y derecho son a su vez árboles

binarios.

N

E

A

G

O

R

U

V

Figura 2. Ejemplo de un árbol binario

En alguna de las definiciones del inicio del documento, la tercera para ser precisos, se utiliza la
recursión para definir un árbol porque representa la forma más apropiada y porque además es una
característica inherente de los mismos. En cualquier árbol, no sólo en los binarios, si eliminamos el
nodo raíz, obtenemos dos árboles; en el caso de que sea un árbol binario. Aquel que colgaba del enlace
izquierdo del nodo raíz se denomina subárbol izquierdo y aquel que colgaba del enlace derecho se
denomina subárbol derecho. Además, en un árbol binario, todos los subárboles son también árboles
binarios.
De hecho, a partir de cualquier nodo de un árbol podemos definir un nuevo árbol sin más que
considerarlo como su nodo raíz. Por tanto, cada nodo tiene asociados un subárbol derecho y uno
izquierdo.

Existen dos tipos de árboles binarios que se consideran especiales en función de ciertas propiedades.
Estos son los siguientes:

1. Árbol binario equilibrado
2. Árbol binario completo

Árbol binario equilibrado
Es un árbol en el que en todos sus nodos se cumple la siguiente propiedad:

| altura(subárbol_izquierdo) – altura(subárbol_derecho) | ≤ 1

E

A

M

N

O

R

Q

V

N

E

A

Figura 3. Árbol equilibrado

Figura 4. Árbol NO equilibrado

Árbol binario completo
Es un árbol en el que todos los nodos tienen dos hijos y todas las hojas están en el mismo nivel. Se
denomina completo porque cada nodo, excepto las hojas, tiene el máximo de hijos que puede tener.

N

E

R

A

G

O

V

Figura 5. Árbol binario completo

Recorridos por árboles
Una de las cosas que debemos poder hacer con un árbol es poder movernos a través de la información
que este contiene. El modo evidente de moverse a través de las ramas de un árbol es siguiendo las
referencias de los nodos que las componen. Los recorridos dependen en gran medida del tipo y
propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos
recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad.
En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Estos tres casos son:

-
-
-

Pre-orden
In-orden
Post-orden

Recorrido Pre-orden (N – I – D)
En este recorrido lo primero que se obtiene o evalúa es el nodo, antes de recorrer las ramas;
posteriormente se recorre la rama izquierda y finalmente la rama derecha. El orden es Nodo – Izquierda
– Derecha (N – I – D).
El rec