ARBOLES 3

ÁRBOLES
____________________________________________________________________________________________________

Á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 listassecuenciales, es
decir, que por la forma en la que están dispuestas es necesario moverse 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 estructurasde datos no lineales
conocidos como árboles, adicionalmente podremos decir que no es 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 primersubconjunto contiene un solo elemento llamado raíz del árbol. Los
otros dos 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árbolizquierdo tiene a „B‟ como raíz y su subárbol derecho a „C‟.

A

B

D

C

E

G

F

H

I

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____________________________________________________________________________________________________
ESTRUCTURA DE DATOS
ING. OSORNIO

80

ÁRBOLES
____________________________________________________________________________________________________

de un nodo en un árbol binario se define como sigue. La raíz del árbol tiene nivel 0 (cero) y el nivel de
cualquier otro nodo del árbol es uno más queel 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.
A

B

C

D

G

E

F

H

I

A

B

C

D

F
E

G

OPERACIONES CON ÁRBOLES BINARIOS

____________________________________________________________________________________________________
ESTRUCTURA DEDATOS
ING. OSORNIO

81

ÁRBOLES
____________________________________________________________________________________________________

Existen varias operaciones simples que pueden aplicarse a árboles binarios. Si p es un apuntador 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 nulosí 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 otro nodo 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 el primer 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)...