Arboles Binarios

ARBOLES BINARIOS
Yandry Rene Mera Macías

• Se define un árbol binario como un conjunto finito de elementos (nodos) que
bien está vacío o está formado por una raíz con dos árboles binarios disjuntos

• Las aplicaciones de los arboles binarios son muy variadas ya que se les puede
utilizar para representar una estructura en la cual es posible tomar
decisiones con dos opciones en distintospuntos.

Árbol binario de búsqueda
Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos
elementos se identifican por una clave única

Un árbol bario con n = 2 se denomina árbol binario
La información almacenada en los nodos del árbol se denomina etiqueta
Las hojas son árboles con un solo nodo (árboles binarios: árbol compuesto por una raíz y 2subárboles vacíos)

Etiqueta
Nodo

Hoja

Clasificación de Árboles Binarios
Árboles
Binarios

Distinto

Similares

Equivalen
tes

Completo
s
G
C

J

Arboles Enhebrado
• Existe un tipo especial de árbol binario llamado
enhebrado, el cual contiene hebras que pueden estar a la
derecha o a la izquierda

• Comprobar si un árbol está vacío.
• Un árbol está vacío si su raíz esNULL.
• Calcular el número de nodos.
• Tenemos dos opciones para hacer esto, una es llevar siempre la cuenta
de nodos en el árbol al mismo tiempo que se añaden o eliminan
elementos. La otra es, sencillamente, contarlos.
• Para contar los nodos podemos recurrir a cualquiera de los tres modos
de recorrer el árbol: inorden, preorden o postorden, como acción
sencillamente incrementamos elcontador.
• Comprobar si el nodo es hoja.

• Esto es muy sencillo, basta con comprobar si tanto el árbol izquierdo
como el derecho están vacíos. Si ambos lo están, se trata de un nodo
hoja.

Recorrido en Arboles
• Hay tres métodos para recorrer un árbol binario a saber
recorridos de
• PREORDEN
• INORDEN
• POSORDEN

Recorrido preorden

Para recorrer un árbol binario no vacío enpreorden, hay que realizar las siguientes operaciones
recursivamente en cada nodo, comenzando con el nodo de raíz:
1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho

Recorrido inorden

Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes
operaciones recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo2. Visite la raíz
3. Atraviese el sub-árbol derecho

Recorrido posorden

Para recorrer un árbol binario no vacío en posorden, hay que realizar las siguientes operaciones
recursivamente en cada nodo:
1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz

Declaración de tipos
Como estamos trabajando con un árbol binario, sólo necesitamos una estructurapara
referirnos tanto a cualquiera de los nodos como al árbol completo.
Recuerda que cualquier nodo puede ser considerado como la raíz de un árbol.

typedef struct _nodo
{ int dato;
struct _nodo *derecho;
struct _nodo *izquierdo;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;

Insertar un elemento en un árbol ABB
Padre = NULL
nodo = Raiz
Bucle: mientras actual nosea un árbol vacío o hasta que se encuentre el elemento.
Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el
árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.
Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el
árbol derecho: Padre=nodo, nodo=nodo->derecho.

Si nodo no es NULL, el elemento está en elárbol, por lo tanto salimos.
Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el
nuevo elemento, que será la raíz del árbol.
Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un
nuevo árbol izquierdo de Padre.
Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un
nuevo árbol derecho de Padre....