Investigacion

UNIDAD VI

ÁRBOLES BINARIOS

6.1. REPRESENTACIÓN DE ÁRBOLES BINARIOS

6.1.1. TERMINOLOGÍA DE ÁRBOLES BINARIOS

Las estructuras dinámicas lineales de datos( listas enlazadas, pilas, colas) tienen grandes ventajas de flexibilidad sobre las representaciones contiguas, pero tienen un problema son listas secuenciales, es decir, que por la forma en la que están dispuestas es necesariomoverse un elemento a la vez debido a que cada elemento tiene un siguiente elemento, esta linealidad es típica de cadenas, de elementos que pertenecen a una sola dimensión: campos en un registro, entradas en una pila, entradas en una cola y nodos en una lista enlazada simple. En esta parte se mostraran las estructuras de datos no lineales conocidos como árboles, adicionalmente podremos decir que noes el único tipo de estructura no lineal pues a parte de los árboles existen los grafos la cual tiene aplicaciones muy diversas en las ciencias.

6.1.2. IMPLEMENTACION DE UN ARBOL BINARIO

Un árbol binario es un conjunto finito de elementos que está vacío, o está dividido en tres subconjuntos desarticulados. El primer subconjunto contiene un solo elemento llamado raíz del árbol. Los otrosdos son en sí mismos, árboles binarios, llamados subárboles izquierdo y derecho del árbol original. Un subárbol izquierdo o derecho puede estar vacío. Cada elemento de un subárbol se llama nodo del árbol.

En la siguiente figura se muestra un árbol binario. Este árbol consiste en nueve nodos y tiene ‘A’ como raíz. Su subárbol izquierdo tiene a ‘B’ como raíz y su subárbol derecho a ‘C’.La siguiente figura muestra estructuras de árboles que no son binarios. De tal modo que, si ‘A’ es la raíz de un árbol binario y ‘B’ es la raíz de su subárbol derecho o izquierdo entonces ‘A’ se llama el padre de ‘B’, y ‘B’ el hijo izquierdo o derecho de ‘A’. Un nodo que no tiene hijos se llama hoja. El nivel de un nodo en un árbol binario se define como sigue. La raíz del árbol tiene nivel0 (cero) y el nivel de cualquier otro nodo del árbol es uno más que el nivel de su padre. Un árbol binario de completo de profundidad ‘D’ es el árbol estrictamente binario cuyas hojas están en el nivel ‘D’. En la siguiente figura se muestra un árbol de profundidad 3.

OPERACIONES CON ÁRBOLES BINARIOS

Existen varias operaciones simples que pueden aplicarse a árboles binarios. Si p es unapuntador a un nodo nd de un árbol binario, la función info(p) da como resultado los contenidos de nd. Las funciones left(p), right(p), father(p), da como resultado el apuntador nulo sí nd no tiene hijo izquierdo, hijo derecho padre o hermano. Como consecuencia las funciones isleft(p) e isright(p) dan como resultado verdadero (true) sí nd es hijo izquierdo o derecho, respectivamente, de algún otronodo del árbol, y falso (false) en caso contrario.

q = father(p);
if(q == null)
return(false);
if(left (q) == p)
return(true);
return(false);

APLICACIONES DE ÁRBOLES BINARIOS

Un árbol binario es una estructura de datos útiles cuando en cada punto de un proceso hay que tomar una decisión de doble opción. Como en la aplicación para encontrar duplicados:

/* Leer elprimer número e insertarlo en un árbol binario de un solo nodo */

scanf (“%d”, &number);
tree = maketree (number);
while (hay número rezagados en la entrada)
{
scanf (“%d”, number);
p = q;
while (number != info(p) && q != NULL)
{
p = q;
if (number < info(p))
q = left(p);
else
q = right(p);
}/* Fin del while */
if (number == info(p))
printf (“%d %s \n”, number, “es un duplicado”);
/* Insertar number a la derecha o izquierda de p */
else if (number < info(p))
setleft(p, number);
else
setright(p, number);
} /* Fin del while */

Otra operación común es recorrer un árbol binario; esto e pasar a través del árbol, enumerando cada uno de sus...